混合蚁群算法（精选十篇）
混合蚁群算法 篇1
遗传算法是受生物进化学说和遗传学说的启发而发展起来的,由美国的J.H.Holland教授于1975年创立[2]。它模拟自然选择和遗传过程中发生的繁殖、杂交和变异现象,进行群体智能进化计算。由于遗传算法求解复杂优化问题的巨大潜力,近年来再许多工程领域的得到应用。
本文基于连续优化目的开展基础性研究,通过蚁群算法与遗传算法的混合编程,改进算法的性能,以求解连续优化问题。
1 求解连续优化问题的蚁群算法
1.1 蚁群算法的基本思想
1)状态转移规则:蚁群算法使用的状态转移规则为随机比例规则,是基于求解TSP问题提出的,它给出来位于城市i的蚂蚁k选择移动到城市j的概率。公式为:
其中τ(i,j)表示边(i,j)的适应值,即“激素”;η(i,j)为距离L(i,j)的倒数。α,β为两个参数,分别表示蚂蚁运动过程中积累信息和启发信息的相对重要程度。
在蚁群算法中,选择方式为:
其中,q为均匀分布在[0,1]上的一个随机变量,q0为在[0,1]上的参数,而J则是根据等式(1)计算出来的概率分布来进行选择。
2)全局更新规则:蚂蚁算法有不同的更新规则,蚁群系统采用全局全局更新规则,只允许全局最优的蚂蚁释放信息素。这样做可以使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径的邻域内。全局更新在所有蚂蚁都完成一次搜索后用下边(3)式进行全局更新:
其中:ρ为信息素挥发参数;Lgb为到目前为止找到的全局最优路径。
3)局部更新规则:每只蚂蚁建立一个解的过程中也同时进行激素迹的更新,规则如下:
其中,r为[0,1]间的参数。
1.2 基于图解的蚁群系统
用蚁群算法求解最优化问题,首先需要将最优化问题转化为求解最短路径问题。为此,文献[3]提出了有向图的概念,文献[4]提出了构造图的概念,他们的共同特点是通过行程对可行解进行编码,进而求解优化问题。
本文在文献[4]的基础上,以二进制为基础,编制了如图1所示的构造图。每只蚂蚁从初始子结点N00或N01出发,顺序走过N1,N2,…,的其中一个子结点,直到终结点Nk0、Nk1,组成路径(N0tN1tN2t…Nkt),(t∈{0,1})。Nkt取二进制数0或1,路径即可代表一个二进制可行解。
在图1中,每两个相邻结点Ni,Nj之间有4个并行路径,分别连接他们的子结点:Ni0->Nj0,Ni0->Nj1,Ni1->Nj0,Ni1->Nj1,其信息值分别记为τ(i,j)1,τ(i,j)2,τ(i,j)3,τ(i,j)4,蚂蚁行进时只能选择其中的一条路径。每只蚂蚁行进开始时,首先根据τ(0,1)s,s∈{1,2,3,4},概率选择一条路径,确定前两个子结点。当第二个子结点为N10时,根据τ(1,2)1,τ(1,2)2值的大小按概率选择下一个子结点;当第二个子结点为N11时,根据τ(1,2)3,τ(1,2)4值的大小按概率选择下一个子结点。这样一直概率选择到最后的子结点Nk0或Nk1,即构成一个完整路径及可行解。
1.3 用于连续优化的蚁群算法
1)参数取值的二进制编码:参数取值的二进制编码与遗传算法相同。假设优化问题的可行解为{x1,x2,…,xm},其中变量xi用长度为l的二进制串表示为{blbl-1…b2b1},其中bj∈{0,1},它对应蚁群算法结构图1中的一段路径(NL+1,tNL+2,t…NL+l,t)。设xi取值范围为[ximin,ximax],则对应的解码公式为:
在TSP问题中,最优路径对应的是最短路径。在优化问题中,最优路径为对应目标函数值最优(最大或最小)的蚂蚁行进路径。
2 蚁群算法与遗传算法的混合编程
2.1 遗传算法及其实现
基本遗传算法程序中使用的是二进制编码,将原问题的解空间映射到位串空间{0,1}上,然后在位串空间上进行遗传操作,结果再通过解码过程还原成其表现型以进行适应度评估,其求解过程为:
1)对待解决问题进行编码。
2)随机初始化群体X(0)=(x1,x2,…,xn)。
3)对当前群体X(t)中每个个体xi,解码计算其适应度F(xi)。解码公式与上式(5)相同。
4)进行选择、交叉、变异等遗传操作,产生下一代个体。
5)对t=t+1代继续从3)步进化计算,直到满足终止条件。终止条件一般为预定的进化代数或误差限小于设定值或。
2.2 遗传算法的常用算子
1)选择算子(selectio):选择算子从群体中按某一概率成对选择个体,某个体被选择的概率Pi与其适应度值成正比。常用的实现方法是轮盘赌规则。
2)交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率Pc进行交叉,生成两个新的个体,交叉位置是随机的。
3)变异算子(Mutation):变异算子将新个体的基因链的各位按概率Pm进行变异,对二值基因链(0,l编码)来说即取反。
2.3 蚁群算法与遗传算法的混合编程
蚁群算法有一个主要缺陷,即搜索进行到一定程度后,各个蚂蚁趋于选择同一条路径,算法出现停滞现象。遗传算法局部搜索能力较差,在应用中体现出收敛速度慢且存在未成熟收敛。但这两种智能算法工作机理不同,有很强的互补性。两者融合,互相取长补短可以产生更好的效果。
当蚁群算法与遗传算法均采用二进制编码时,很容易实现混合编程。具体实现时,蚁群算法中蚂蚁个数与遗传算法中染色体个数取相等,每进行M次蚁群搜索循环后,将蚁群的二进制路径看做遗传算法中种群的染色体,进行N次遗传算法进化计算,然后再将得到的染色体作为蚁群二进制路径,继续进行蚁群算法搜索。
3 函数优化
3.1 函数优化及其求解
函数优化在工程技术领域应用很广泛。生产优化、设计优化、投资决策等可通过数学建模直接应用优化方法求解,参数识别、系统控制等问题则可转化为优化问题再进行求解。
函数优化的解法主要有两大类。其一为数学方法,即传统方法,主要利用导数及偏导进行求解,有可靠的理论基础。由于传统方法建立在梯度局部下降的基础上,多数情况下不适合求解全局优化问题,而且对于不可微和病态函数,常常无能为力[5]。
其二是进化算法,如遗传算法、蚁群算法、免疫算法、粒子群算法等,不需要计算梯度,计算过程对函数性态依赖性较小,适应范围广、鲁棒性好,适合计算机编程计算。近年来进化算法飞速发展,具有广阔的应用前景。
3.2 数学算例
由于蚁群算法及遗传算法程序运行中均存在大量的随机操作,从理论上对其性能和效率进行分析比较困难,因此这里通过一个测试函数对本文提出的蚁群-遗传混合算法进行多参数优化效率分析。
测试函数取一简单的多元平方求和函数,即求:
在函数定义域内其最优解为:当xi=2.0(i=1,2,3),xi=5.0(i=4,5)时,目标函数取最小值0。分别用蚁群算法、基本遗传算法、蚁群-遗传进行进化寻优计算。蚂蚁或染色体数目取40,最大进化代数取200代。
在开始计算前,蚁群算法中公式(1)~(4)中的参数α,β,γ,Δτ(i,j)等都预先赋给合适的经验值,本文各参数取值为:
α=1,β=0,τ0=50,q0=0.1,δ=0.1,r=0.05,Lgb=0.016
β=0意味着不考虑启发信息的作用,Lgb=0.016时意味公式(3)中Δτ(i,j)s=62.5,即进化计算过程中Δτ(i,j)s始终取一个恒定值。
遗传算法中的主要计算参数取:交叉概率Pc=0.8,变异概率Pm=0.02。
蚁群-遗传算法中取每进行6次蚁群搜索循环,进行4次遗传算法进化计算。
在这个多参数优化问题中,最优路径为对应目标函数值最小的蚂蚁行进路径。经过200代进化计算后,三种方法的函数优化结果如表1所示。
从表1可以看出,蚁群-遗传算法得到的识别结果比蚁群算法和基本遗传算法结果明显要好,单个变量的识别值与实际值更接近,最后得到的目标函数值也更小,说明采用蚁群-遗传算法混合编程求解效率与求解精度更高。算例还表明,混合算法可以很好地进行多参数优化求解,这可为求解实际工程技术问题打下良好的基础。
4 结论
运用蚁群-遗传算法混合编程进行优化设计,不仅具有较强的全局最优解搜索性能,还有较快的收敛速度和较高的求解精度,更适合解决多参数优化实际问题,具有广阔的应用前景。
参考文献
[1]DorigoO M.Optimization,learning,and natural algorithms[D].Milano:Politecnico di Milano,1992.
[2]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[3]Stutzle T.Parallelization Strategies for Ant System[C]//Proceedings of Parallel Problem Solving from Nature.Eileen A,Mchoenauer T B,Schwefel H.Lecture Notesin Computer Science.Berlin:Springer-Verlag,1998(1498):722-741.
[4]Gutjahr W J.A Graph-based Ant System and its convergence[J].Future Generation Computer Systems,2000(16):873-888.
蚁群优化算法及其理论进展 篇2
关键词:蚁群算法 离散域 连续域 收敛性
中图分类号:TP301.6文献标识码:A 文章编号:1674-098x(2012)04(a)-0032-02
1 引言
意大利学者Dorigo[1]等人根据真实蚂蚁觅食行为,提出了蚁群优化算法的(ACO)最早形式—蚂蚁系统(AS),并应用在TSP旅行商问题中。该算法采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性。AS算法提出之后,其应用范围逐渐广泛,已经由单一的TSP领域渗透到了多个应用领域[2],算法本身也不断完善和改进,形成了一系列改进ACO算法。
2 蚁群算法理论研究
2.1 基本蚂蚁算法
与真实蚂蚁觅食行为类似,基本蚁群算法主要包括路径选择和信息素更新两个步骤。以蚁群算法求解TSP问题为例[1]:TSP问题可表述成,旅行商走完n个城市有多种走法,每周游完所有城市可得长度为i的路径,它们构成解的集合
。而每个解是依次走过n个城市的路径距离构成的集合,可表示为。
设是在第g次周游中城市i上的蚂蚁数。在算法周游过程中,每只蚂蚁根据概率转换规则生成一个有n步过程的行动路线,整个算法的周游过程以g为刻度,。其中是预先设定的算法最大周游次数,当所有蚂蚁移动一次后,周游次数计数器加1。经过次周游,基本可找到一条最短路径。设,NP为算法中总蚂蚁数。
基本步骤为:算法开始时,每条路径上初始信息素设置为常数,并对每只蚂蚁设置随机起始城市。蚂蚁移动过程中,从城市i选择移动到城市j主要是根据概率启发公式(1)来完成,每次选择的城市都是从可选城市列表中取出。
(1)
其中为启发优先系数且。可以改变信息素与启发优先系数的相对重要性。如果则最近的城市容易被选择,这类似经典的随机贪婪算法。如果则只有信息素放大机制在独自工作,这将导致算法迅速收敛于一个可能是非最优的解。
为满足一只蚂蚁可以旅行n个不同城市,赋给每只蚂蚁一个数据结构,称禁忌表(tabu表)即tabu表与的集合为整个城市集合。tabu表存储本次周游中已经走过的城市,禁止本只蚂蚁在本次周游中再次访问已访问的城市。本周游结束后,tabu表置空,释放蚂蚁再次循环。假设是在g+1次周游时信息素值。
在基本蚂蚁算法中,通过应用信息素更新来提高蚂蚁构建解的质量,以全面提高算法性能。
(2)
而其中ρ是挥发系数,即信息素随着时间的推移是逐渐挥发的;是第k只蚂蚁在g到g+1次周游过程中放置在路径上的信息素增量。
2.2 改进蚂蚁算法
不可避免蚁群算法也有其明显的缺陷,测试结果证明,基本AS算法要次于其它已经存在的优化算法,如计算量较大,需要较长的搜索时间,易陷入局部最优解等。为此,许多学者开发了一系列改进ACO算法。
对AS较早的改进是EAS[3]算法,其对信息素的更新规则进行了改进,信息素更新形式为:
(3)
在EAS算法中,定义为用于更新的解的集合,由每代生成的解(称为)和目前找到的最好的解(称为)组成。为解Ψ的权值,当,解的权值定义为,只有解的权值比较大,为。称为品质函数,
。为解的集合Φ中的两个不同的解。
ACS算法[4]与原始AS有多方面不同:在时,ACS与AS的转化规则是一致的。当时,其转换规则就来源于与问题相关的知识。q是均匀分布在之间的随机变量,是一个可调参数;ACS算法把信息素更新分为全局更新和局部更新。全局更新仅应用中,ACS只更新属于最好路径的各条边的信息素值;在局部搜索中,每次构造解后,对信息素应用如下方式进行信息素更新。
。其中为常数,满足
。这种方法的优点是有利于发现更多的潜在最优解,从而提高算法的搜索质量。
MMAS算法[5]是ACO系列中最成功的改进之一,特征如下:算法开始时,通常多使用局部更新规则。算法运行时,更多使用全局更新规则。在MMAS中只有每次迭代后一只蚂蚁的信息素更新,这只蚂蚁可以是当前迭代中最好的解或截止当前的最好解解;为避免搜索停滞,对信息素设置一定的范围,初始信息素设置为,可以在开始时较快的搜索到较好解。
此外,一些学者针对基本蚁群算法在求解大规模旅行商问题进易陷入停滞的问题,提出一种基于信息熵调整的自适应蚁群算法。该算法通过优化过程中种群的信息熵来衡量演化的程度,自适应地调整路径选择策略和信息素更新策略[6]。随着人们对ACO研究的不断深入,Dorigo等人对各种版本的蚁群算法进行总结,提出了蚁群优化元启发式(ACO-MH)这一求解复杂问题的通用框架[7],ACO-MH为ACO的理论研究和算法设计提供了技术上的保障。
2.3 连续域内算法改进
在离散优化问题中,蚁群算法的信息量留存,增减和最优解的选取,都通过离散的点状分布方式进行的。因此,连续蚁群算法与离散蚁群算法至少应有信息量留存方式,蚁群在解空间中的寻优方式和行进策略等方面的不同。
Bilchev等最早将蚁群算法运用于连续优化问题,把整个搜索空间分成多个搜索域,使用遗传算法对解空间进行全局搜索,并利用蚁群算法对所得结果进行局部搜索。但是算法在运行过程中出现蚂蚁对同一个区域进行多次搜索的情况,算法效率较低。倪世宏等[8]在实现了连续蚁群算法的基础上,针对容易陷入局部最优解的问题,对连续蚁群算法的全局转移概率进行改进,提出一种动态蚁群算法,根据动态全局转移概率分配蚂蚁个数,进行不同阶段的搜索。但在如何将蚁群优化思想有效地应用到连续空间优化中还没有形成一致的看法。许多算法就结果的鲁棒性、算法的推广性来说,都有待进一步验证。
3 收敛性研究
蚁群算法理论发展的“瓶颈”问题之一是算法的收敛性,研究算法的收敛性不仅可以深入理解算法机理,还可以对改进算法、编写算法程序有重要意义。
在ACO的收敛性方面,Gutjahr作了开创性的上作,提出了基于图的蚂蚁系统元启发式模型,证明了改进算法可与模拟退火算法获得相似的结果,该模型在一定的条件下能以任意接近1的概率收敛到最优解。Stützle等对一类ACO算法的收敛性进行了证明,其结论可直接用到实验证明最成功的两个ACO算法—MMAS和ACS上。
4 结语
自蚁群算法创立以来,已有十多年的发展历程,其良好的寻优性能越来越受到人们的关注。目前对算法的研究己由解决一维离散优化问题发展到多维离散优化问题,由离散域拓展到连续域研究。蚁群算法作为一类用于解决优化问题的随机搜索过程。其收敛性研究依然是今后一个非常重要的研究方向,这对深入理解算法机理,改进蚁群算法具有重要意义。此外,蚁群算法同其它仿生学智能算法的融合目前也有了一定的研究成果,这也将是蚁群算法的发展方向之一。
参考文献
[1] Colorni A,Dorigo M,Manlezzo V．Distributed optimization by ant colonies [C]∥Proceedings-European Conference on Artificial Life,ECAL1991． Paris:Elsevier Publishing,1991:134～142．
[2] 張晋,曹耀钦.基于混合遗传蚁群算法的多Agent动态任务分配研究[J]．计算机科学,2011,38(10):268～270.
[3] Dorigo M．Optimization, learning and natural algorithms [D]． PhD thesis, Dipartimento di Elettronica, Politecnico di Milano,Italy,1992．
[4] Dorigo M,Gambardella LM．Ant colony system:a cooperative learning approach to the traveling salesman problem [J]．IEEE Transactions on Evolutionary Computation,1997,1(1):53～66．
[5] Stützle T,Hoos HH．MAX-MIN ant system[J]．Future Generation Computer Systems Journal．2000,16(8):889～914．
[6] 肖菁,李亮平．基于信息熵调整的自适应蚁群算法[J]．计算机工程与设计,2010,(22):4873～4876．
[7] Dorigo M, Caro GD, Gambardella LM．Ant algorithms for discrete optimization [J]．Artificial Life, 1999,5(2):137～172．
[8] 倪世宏 秦军立 苏晨．一种求解连续空间优化问题的动态蚁群算法[J]．电光与控制,2009,16(12):12～14．
混合蚁群算法 篇3
网格资源调度技术是根据任务的信息和各资源节点的状态、网络通信性能等参数, 采用适当的匹配策略把不同的任务分配到相应资源节点上运行, 是网格系统中间层的核心功能之一[1]。研究网格资源调度技术的重点是对网格资源调度算法的研究。一个优良的调度算法可以使网格节点执行更多的任务, 增大网格系统的吞吐率, 并能尽量使整个网格环境保持负载均衡。
蚁群算法来源于对自然界蚂蚁寻找从蚁巢到食物的最短路径并找到回巢路径方法的研究, 它以信息素为媒介, 通过群体智能间接散布最优解信息, 采用逐步收敛的方式求解最优解, 主要用于解决诸如TSP问题 (Traveling Saleman Problem) , JSSP问题 (Job Shopping Scheduling Problem) , GCP问题 (Graph Coloring Problem) 等组合优化问题[2]。网格资源调度问题本质上是从资源分配给作业的多种组合中选择性价比最高的一种组合方式, 也属于组合优化问题, 因此蚁群算法非常适合解决资源调度问题[3]。然而笔者发现蚁群算法在应用到网格资源调度中时通常需要耗费一定的时间进行多次迭代才能建立起较好的调度方案。为了较快建立调度方案, 加快算法收敛速度, 本文提出在蚁群算法中加入局部搜索算法, 并以此混合蚁群算法为核心建立起网格资源调度模型。
为了解决上述问题, 本文将禁忌搜索算法作为蚁群算法局部搜索策略[4], 以扩大算法的搜索空间, 使蚁群算法能够跳出局部最优, 提高算法的收敛速度。
2 基于混合蚁群算法的网格资源调度模型
在网格调度模型中, 我们设定模拟的调度器为蚂蚁, 一个完整的任务调度方案相当于TSP问题中的一条路径, 任务—处理器对则相当于城市节点。基于混合蚁群算法的调度模型在每只蚂蚁建立了一个完整的调度方案后并不急于用这些调度方案来更新信息素, 而是对每只蚂蚁的调度方案进行适应度评价并选择最后方案, 接下来在这个最优方案的邻域内进行局部寻优, 找到局部最优方案, 再用此局部最优方案来更新信息素, 这样做就极大的减少了蚂蚁寻优的迭代次数。本文构造的用于网格任务调度的混合蚁群算法总体框架如图1所示。
2.1 调度方案建立 (Establishing scheduling scheme)
蚂蚁建立调度方案主要依据两方面的重要信息, 一是信息素信息, 二是启发信息。
我们把信息素定义为把任务i调度到处理器j上的期望程度, 并建立了一个信息素矩阵来存储信息。初始阶段, 在没有任何信息的前提下, 我们对任意τ (i, j) 取相同的值。τ (i, j) 表示把任务i调度到处理器j上的信息素值。
启发信息在本文的网格调度模型中表示启发蚂蚁将任务调度到某一处理器的能见度, 即“诱惑”蚂蚁将任务调度到某一处理器的力量的大小。我们借鉴Min-Min算法中对启发因子的设计[5]:MinMin算法的启发因子值与任务的最小完成时间MCT (j, pjbest) 成比例, MCT (j, pjbest) 表示任务j在相对于该任务最优的处理器上pbest的期望完成时间, 表达式如式 (1) 所示,
式中, t (pi) 表示当前处理器pi的总运行时间, ETC (j, pi) 是ETC (Expected Time to Compute) 矩阵中的一个值, 表示任务j在处理器pi上的期望执行时间。构造启发因子如下:
η (j) 表示最优处理器对任务j的启发信息值。在蚂蚁进行下一任务调度计算转移概率时需要计算所有任务的η (j) , 启发信息在蚂蚁转移过程中不断更新。
在确立了蚁群算法的相关规则后, 我们就可以来设计蚁群建立调度方案的过程。蚂蚁 (模拟的调度器) 依据概率公式 (3) 将任务j调度到处理器pjbest。
在此式中, α表示信息素的权重, β表示启发信息的权重。若有n个任务, 则要经历n步调度迭代, 迭代过程中, 需要建立一个存储已调度任务及处理该任务的处理器信息的禁忌表, 这样在下一步调度时, 禁忌表中的任务将不再调度, 当所有任务都进入这个禁忌表时, 一个完整的调度方案就建立了, 读取禁忌表就能得到一个完整的调度方案。当所有蚂蚁都建立了完整的调度方案该蚁群就完成了一次迭代。在蚁群开始下一次迭代前, 清空禁忌表。
2.2 适应度评价 (Fitness evaluation)
全局的适应度函数用来评价蚂蚁建立的调度方案的优劣。在评价调度方案优劣的时候, 跨度是一个非常重要的衡量指标。跨度越小, 表明系统的吞吐率大, 任务执行快。我们设计适应度函数如下:
其中, f (s) 表示在调度方案s下系统的吞吐率, ms (s) 表示调度方案的跨度, 也即最后一个任务的完成时间, 其表达式如式 (5) 。
2.3 局部搜索最优方案 (Searching optimization pro-gram locally)
在蚁群完成一次迭代后, 用适应度函数评价此次迭代的所有调度方案并得出最优调度方案sbest, 在由sbest和它的邻域N构成的解空间内进行局部搜索, 找到这个解空间的最优调度方案s'best, 再用s'best更新信息素。这种方案没有通过蚂蚁的大量的迭代得到较优解, 大大降低了算法收敛的时间代价。
2.4 信息素更新 (Pheromone update)
我们参照Stutzle&Hoos对最大—最小蚂蚁系统[5]的研究, 采取精英策略[5]和最大—最小蚂蚁策略作为本调度模型的信息素更新策略。信息素更新方式和过程如下:
本文用sbest来表示最优蚂蚁解, sib代表蚁群第i次迭代的最优蚂蚁解, sgb代表从实验开始到现在全局最优蚂蚁解, 信息素更新的表达式如式 (6) 所示,
γ用来控制信息素更新的强度, 增加的值将使得搜索速度和算法收敛的速度降低, 但可以激励蚂蚁在更大的解空间搜索, 有利于发现更优的解, γ越小, 收敛速度越快。参数ρ表示信息素挥发的程度, ρ的值也能影响收敛速度和寻找最优解, 我们可以根据实际需要调整γ和ρ的值, 平衡收敛速度和寻找最优解, 本文都采用参数的经验值:γ=1, ρ=0.7。
综合上面的分析可以看出, 信息素的更新就是要强化最优路径的信息素和弱化非最优路径的信息素, 这样有利于蚂蚁朝最优解方向搜索。在蚁群完成一次迭代后, 根据上述信息素更新方式来更新信息素, 所有蚂蚁的启发信息都回到初始状态, 清空禁忌表, 开始新一次迭代。
3 仿真实验及分析
本实验以经典的Min-Min算法和Max-Min算法作为参照测试混合蚁群算法的性能, 在Eclipse中编程实现并调试运行。实验中, 系统随机构造m个任务, n个计算资源 (都为单CPU, 计算速率统一) 。为了避免参数对蚁群算法性能的影响, 本文都采用参数的经验值:蚁群规模10, α=β=1, ρ=0.7。
仿真实验一:系统随机产生7个作业和5个资源, 在创建资源时, 初始化各资源节点的带宽相等并且各个资源节点的任务队列为空。表1是7个作业和5个资源的ECT (期望执行时间) 矩阵,
以上表为实验数据, 得出Min-Min算法、Max-Min算法和混合蚁群算法最优调度方案如表2所示:
负载均衡是评价网格调度算法性能的一个重要指标, 负载均衡值越小说明网格系统的负载均衡越好。负载均衡值的计算公式如式 (7) 所示:
其中ct (pi) 表示处理器执行任务的总时间, 表示执行任务总时间最长的处理器的任务执行总时间, 而表示执行任务总时间最短的处理器的任务执行总时间, n表示处理器的个数。最后综合运行结果和负载均衡的计算结果得出最终统计结果如表3。
从表3可以看出, 以评价网格任务调度算法性能最重要的两个指标最优跨度和负载均衡来衡量, 最优的调度结果是混合蚁群算法得出的调度方案, 最优跨度值为7.0, 最优负载均衡是0.34。
仿真实验二:为了增强实验结果的说服力, 笔者用更多的实验和更大规模的数据来比较算法的性能。这一步将进行一系列的实验, 处理器数量固定为5, 任务数以20递增。最后的实验结果统计如表4。
从实验二的结果可知, 当处理器数量不变, 任务数量变化时, 混合蚁群算法无论在跨度还是负载均衡方面都表现出比Min-Min算法和Max-Min算法更好的性能, 这种优势随着任务总数的增加而更加明显。
仿真实验三:此次实验固定任务数为200, 处理器数量以5递增。最后的实验结果统计如表5。
从实验三的结果可知:任务总数不变, 处理器数目越多, 任务总执行时间会逐渐减少;无论处理器数量多少, 混合蚁群算法都表现出了比Max-Min算法和Min-Min算法更好的性能, 这种优势在处理器数目更小的时候体现得更加显著。
4 结论
通过以上实验测试及对结果的统计分析, 我们可以看出本文构造的混合蚁群算法及以此为核心的网格任务调度模型是有效的, 其有效性主要体现在以下两个方面:1.调度跨度和负载均衡是评价网格任务调度算法性能两个最重要指标, 混合蚁群算法在这两个指标上的表现都比经典的Min-Min算法和Max-Min算法要好;2.混合蚁群算法比基本蚁群算法的收敛速度要快和性能更好。在程序运行中我们发现混合蚁群算法找到最优解的收敛速度比Min-Min算法和Max-Min算法要慢, 但是程序运行时间相对于真实的任务执行时间来说, 比例很小甚至可以忽略不计, 混合蚁群算法通常能在蚁群迭代的前几次就能得出Min-Min算法能够得出的满意解, 甚至更优;并且通过实验证实混合蚁群算法在跨度和负载均衡方面都表现出比Min-Min算法和MaxMin算法更好的性能, 因此基于混合蚁群算法的网格调度模型具有良好的性能, 可以有效地解决网格资源调度问题。
参考文献
[1]CHENG K W, YANG C T, LAI C L, et al.A parallel loop selfscheduling on grid computing environments[C].Proc.of 7th International Symposium on Parallel Architectures, Algorithms and Networks, Hong Kong, 2004:409-414
[2]XU Z H, HOU X D, SUN J Z.Ant algorithm-based task scheduling in grid computing[C].Proc.of 2003-Canadian Conf on Electrical and Computer Engineering, Canada, 2003, 2:1107-1110
[3]王天擎, 谢军, 曾洲.基于蚁群算法的网格资源调度策略研究[J].计算机工程与设计, 2007, 28 (15) :3611-3612
[4]HO S L, YANG SHIYOU, NI GUANGZHENG, et al.A Modified Ant Colony Optimization Algorithm Modeled on Tabu-search Methods[J].IEEE Transactions on Magnetics, 2006, 42 (4) :1195-1198
[5]CASANOVA H, LEGRAND A, D ZAGORODNOV, et al.Heuristics for scheduling parameter sweep applications in grid environments[C].Proc.of 9th Heterogeneous Computing Workshop (HCW) , Cancun, Mexico, 2000:349-363
蚁群算法在客户关系管理中的应用 篇4
[关键词] 蚁群算法聚类分析客户关系管理
一、引言
迅速发展的Internet，使世界经济进入前所未有的高速增长期。随着网络技术的进步和成熟，网络经济和电子商务越来越深入人心、飞速发展，在全球范围内正加速改变着传统商业模式。如今，网上客户只需轻动鼠标，就可使买方购物链重构，会让卖方供应商重组。成为客户社会作用放大器的网络经济和电子商务，已使客户拥有在传统商务时代所无法比拟的自主权、自由度、自选域与影响力。因此，处在“网络经济新时代”的今天，企业界特别是IT界原来习惯的“只使现行流程实现数据处理自动化，就可使企业拥有商业优势”的传统观念已经过时，卖方管理者必须具备与网际竞争相匹配的全新思维，一定要挣脱束缚、改变视角、弃旧创新，高度重视管理、分析、研究和利用客户关系，灵活应对客户需求流的变化及发展，提高客户资源利用率与商品营销竞争力。这对企业界特别IT界与时俱进有重要意义。
二、客户关系管理（CRM）
“客户”，在全球网际卖方竞争中，已升级为如今买方市场激烈竞争下企业兴衰成败的关键。许多商业调查和行业分析家证实：客户的满意度和忠诚度将直接影响企业的销售和成本。一个非常满意的客户其购买意愿，将六倍于一个满意的客户；而2/3的客户离开其供应商，是因为它对客户关怀不够。
“客户关系管理”，并不单纯是一种计算机软件技术，而是一种以计算机为基本工具的、但更注重“建立、改善和发展客户关系”的商业战略、企业理念、经营手段。客户关系管理，旨在使以客户为中心的企业业务流程不仅要实现自动化，而且要使之具有随机应变、随需而变的动态重组能力。
客户关系管理，以“广泛收集、科学分析、积极建立、快速反馈、有效维系、逐步扩大、合理利用厂商的客户信息资源”为己任，是当今厂商取得电子商务网际竞争优势的最重要基础和最有效法宝。CRM使企业提升客户资源价值的主要手段主要如下:
1.分类管理客户资源，重点关注核心客户。
2.随时跟踪客户变化，动态管理客户需求。
3.以人为本关爱客户，定期沟通双向交流。
4.全方位化关注客户，延伸拓展客户服务。
三、蚁群算法在CRM中的应用
“K—中心”算法，是传统聚类分析的主用算法。然而，随着“海量客户数据”的出现与“模式样本、客户分类”的数量很大时，这种算法效率锐减、逐渐失效。
蚁群算法，是由意大利学者M.Dorigo等人首先提出。它借用蚁群在搜索食物源的过程中所体现出的寻优能力，来解决一些颇为困难的寻求离散系统的优化解或满意解的问题。已经用该办法解决了旅行商问题、指派问题、调度问题等，取得了很好的结果。初步的研究表明，蚁群算法是一种基于种群行为特性的鲁棒性较强的算法，具有很多优良的性质。
1.蚁群算法概述。蚂蚁觅食时，对于从蚁窝到食物源的诸多途径，开始时不同的蚂蚁会选择不同的路径，但最后，几乎所有的蚂蚁都会找到同一条最短的路径。这是因为蚂蚁寻找最短路径的过程，是一个非常有趣、十分合理的交互式过程：每个蚂蚁都会在所经过的路上留下一定量的外激素(pheromone)，且能感知这种外激素的存在及强度，并有“朝外激素强度高的方向运动”的本能。这些外激素，既会随所通过蚂蚁数量的增加而增加，也会随时间的流逝而按一定的衰减函数关系而消退（即：减退→淡化→消逝）。这样，整个蚁群的集体行为便表现出一种信息正反馈现象；某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。显然，最短路径上所通过蚂蚁的数量会按“较少→较多→最多”方式进行演进，使最短路径上所散布的外激素总比其他路径浓得多（因为其路上的外激素积累速度比消退速度大得多）；蚁群则通过感知、交流和反馈外激素强度信息，并受高强度外激素的制导——“不断调整自己觅食行进方向，动态集聚于外激素浓度高的路径上”；从而，蚁群最终找到一条从蚁窝到食物源的最佳（即最短）路径。受自然蚂蚁系统及其行为机理的启迪，人们创造出人工蚂蚁（AA）、人工蚁群系统（ACS）以及蚁群算法（ACA）。人工蚂蚁，类似于真实蚂蚁，它在运动中会释放出一定的行为特征信息，能感知该行为特征信息的存在及其强度，并按“向高强度特征信息集聚”的原则制导人工蚂蚁的行为。
2.蚁群聚类算法。蚁群算法的聚类处理，其主要思想是：在基于蚁群算法的聚类分析中，把“数据”视为具有不同属性的“人工蚂蚁”，把“聚类中心”看作是这些蚂蚁所要寻找的“食物源”；而把数据聚类过程，看作是人工蚂蚁寻找食物源的过程。显然，最后数据将会在“食物源”中聚集，从而达到对数据的自然聚类——正确分类。
为了叙述简便，可给出如下约定：设聚类集合，加权欧氏距离。在客户关系管理中，各个指标的贡献往往不同，应设定加权因子来反映这种变化。r0为初始聚类距离阀值。
(1)由于传统的蚁群算法对初始聚类中心的选择，没有统一的一致方法。本文采用如下方法选择初始聚类中心：
首先，如果聚类中心的距离小于r0，则重新选择聚类中心，这样能加快收敛速度。m为初始聚类个数，为统计误差，为数据到聚类中心路径上残留的外激素。第i个数据选择第j个聚类中心的概率为：
其中为强度的持久性系数，一般取0.5～0.9左右，Q为正常数。
然后，新聚类中心的确定方法，可采用K-均值法:，其中表示所有在此类中的数据。（注：新的聚类中心可能不在样本集中）
(2)蚁群聚类ＣＲＭ算法，可概述如下：
①初始化：设定r0(初始聚类半径)，r1(最后确定分类的聚类半径)，(误差),Q,。
②任意选择K个中心Cj，确定K个聚类（采用基于欧氏距离的最邻近法则聚类）。如果聚类中心之间的距离小于r，则重新选择聚类中心。给每个信息素变量赋予相同的数值。
③计算转移概率（第i個蚂蚁选择第j个聚类中心的概率）：
④对每个蚂蚁按转移概率选择聚类中心。
⑤计算各点到聚类中心的距离：
⑥更新信息素：
⑦计算新的聚类中心（K-均值法）：
⑧计算第i个聚类的偏离误差：
⑨计算总体偏离误差：
⑩如果成立，就看聚类中心的距离是否小于r1：若小于就可构成一类，然后输出聚类结果。不然，就转“第4）步”。
在此算法中，为了减少蚁群算法迭代次数，本文特提出一种动态自适应调整改进方法，并对聚类中心的距离进行了一定限制，从而对于输出理想的聚类个数有一定帮助。不过，笔者认为：这还不是很理想的聚类个数优化确定方法，有待进一步的优化研究。
四、结论
企业的竞争重点，正在经历着从以产品为中心向以客户为中心的转移，客户关系管理作为一种全新的管理、经营理念，越来越引起商家的重视。在数据仓库中进行数据挖掘正逐渐成为CRM中最核心的部分。用蚁群数据挖掘聚类算法解决CRM的客户聚类分析问题，是可行的。这在支持企业决策方面有着极为重要的理论参考价值和实际应用意义，可以帮助高层管理者更好地管理企业，使企业得到更好的顺利发展。
混合蚁群算法 篇5
关键词：作业车间调度,蚂蚁算法,遗传算法
2009年2月23日收到 国家自然科学基金(70572098)资助车间调度问题(Job shop Scheduling Problem, JSP) 是一种资源分配问题。这里的资源主要是指设备资源[1], 问题的求解目标是要找到一个将一组工件安排到设备上去, 以使作业可为“最优”完成的方案。一个调度是按先后顺序条件将所有任务安排到设备上的一种方案。通常, 约束的数目很大, 使JSP成为一个非常难解的组合问题(N P完全问题)。车间调度作为CIMS体系结构中连接生产计划和生产控制层的中间环节, 发挥两方面的重要作用: 一方面接受计划决策信息, 在空间和时间上合理配置任务和资源, 形成具体生产实施方案,驱动整个生产系统高效运作, 保证计划的实现; 另一方面, 接受生产过程的实际信息, 通过统计分析, 有机协调整个生产系统, 并向决策层反馈计划执行情况。
1 车间作业调度的问题描述
经典车间调度问题可以描述为: n个不同的工件要在m台不同机器上加工, 每个工件需要经过m道工序, 每道工序要求不同的机器, 并且已知各个操作的加工时间和各工件在机器上的加工次序约束, 问题的目标是确定各个工件在各台机器上的加工顺序和开始、结束时间, 使优化目标最优。在这里的优化目标是使该批工件的加工时间(Markspan)最短。其中约束条件包括:(1)工件约束条件:对每个工件而言,机器对它的加工路线是事先确定的;(2)机器约束条件:对每台机器而言,一次只能对一道工序进行加工。
2 算法在车间作业调度的应用
蚁群算法是模拟真实蚁群觅食过程寻求最短路经的原理,由意大利学者M Dorigo等人首先提出的[2]。最初的蚁群算法称为蚂蚁系统(ant system),对于解决旅行商问题(TSP)及二次分配问题取得了较好的效果。经过改进后称为蚁群算法。蚁群算法吸收了蚂蚁群体行为的典型特征:
(1) 能察觉小范围区域内状况,并判断是否有食物或其他同类的信息素轨迹;
(2) 能释放自己的信息素;
(3) 所留得信息素数量会随时间而逐步减少。
自然界中的蚂蚁是以外激素(pheromone)为媒介进行信息传递的,从而蚂蚁个体能相互协作,完成复杂的任务。蚂蚁在行动中,会在它们经过的地方留下外激素。同一蚁群中后到的蚂蚁能够感知到这些外激素的存在及其强度,并以此来指引自己的行动方向,具体表现在选择外激素强度大的路径的概率要高些。这样,后到的蚂蚁同样留下外激素,对原有的外激素进行加强,如此循环下去。蚁群的行为便表现出一种信息正反馈现象:某一路径上经过的蚂蚁越多,则后到者选择该路径的概率就越大。
蚁群算法具有如下优点:(1) 较强的鲁棒性,对基本蚁群算法可以应用于解决很多问题;(2) 分布式计算,蚁群算法是一种基于种群的进化算法,具有真正的并行性,易于实现并行;(3) 易于与其它算法相结合,蚁群算法很容易与多种启发式算法结合,以改善算法的性能。众多研究已经证明蚁群算法具有很强的发现较优解的能力,这是因为该算法不仅利用了正反馈原理在一定程度上可以加快进化过程,而且是一种本质并行的算法,不同个体之间不断进行信息交流和传递,从而能够相互协作,有利于发现较好解。
基本蚁群算法的主要缺点是:第一,算法开始时,信息素的作用不明显,主要是因为各条路径上的信息素分配差异不明显,要经过较长的一段时间,较好路径上的信息素优势才会明显起来,从而会最终收敛于较好的路径,可见算法初期浪费了较长时间;第二,正反馈机制虽然能强化较好解,但却使算法出现停滞现象,即只取得了局部最优解就停止,而未达到全局最优解。针对上述基本蚁群算法的缺点,需要改进的是围绕选择概率模型和信息素更新规则的设计。其中既包括对纯粹的蚁群算法的改进,也包括引入其它优化算法对蚁群算法的性能进行提高。
遗传算法[3]类似于自然进化,通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始群体:通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加遗传操作,经过遗传操作后的个体集合形成下一代新的种群,对这个新种群进行下一轮进化,这就是遗传算法的基本原理。遗传算法基本步骤:
(1) 初始化群体;
(2) 计算群体上每个个体的适应度值;
(3) 技由个体适应度值所决定的某个规则选择将进入下一代的个体;
(4) 按概率pc进行交叉操作;
(5) 按概率pm进行突变操作;
(6) 没有满足某种停止条件,则转第(2)步,否则进入(7)。
(7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。
3 算法混合思想的研究分析
遗传算法具有大范围快速全局搜索能力,但对系统中的反馈信息利用不够,当求解到一定范围时往往做大量无用的冗余迭代,求精确解效率低。蚁群算法原理是一种正反馈机制,但初期信息素匮乏,求解速度慢。将遗传算法与蚂蚁算法的融合[4,5],采用遗传算法生成信息素分布,利用蚂蚁算法求精确解,优势互补,期望获得优化性能和时间性能的双赢。将遗传算法与蚁群算法的混合来解决作业车间调度问题,不仅仅采用遗传算法生成初始信息素分布,在蚂蚁算法寻优中,采用交叉和变异的策略,改善解的质量。
混合的思路是首先由遗传算法产生较优解,较优的路径留下信息素,其他不改变;然后让蚂蚁按照蚁群算法,完成一次遍历后,再让蚂蚁作遗传算法的交叉操作和变异操作,有可能经过交叉操作和变异操作的解不一定得到改善,只有改变蚂蚁的路径,代替原来的路径,才能使解得到改善。
另外这里作如下改进,蚂蚁每次周游结束后,不论蚂蚁搜索到的解如何,都将赋予相应的信息增量,比较差的解也将留下信息素,这样就干扰后续的蚂蚁进行寻优,造成大量的无效的搜索。改进的方法是,只有比较好的解才留下信息素,即只有当路径长度小于给定的值才留下信息素.为了充分利用各蚂蚁所走过的路径信息,随时记录当前的最好解.也采用MAX-MIN Ant System技术[6],即路径上的信息素浓度被限制在[τmin,τmax]范围内。
变异策略:在第1～n个工件中随机地选取第ji次工件,在路径C0中交换第ji次和第ji+1次工件,其余不变,此时的路径为C1。比如C0=2 3 4 1 5 7 9 8 6,j1=2,则C1=2 4 3 1 5 7 9 8 6 。交叉策略:在第二个串中随机选择一个交叉区域;将old2的交叉区域加到old1对应的位置,删除old1中已在old2的交叉区中出现过的工件。例如两父为:old1=1 2 3 4 5 6 7 8 9,old1=9 8 7[3,4,5,6]2 1,若交叉区域为:6 5 4 3,交叉后为:new1=1 2 6 5 4 3 7 8 9。
解JSP问题的遗传蚁群算法如下:
步骤 1 利用遗传产生一个较优解,在这个路径留下信息素;
步骤 2 nc=0,(nc为迭代步数或搜索次数),将m个蚂蚁置于n个顶点上;
步骤 3 将各蚂蚁的初始出发点置于当前解集中,对每个蚂蚁k(k=1,2,…,m),按概率p
步骤 4 根据交叉概率,选择若干组解,然后分组进行交叉的解,若新的目函数变好,接受新值,否则就拒绝;
步骤 5 根据变异概率,判断是否变异,变异后的目标函数变好,接受新值,否则就拒绝;
步骤 6 计算各蚂蚁的路径长度Lk(k=1,2,…,m),记录当前的最好解;
步骤 7 对路径长度Lk小于给定值的路径,按更新方程修改轨迹强度;
更新方程:
E为此次分配全部目标的失败概率,ρ表示强度的持久性系数,一般取0.5一0.9左右,Q为一正常数。
步骤 8 nc=nc+1;
步骤 9 若nc<预定的迭代次数且无退化行为(即找到的都是相同解)则转步骤2;
步骤 10 输出目前最好解。
4 调度问题的混合算法仿真结果
鉴于JSP的重要性和代表性,许多研究工作者设计了若干典型问题,用以测试和比较不同方法的优化性能。对于上述算法,一基准问题Muth&Thompson的6×6基准问题为例,参数:α=1.5,β=2,ρ=0.9,染色体个数N=30,pc=0.2,pm=0.5。表1将实验结果与传统的ACO算法进行比较,验证算法的可行性。
经过研究JobK-p调度问题的模型,提出了混合蚁群算法来求解该问题及其实现方法。通过方针、比较、该算法具有较好的收敛性和求解能力。
5 结束语
针对车间作业问题,基于混合算法的思想,利用蚁群算法和遗传算法特性,提出混合算法吸收了两种算法的优点,可以显著提高计算效率。该算法采用遗传算法生成初始信息素分布,在蚂蚁算法寻优中,采用交叉和变异的策略,改善解的质量。从实例仿真可以看出,试验结果的平均运行时间优于蚁群算法,这使混合算法能够更好的求解车间作业调度问题。试验证实了混合算法是可行有效的。
参考文献
[1]刘土新,王梦光,唐加福.资源受限工程调度问题优化方法综述.控制与决策,2001;16:647—651
[2]Colorni A,Dorigo M,Maniezo V.Distributed optimization by ant col-onies.Proc of lst European Conf.Artificial Life,Pans,France:Elsevier,1991:134—42
[3]丁建立,陈增强,袁著扯.遗传算法与蚂蚁算法的融合.计算机研究与发展,2003;40(9):1351—356
[4]丁建立,陈增强,袁著扯.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析.自动化学报,2004;30(4):629—634
[5]王凌.智能优化算法及其应用.北京:清华大学出版社,2001:17—59
混合蚁群算法 篇6
美国J.Holland教授及团队在1970年代建立发展了遗传算法,它是通过潜在解种群进行搜索,采用概率转移来选择个体,创造新后代,适合数值求解有些带有多数、多变量的NP难题,但过早收敛和搜索效率低等问题。根据蚁群觅食的群体行为,意大利学者Dorigo M等于1991年在法国巴黎召开的第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型;1992年Dorigo M在其博士学位论文中进一步阐述了蚁群算法的核心思想。由于具有较强的群体搜索能力,蚁群算法被运用于求解各种组合优化问题。但研究结果表明在计算过程中有时会陷入局部最小,使整个系统呈现出早熟现象。于是我们构造了遗传算法和蚁群算法相结合的混合蚁群算法为求解物流配送路径优化问题提供了有效的工具。
1 蚁群算法原理和模型
1.1 蚁群算法原理
蚂蚁寻觅食物的过程中,从蚂蚁巢窝启程寻觅食物源,刚开始的时候其路径选择是随机的,但后来路径选择会随着寻觅食物过程的继续而适应性地搜索新的路径。原因主要是蚂蚁在运动过程中,在途径的路径上释放信息素的物质,路径上的信息量随着时间流逝而逐渐消减,信息素物质与路径长度有关,路径越短分泌的信息素越大;如若某一条路径上经过蚂蚁越多,其留下的信息素浓度越强,信息素浓度越强就会吸引更多的蚂蚁从此路径过,这样形成正反馈效应。如此蚂蚁在寻觅食物的过程中就形成一个较优的寻觅食物路径。受蚂蚁寻觅食物路径发现行为的启发,1992年Marco Dorigo在其博士论文中阐述了蚁群算法,并且对其数学模型做了分析、解释。
1.2 蚁群算法模型
2 物流配送路径优化问题的数学模型
各个顾客点需求量和位置及各车辆的装载量已知,按要求用多个车辆对多个顾客需求进行配给货物,寻求好的配送方案,使得总代价最小即我们说的物流配送路径优化。它需要满足:物流配送中心车型、位置唯一且已经;每辆车出发点和任务终止点都是配送中心;每条配送路径上各需求点的总需求量不得超过该车辆的载重量;每条配送路径的长度不得超过配送车辆一次配送的最大行驶距离;每个需求点需求被满足且只能由一辆车送货。
假设有n个客户需配送中心送货,每个客户需求货物量是gi,每辆车载重量为q,数学模型为:
则
上述模型,m代表所需车辆数;Cij为从点i到点j的运输成本,它包括距离、时间、费用等,可以根据情况,并同时考虑车辆数及运行费用,式(1)是目标函数;式(2)是汽车容量约束;式(3)确保每客户的运输任务由仅有一辆车完成;式(4)和式(5)为到达和离开某一客户的车仅为一辆。
3 物流配送路径优化问题的混合蚁群算法
混合蚁群算法主要思想是将蚁群算法和遗传算法结合起来。因为蚁群算法和遗传算法具有很多类似的特性,蚁群算法和遗传算法都是模拟生物进化的方法,蚁群算法是利用群体智能来搜寻最优解,而遗传算法是利用种群进化来搜寻最优解。蚁群算法具有正反馈和建设性的“贪婪”启发式特性,而遗传算法具有全局收敛性。
物流配送路径中选择混合蚁群算法,省去了蚁群算法一开始寻找最优解的过程,而且遗传算法寻找较优解的速度快,这两种算法的融合,在时间效率上得到了提高。
混合蚁群算法对优化问题首先采用蚁群算法获得一组局部极小值Xk,再采用遗传算法对其进行变异成Xp,然后采用蚁群算法在X邻域内寻优。具体算法如下:
4 实例仿真
根据物流配送路径优化问题的混合蚁群算法,本人利用Matlab2012进行编程,计算实例结果进行分析比较。
实例:某配送中心有载容量8t的2辆配送车,各客户的需求量为di(i=1,…,8)(单位为t),各客户与配送中心距离如表1所示:
运用本文提供的混合蚁群算法对其问题求解,参数设置α=2,β=4,ρ=0.85。利用编程工具Matlab2012获得的物流路径为:0→4→7→6→0,0→1→3→5→8→2→0,随机求解8次,得到结果如表2所示。
利用蚁群算法得运输总距离为159km,线路为0→6→5→7→3→0,0→4→8→2→1→0;遗传算法可得总运输距离143km;然而从表2可得其运输总距离为135km,可见利用混合蚁群算法求得的距离较优,此方案满足所规定的约束条件,是所陈述的车辆路径问题的可行解。
5 结束语
本文用混合蚁群算法完成了物流配送车辆路径问题方面的求解。本课题的研究对物流配送路径具有优化作用,节约物流运送成本,提升企业竞争力。从仿真实例来看,该算法的优化质量和效率都优于遗传算法和蚁群算法,增强寻优能力,提高了运算速度,避免算法造成停滞现象,具有较好搜寻全局最优解的能力。
参考文献
[1]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006(1):119-121.
[2]于文莉.基于混合蚁群算法的物流配送路径优化问题的研究[J].商场现代化,2007(10):137-138.
[3]陈卫东,王佳.基于混合蚁群算法的物流配送路径优化[J].计算机工程与设计,2009(14):3383-3385.
[4]李卓君.混合蚁群算法求解物流配送路径问题[J].武汉理工大学学报(交通科学与工程版),2006(2):306-309.
[5]雷德明,吴智铭.基于粒子群优化的多目标作业车间调度[J].上海交通大学学报,2007,41(11):1796-1800.
[6]张潇,王江晴.混合蚁群算法在车辆路径问题中的应用[J].计算机工程,2011(12):190-192.
[7]Colorni A.,Dorigo M.,Maniezzo V.,et al.Distributed optimization by ant colonies[C]//Proceedings of the1st European Con-ference on Artificial Life,Paris,1991:134-142.
混合蚁群算法 篇7
关键词：智能交通系统,蚁群算法,混合蛙跳算法,最优路径
1 引言
随着社会经济的快速增长和城市交通的飞速发展,路径优化已成为城市交通诱导系统中的热点研究领域,也是智能交通系统中最为人们所期盼的目标功能之一,其主要作用是基于城市路网信息及实时道路交通状况信息, 实现对用户出行前及出行中的路径规划功能, 引导车辆在交通网络中顺利地到达目的地且耗费总和最优,实现车辆实时诱导, 进而实现改善城市交通和避免交通拥挤、道路阻塞的目的[1,2]。因此, 研究路径优化具有十分重要的理论意义和实用价值。目前, 各国学者已经使用多种方法来研究路径优化问题, 包括启发式搜索[3]、粒子群算法[4]、遗传算法[5]、神经网络[6]、Petri网[7]等。尽管取得了一系列较好的实验结果, 但仍然有很多问题亟待解决。
本文在综合考虑交通网络各种动态变化因素的基础上, 以通行时间作为最优路径的选择依据, 提出了一种基于混合蛙跳思想的蚁群算法, 并应用于路径优化研究。针对基本蚁群算法搜索时间长、易陷入局部最优解等缺点, 通过引入混合蛙跳算法的全局信息共享和局部深度搜索机制, 以扩大搜索解空间, 使搜索不易陷于停滞状态。最后, 本文采用重庆市渝中半岛的路网进行仿真实验, 结果表明改进的蚁群算法能够更好地克服基本蚁群算法陷入局部极值的不足, 改善了搜索效率, 为路径优化研究遇到的问题提供了良好的解决方法。
2 城市交通路网的路径优化模型
2.1 城市交通路网模型
以城市交通网络中的道路交叉口为点分割成为路段, 同时把弯度较大的道路以转弯点也分割为路段, 于是可以将城市交通网络直观地认为是由相互连接的点状目标和线状目标组成的图, 且定义节点为路网的交叉口、边缘截断点和弯度较大的拐点, 弧为连接两个节点间的有向路段, 权值为通过路段遇到的阻抗。另外, 在实际的道路网络中, 还存在大量交通限制条件, 特别是以下两种情形: ① 交叉口的转向限制; ② 交叉口的转向延误。在建立城市道路网络模型时必须考虑交叉口的转向延误和限制, 以更好地表达真实的交通网络。由此可见, 城市交通路网模型可以用一个赋权有向图G=(V,A,W,D) 来描述, 其中:
① V={vi| i=1,2,…,n} 表示城市道路网络的节点集合;
② w={w(i,j) | w(i,j) ≥ 0;i,j=1,2,…,n}, 权值w(i,j) 表示从节点vi移动到节点vj的代价;
③ D={d(i,j,k) | i,j,k=1,2,…,n, 且i ≠ j ≠ k}为点权集合,d(i,j,k) 的表示由节点vi经节点vj至节点vk时在节点j处的延误, 若d(i,j,k)=+ ∞ , 则表示禁止从节点vi经节点vj转向到节点vk;
④ A={<vi,vj> | i,j=1,2,…,n; 且i ≠ j} 表示城市道路网络的有向路段集合, 有序对<vi,vj> 和< vj,vi> 表示两条方向相反的路段, 在图论中称为弧段。
2.2 最优路径模型
建立了体现城市道路交通的方向性及交叉口延误的城市道路网模型后, 最优路径计算问题就等价于在赋权有向图G=(V,A,W,D) 中搜索从出发地到目的地的一条具有最小权值总和的路径。
若s和d是G中两节点。一个有向路径P(s,d) 表示从始点s到终点d的路径: P(s,d)=(s,i,j,k,…,r,d) 即(s->i->j->k->…->r->d), 则从始点d到终点d的总路阻为:
显然, 最优路径问题就是寻找一条路径使得C(s,d)最小。本文以路段通行时间作为路段权值衡量城市交通网络最优路径的选取。
3 基于蚁群算法的最优路径问题
3.1 蚁群算法基本原理
蚁群算法[8,9](Ant Colony Optimization Algorithm,简称ACO) 是由Colorni、Dorigo和Maniezzo等于1991年首先提出来的, 它是受到真实的蚁群觅食行为启发而产生的一种模拟进化算法。生物学家发现蚂蚁之间通过留在所经路径上的信息素进行信息传递而达到合作的目的。自然界的蚂蚁在运动路径上释放出的特殊激素——信息素, 在蚂蚁个体之间的信息交流和相互协作起着重要作用, 其浓度与蚂蚁走过的路径长短有关, 路径越短,其浓度越高, 于是沿较短路径的蚂蚁首先到达并返回。当别的蚂蚁走到前面蚂蚁走过的路径时可以感知环境中这种信息素的存在及强度, 并倾向于朝着信息素浓度高的方向移动, 即选择信息素浓度高的路径的概率就会相对较大。于是, 由大量蚂蚁完成的高度自组织行为便形成一个信息正反馈机制: 某一路径上走过的蚂蚁越多,该路径上的信息素浓度越大, 则后来者选择该路径的概率越大; 蚂蚁少的路径信息素浓度低, 选择概率就小,并且随着时间的推移逐渐挥发直至消失, 这样的路径最后被淘汰, 最终指导蚂蚁集体搜索到一条从蚁穴到食物源的最短路径。
设蚁群规模为m, 路网节点数为n,τij(t) 为第t次迭代时路段(vi,vj) 上的信息素 ηij=1/wij, 为(vi,vj) 的启发信息。在搜索过程中, 蚂蚁根据路径上的信息素及路径的启发信息来计算状态转移概率, 则位于vi的蚂蚁k按以下选择策略选择Vj:
式中,allowedk=neighbori-tabuk为蚂蚁k下一步可以选择的节点集合, neighbori为与vi相邻的节点集合, 禁忌表tabuk为记录蚂蚁k已经过的节点集合;α为信息素启发式因子, 表示轨迹的相对重要性, 其值越大, 则该蚂蚁越倾向于选择其它蚂蚁经过的路径, 蚂蚁之间的协作性越强;β 为期望启发式因子, 表示能见度的相对重要性, 反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度, 其值越大, 则该状态转移概率越接近于贪心规则。
为了避免残留信息素过多引起残留信息淹没启发信息, 在每只蚂蚁走到终点后, 要对残留信息进行更新处理。在第t+1 次迭代时, 所有蚂蚁均到达目的地, 则各路段上的信息素更新为:
式中,ρ(0 ≤ ρ ≤ 1) 表示信息素的持久性, 则1-ρ表示信息素的挥发性, 该参数可以避免无限度的增强信息素的浓度, 当一条道路没有被任何蚂蚁选择到时, 这条道路上的信息素浓度会呈指数级的减少, 所以该参数还可以帮助算法“遗忘”过去时刻的“错误选择”或者“不良选择”。Δτkij表示蚂蚁k在此次迭代中<vi,vj> 增加的信息素。M. Dorigo给出了 Δτkij的三种不同模型,即ant-cycle、ant-density及ant-quantity, 前一个利用整体信息, 后两个利用局部信息, 因此本文采用性能较好的ant-cycle模型:
式中,Q是一个正常数, 表示每只蚂蚁所释放的信息素总和;Lk表示蚂蚁k搜索得到的路径上的行程时间。
3.2 引入混合蛙跳思想
混合蛙跳算法的基本思想是: 混合蛙跳算法[10,11]是一种受自然生物模仿启示而产生的基于群体的协同搜索方法。这种算法模拟青蛙群体寻找食物时, 按族群分类进行思想传递的过程, 将全局信息交换和局部深度搜索相结合, 局部搜索使得思想在局部个体间传递, 混合策略使得局部间的思想得到交换。在混合蛙跳算法中, 群体( 解集) 由一群具有相同结构的青蛙( 解) 组成。整个群体被分为多个族群, 不同的族群被认为是具有不同思想的青蛙的集合。族群中青蛙按照一定策略执行解空问中的局部深度搜索。在已定义的局部搜索迭代次数结束之后, 思想在混合过程中进行了交换。局部搜索和混合过程一直持续到定义的收敛条件结束为止。全局信息交换和局部深度搜索的平衡策略使得算法能够跳出局部极值点, 向着全局最优的方向进行, 这也成为混合蛙跳算法最主要的特点。
本文借鉴上述混合蛙跳思想对基本蚁群算法进行改进, 为叙述方便, 将“青蛙”表述为“蚂蚁”, 具体为:
① 族群划分
在蚁群算法中, 每次迭代L只蚂蚁均成功达到目的地后, 将群体内蚂蚁个体按适应度降序排列, 并将整个蚂蚁群体分成M个族群, 每个族群包含N只蚂蚁, 满足关系L=M*N; 然后, 第1 只蚂蚁分入第1 族群, 第2只蚂蚁分入第2 族群,……, 第M只蚂蚁分入第M族群,第M+1 只蚂蚁分入第1 族群, 第M+2 只蚂蚁分入第2族群, 依次类推, 直到全部蚂蚁划分完毕。
② 局部深度搜索
对于每一个族群, 具有最好适应度的解表示为Xb,最差适应度的解表示为Xw, 而所有族群中具有全局最好适应度的解表示为Xg。然后对每个族群进行局部深度搜索, 即对族群中的Xw循环进行更新操作, 更新策略为:
如果Xb与Xw所表示的路径节点序列具有公共节点( 除去起点与终点), 则选其一公共节点进行交叉操作,产生两条新路径, 将其中较优的解new Xw取代原来族群中的解old Xw。
如果Xb与Xw所表示的路径节点序列没有公共节点( 除去起点与终点), 则在该两条路径中分别任意剔除一条路段, 通过交叉拼接得到两条新路径, 如果其中较优的解new Xw优于原来的解old Xw, 则取代原来族群中的解; 如果没有改进, 则用Xg取代Xb重复执行交叉操作; 如果仍然没有改进, 则随机产生一个新的解取代原来的Xw。
3.3 最优路径求解的实现步骤
针对第2 节城市道网的路径优化问题, 把出发地和目的地分别假设为蚁群的巢穴和要寻找的食物, 则路径优化问题就可以转化为蚁群寻找食物的路径寻优问题。则用改进的蚁群算法求解最优路径问题的步骤如下:
Step1: 初始化控制参数、路段信息素c、迭代次数t=0 及最大迭代次数Nc;
Step2: 将m只蚂蚁均放在出发地vs, 对每只蚂蚁按式(2) 依次选择下一节点;
Step3: 对于成功到达目的地vd的蚂蚁, 计算其总行程时间, 记录当前最优解;
Step4: 按照3.2 节的混合蛙跳思想, 对蚂蚁群体进行族群划分和局部深度搜索;
Step5:按按式(3)和式(4)更新路段上的信息素;
Step6:t=t+1;若t<Nc,则转Step2,否则转Step7;
Step7:输出当前最优解。
4 应用实例与结果分析
4.1 路网实例
本文以重庆市渝中半岛的路网( 如图1 所示) 进行测试实验, 该路网共计220 个节点( 以黑圆点表示),341条路段( 主干道155 条、次干道43 条、支路143 条, 分别以实线、虚线、点线表示)。
4.2 结果分析
由于道路的拥堵程度随时间而变化, 行驶距离最短的路径并不一定是行驶时间最短路径, 因此, 本文以路段通行时间为路段权值, 以行程时间最短为最优目标,使用Matlab2015 编程计算在某时刻从朝天门( 节点001)到菜园坝(节点184)的最优路径。参数设置:m=200,Nc=100,α=2,β=5,ρ=0.9,c=10,Q=20。则测试结果如表1、图2 和图3 所示。
从上述结果对比可知, 改进蚁群算法求得的最优值(0.3223h) 优于基本蚁群算法求得的最优值(0.3277h),显然改进蚁群算法的搜索效果更好。这表明通过引入混合蛙跳思想改进基本蚂蚁算法, 可以尽可能扩大搜索空间, 增加解空间的多样性, 全局性和收敛速度有所提高,从而在一定程度上避免了局部收敛和早熟的趋势。
5 结束语
本文提出基于混合蛙跳思想的蚁群算法, 并求解城市路网最优路径, 较好地解决了基本蚁群算法容易陷入局部最优解和搜索速度较慢的问题, 实验结果表明这种方法是有效、可行的。但是, 如何合理地约简大规模复杂路网中的冗余节点以使蚁群算法在求解时能够较快收敛, 以及如何优化蚁群算法的参数配置, 将有待于进一步探讨。
参考文献
[1]FENG YUQIN,LENG JUNQIANG,XIE ZHONGYU,et a1.Route choice model considering generalized travel cost based on game theory[J].Mathematical Problems in Engineering,2013(1):1-5.
[2]吴正言,莫时旭.交通拥堵情况下路径诱导方案的生成方法[J].武汉理工大学学报(交通科学与工程版),2015,39(1):5-8.
[3]FU L,SUN D,RILETT L R.Heuristic shortest path algorithms for transportation applications:state of the art[J].Computers&Operations Research,2006,33(1):3324-3343.
[4]MOHEMMED A W,SAHOO N C,GEOK T K.Solvi ng shortest path problem using particle swarm optimization[J].Applied Soft Computing,2008,8(4):1643-1653.
[5]MAINAL M K,MABU S,HIRASAWA K.Pruning high-level network using genetic algorithm for efficient hierarchical route planning in road networks[C]//IEEE Annual Conference.Tokyo:IEEE,2011:2903-2909.
[6]崔铁军,马云东.时间递推耦合神经网络的交通路径动态诱导技术[J].计算机应用研究,2013,30(10):2932-2935.
[7]杨琰,廖伟志,李文敬等.基于Petri网的顾及转向延误的最优路径算法[J].计算机工程与设计,2013,34(10):3643-3648.
[8]REED M,YIANNAKOU A,EVERING R.An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing,2014,(15):169-176.
[9]HOSEINI P,SHAYESTEH M G.Efficient contrast enhancement of images using hybrid ant colony optimization,genetic algorithm,and simulated annealing[J].Digital Signal Processing,2013,23(3):879-893.
[10]VAISAKH K,REDDY A S.MSFLA/GHS/SFLAGHS/SDE algorithms for economic dispatch problem considering multiple fuels and valve point loadings[J].Applied Soft Computing,2013,13(11):4281-4291.
混合蚁群算法 篇8
针对要求较高、难以凭经验和先验知识准确分类的问题, 通过聚类分析[1,2,3], 将样本数据按某些属性或准则分成多个类别, 使得同类样本相似程度尽可能大, 同时, 不同类别的样本差异程度也尽可能大。K均值聚类算法是聚类分析中一种非监督实时聚类算法[4,5], 该算法是在最小误差函数的基础上将数据划分成不同类别。本文在蚁群算法和粒子群算法的基础上, 通过对两种算法进行结合, 提出了一种基于蚁群粒子群混合算法的K均值聚类优化算法。
2 传统K均值聚类算法的不足
根据K均值聚类算法思想, 首先对n个数据对象随机选择m个对象, 将这m个对象视为m个类的数据均值, 则m个均值就分别表示初始的m个不同聚类中心;然后计算剩余数据与聚类中心的相似度, 并分别赋给与聚类中心相似度最大的聚类;初始分类完成后, 再以各类数据均值作为对应类别的聚类中心, 进行重新聚类;如此反复迭代计算, 直至类收敛或达到最大的迭代次数时结束。K均值聚类算法虽然具有计算简单, 收敛速度快等优点[5], 但该算法仍然存在如下不足:
(1) 在计算之前必须确定初始聚类的个数。聚类的个数直接影响聚类结果及准确性。
(2) 初始值的选取对聚类结果影响较大。当初始值选取不当时, 可能会出现无解情况。
(3) K均值聚类算法采用的是梯度法求得最优解, 因而求得的结果是局部最优解, 而不是全局最优解。
3 K均值聚类优化算法
3.1 蚁群粒子群混合算法
蚁群算法 (Ant Colony Algorithms, ACA) 是一种源于大自然的仿生类算法, 它不需要任何先验信息, 从最初的的随机搜索路径开始, 通过找到规律使解空间逐渐逼近直至最终达到全局最优。在ACA算法中, 信息素更新公式为
其中, Q表示信息素总量, L表示搜索路径总长度。则第只k蚂蚁从城市i到城市j的转移概率为
其中, Nik是第k只蚂蚁在城市i的可行邻域城市集合, α和β分别为信息素浓度和启发式信息值在概率中的权重系数。
粒子群算法 (Particle Swarm Optimization, PSO) 是一种基于群体智能理论的全局寻优算法, 通过将每一个解看作搜索空间中具有一定速度的粒子, 根据该粒子当前搜索最优解和粒子群全局搜索最优解两个极值进行动态调整粒子位置。在PSO算法中, 粒子速度和位置更新公式为
3.2 ACA-PSO混合算法对K均值聚类算法的优化
根据ACA-PSO混合算法的思想, 对K均值聚类算法进行优化, 步骤如下:
(1) 粒子初始化。计算原始聚类中心, 得到初始粒子的位置编码, 同时计算粒子适应度并初始化粒子速度, 生成N个初始粒子群。
(2) 确定个体极值。比较每个粒子适应度与当前个体极值的最好位置适应度, 若前者大于后者, 则用该粒子的位置代替最好位置。
(3) 确定全局极值。比较每个粒子适应度与当前全局极值的最好位置适应度, 若前者大于后者, 则用该粒子的位置代替最好位置。
(4) 根据式 (5) 和式 (6) 对粒子速度和位置进行更新。
(5) K均值优化。对粒子的聚类中心编码, 并根据最邻近法则确定粒子类别, 然后对各类别的聚类中心进行计算, 同时更新粒子适应度以确定新的聚类中心编码值。
(6) 优化结束。确定最好位置和最大迭代次数时结束优化, 否则回到第2步中继续优化, 直至优化结束。
4 仿真分析
为验证蚁群粒子群混合算法优化的K均值聚类算法相比于传统K均值聚类算法的优越性, 通过仿真比较两种算法, 如图1所示。在相同条件下, 传统K均值聚类算法收敛速度较快, 但容易陷入局部最优问题。而本文提出的改进K均值聚类算法具有很强的全局寻优能力, 解决了局部最优问题, 从而证明本文方法的有效性。
5 结语
针对传统K均值聚类算法存在的不足, 提出了一种基于蚁群粒子群混合算法的K均值聚类优化算法。仿真结果表明, 该优化算法对初始值不敏感, 且具有较强的全局寻优能力, 能够对大数据进行准确分类, 具有一定的应用价值。
摘要：K均值聚类算法是一种经典的数据挖掘算法, 但该算法存在对初始值敏感且容易陷入局部最优问题, 一定程度上影响分类结果的准确性。通过分析蚁群算法和粒子群算法, 将两者混合算法应用到K均值聚类算法, 提出一种K均值聚类优化算法。仿真结果表明, 该优化算法不易受到初始值取值的影响, 且具有较强的全局寻优能力, 可作为聚类分析的一种有效方法。
关键词：蚁群算法,粒子群算法,K均值聚类算法
参考文献
[1]周丽娟.改进粒子群算法和蚁群算法混合应用于文本聚类[J].长春工业大学学报 (自然科学版) , 2009, 30 (3) :341-346.
[2]loan Cristian Trelea.The particle swarm optimization algorithm:Convergence analysis and paramer selection[C].Information processing Letters, 2002:317-325.
[3]Frans vanden Berth.An Analysis of Particle Swarm Optimizers[D].University of Pretoria, 2001.
[4]张宇飞.模拟电路多软件故障特征的智能优化提取方法研究[D].哈尔滨:哈尔滨理工大学, 2014.
[5]梁烨炜.K均值聚类算法的改进及其应用[D].湖南:湖南大学, 2012.
[6]张维存.蚁群粒子群混合优化算法及应用[D].天津:天津大学, 2007.
混合蚁群算法 篇9
1引言：
入侵检测系统（intrusion detection system，IDS）作为防火墙之后的第二道安全闸门，能够发现网络入侵行为，因此网络入侵检测已成为网络安全领域的研究热点[1]。网络入侵检测分为误用检测（misuse intrusion detection，MID）和异常检测（anomaly intrusion detection，AID）两类[2]。误用检测技术只可以检测已知入侵行为，不能对未知或变入侵行为进行检测，而异常检测可以较好对未知入侵行为进行检测，成为入侵检测中的主要研究方向[3]。传统网络入侵异常检测算法有：模式匹配算法、BM算法、QS算法等，这些算法均属于单模式的网络入侵检测算法，难以适应现代大规模网络安全检测要求[4]。近年来，随着人工智能技术的发展，出现了隐马尔可夫模型、支持向量机和神经网络等入侵检测模型，其中支持向量机（support vector machine，SVM）较好的克服了神经网络等传统机器学习算法的过拟合、泛化推广能力差等缺陷，对于高维、小样本的网络入侵检测具有明显优势[5-7]。大量实验表明，基于SVM的网络入侵检测模型性能与其参数：惩罚因子C和核函数参数等直接相关。为了获得较优SVM参数，学者们提出采用遗传算法（GA）、粒子群算法（PSO），在一定程度上优化了SVM的入侵检测性能[8-10]。蚁群算法（ant colony optimization algorithm，ACO）是一种源于大自然中生物世界的新仿生类算法，吸收了蚂蚁的行为特性，通过其内在的搜索机制，易于与其他启发式方法相结合[11，12]。
为了提高网络入侵检测率，提出一种变异蚁群算法（mutation ant colony optimization algorithm，MACO优化支持向量机的网络入侵检测模型（MACO-SVM），并通过仿真实验对其有效性进行检验。
变异蚁群算法
蚁群算法是由意大利学者M Dorigo等人在1991年受到蚂蚁搜索食物过程中依据同伴遗留下的信息激素进行最短路径选择的启发而提出的一种新的仿生优化计算方法，具有正反馈、分布式计算和贪婪启发式搜索等特点，但是基本蚁群算法存在过早收敛以及局部聚集等问题，为此，本文探路过程中，对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），产生一种变异蚁群算法（MACO），以便探索新的路径，提高问题求解的效率。
MACO算法优化SVM参数原理
采用MACO算法对SVM的参数C和σ优化过程，节点值表示C和σ，以入侵检测率作为目标函数，激素物质遗留在蚂蚁所走过的每个节点上，MACO算法所搜索出的最终路径表示最优网络入侵模型参数。SVM 参数优化的蚁群系统根据目标函数值来更新信息素的浓度，目标函数中包含各蚂蚁所爬行过的全部节点信息以及所建模型的网络入侵检测率。待优化的变量为SVM的参数C和σ，程序终止时，从蚁群的最优化路径中得到相对应的SVM的参数C和σ值，原理如图1所示。
MACO算法优化SVM参数过程
1）设蚁群规模为m，每只蚂蚁k均有一维数组pathk。其中依次存放第k只蚂蚁经过n个节点的纵坐标，n为所优化参数的总有效位，这些纵坐标连接在一起组成该蚂蚁的爬行路径。
2）全部蚂蚁置于起始点O，循环次数N=0，时间计数器t=0，最大迭代次数为：Nmax，初始化节点上信息量△τ（xi，yi，j，0），并设Δτ（xi，yi，j）=0。
3）设置变量i=1。
4）根据式（7）计算蚂蚁的转移概率，在线段Li上，根据概率以赌轮算法选择每只蚂蚁下一个转移节点，并将蚂蚁转移到相应节点上，并将该节点的纵坐标存入pathk的第i个元素中。
5）i=i+1，如果i>n，跳转到步骤6），不然跳转到步骤4）继续爬行。
6）根据数组pathk计算该路径对应的C和σ。
7）将训练集平均分成k个子集S1，S2，…，Sk。
8）SVM根据获得的{C，σ}对训练集进行学习，计算kfold交叉验证的检测率。
9）以kfold交叉验证中最优检测率作为适应度值，检测率最高对应路径作为本次循环的最优路径。
10）N=N+1，t=t+n，更新每个节点上的信息浓度，pathk中的全部元素置零。
11）对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），以便探索新的路径，并将新的路径与原有路径进行比较，选出最优蚂蚁。
12）如果迭代次数大于最大迭代数，则表示算法结束，并计算输出最优路径对应的SVM参数C和σ值。
13）SVM根据最优C和σ值对训练集重新学习，建立最优的网络入侵检测模型。
网络入侵检测多分类器构建
网络入侵检测实质上一个多分类问题，但SVM只能求解两分类问题，必须通过组合策略构建网络入侵检测器，本文采用有向无环图将两分类的SVM组合在一起，构造的网络入侵检测器如图2所示。
在CPU 2.8 GHz，RAM 1 GB 环境上，采用Libsvm 2，98实现仿真实验。按照一般的做法，实验采用KDD CUP 99数据集中的10%的数据（约10万条记录）中随机抽取的的正常连接记录作为训练样本。MACO算法的参数为：蚂蚁数m=10，最大迭代次数Nmax=100，Q=100，α=2，β=4。
为了使MACO-SVM模型检测更具说服力，在相同条件下，采用遗传算法优化SVM（GA-SVM）和基本蚁群算优化SVM（ACO-SVM）作为对比实验。模型性能评价指标为：检测率、误报率和运行速度。检测率和误报率定义如下：
检测结果对比
GA、ACO、MACO算法对SVM参数选择的结果见表3。然后采用表3的参数建立相应的网络入侵检测模型，GASVM、ACOSVM和MACOSVM的检测结果见表3。从表3可知，相对于对比模型GASVM、ACOSVM，MACOSVM的中支持向量数更少，但检测结果最佳，这表明 MACO算法比GA、ACO在SVM参数优化方面具有更好的较强的全局搜索能力，获得更优的SVM参数C，σ，可以降低网络入侵检测误报率，有效提高了网络入侵检测率。
运行速度对比
为了检测模型的运行速度，采用模型对验证集的检测时间（秒，s）作为衡量指标，各模型的检测时间见图3。从图3可知，相对于GASVM、ACOSVM，MACOSVM检测速度大幅度提高，主要由于MACOSVM减少了支持向量点数量，收敛速度加快，满足了现代网络入侵检测系统的实时性要求。
混合蚁群算法 篇10
在激光切割过程中,工件的加工时间等于激光实际出光时间与激光头空行程时间之和,而轮廓的边界长度是固定不变的,也就是说激光实际出光时间是固定不变的,那么只有缩短空行程时间才能缩短工件的加工时间。通过路径优化,缩短激光头在轮廓间移动的空行程距离,对节省总加工时间提高激光切割加工效率具有实际的意义[1]。
在实际切割中经常会遇到复杂的图形轮廓,轮廓间往往存在嵌套关系,如图1所示。切割时如果先对外层轮廓加工,切割完成后内层轮廓将会丧失定位的准确性,因此为了保证加工精度必须注意加工顺序,必须在轮廓嵌套关系的基础上进行分层,由最内层轮廓开始依次向外加工。
因为被切割轮廓为封闭式图形,因此在分析路径问题时可不考虑具体的轮廓轨迹,只需从轮廓中提取一个点来代替该轮廓,该点表示激光切割该轮廓时的起点和终点。当切割起点确定后,路径优化问题相当于一个旅行商问题(TSP)。现有研究一般均采用最近邻算法来确定切割起点[2],在优化过程中并未考虑切割起点变化的情况。本文根据图论原理将问题归结为广义旅行商问题(GTSP)[3]。其描述是:把给定的n个城市分成m个组,旅行商要选择一条访问每个组中一个城市的最短旅行回路。显然TSP是GTSP的特例。把每个零件轮廓包含的顶点作为每一组城市,把城市看做集合中的点。
1 数学模型的建立
激光切割路径规划应使空行程时间最短,文献[4]提出了时间距离的概念:激光切割空程运行时x、y轴扫描机构都能以最大速度运行,所以从一个轮廓的起点Pi(xi,yi),到另一个轮廓的起点Pj(xj,yj),空行程时间取决于max{fabs(xi-yi),fabs(xj-yj)},此距离即为时间距离。设激光切割的编程原点为P0=(x0,y0),则时间距离最短的目标函数为:
式中:cycles为被切割轮廓的个数,(xi,yi)为轮廓i的起始点坐标。在这里定义每个轮廓上的某一个顶点为切割起点,并记为Pi(i=1,2,……,m),其整个切割过程可以描述为:激光切割头从编程零点出发,快速行进到某一环上的切割起点,然后开光,切割完该封闭环即又回到切割起点,然后关光,蛙跳到下一个环上的切割起点,重复前面类似过程直到切割完所有环,再从最后一个环上的切割起点关光快速返回编程零点。
2 算法描述
在考虑轮廓位置关系的前提下,一般算法先使用最邻近TSP算法进行轮廓排序,再按照嵌套关系调整排序,这样轮廓顺序将失去部分邻近关系。所以提出先按照轮廓关系建立树形结构[5],再利用遗传蚁群算法对轮廓切割顺序及轮廓的起始点同时进行优化。
2.1 树形结构的建立
因为所有待加工轮廓都包含在激光切割机可加工区域范围内,因此以加工区域作为树形结构的根节点[6]。由图1所示轮廓关系得图2形式的树形结构。
2.2 遗传蚁群算法
遗传算法与蚂蚁算法的融合,其基本思想是汲取2种算法的优点,克服各自的缺陷,优势互补。在时间效率上优于蚂蚁算法,在求解效率上优于遗传算法,是时间效率和求解效率都比较好的一种新的启发式方法,其流程图如图3所示。
其基本思想是算法前过程采用遗传算法,充分利用遗传算法的快速性、随机性、全局收敛性,其结果是为后部分的蚂蚁算法产生初始信息素分布。算法后过程采用蚂蚁算法,在有一定初始信息素分布的情况下,充分利用蚂蚁算法并行性、正反馈性、求解效率高等特点[7]。
在旅行商问题中,城市从1到n顺序编号,而在广义旅行商问题中由于引入了城市集合,城市改用(集合编号、集合内城市编号)的数据对表达[8],为了尽可能少地改动原程序,在算法中创建了一个n行5列的二维数组Index存储城市序号之间的对应关系,其中n为城市总数,5列数据分别为城市从1到n顺序编号、所属轮廓编号、轮廓其父代编号、轮廓子代个数、轮廓是否已切割。在算法运行过程中,有时采用城市顺序编号,有时采用二维数组对,还要考虑轮廓之间的包含关系,Index数组保证了这些关系的对应。
a)遗传算法部分
编码与适应值函数:
采用十进制实数编码,以轮廓起始点的遍历次序为遗传算法的编码。适应度函数取为哈密顿圈长度的倒数。
种群成员编码初始化:
选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁衍子孙。遗传算法通过选择操作体现这一思想,进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大[9]。为避免最优个体的遗失,将最优个体中的一个直接被选择。
交叉操作:
交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体,新一代组合了其父辈个体的特征。
进行交叉的一对染色体父串,其中1条直接获得,另一条随机从成员中获得。具体交叉如下:
1)随机产生交叉起始点,交叉宽度是给定的,此处取50%。假设交叉起始点为3,则交叉区域为3-7。Old1=1、2、19、31、28、25、14、36、16、7。Old2=1、3、16、28、31、24、9、37、12、20为一对父代。
2)保存Old2中的3-7位,其他位先填0,temp=0、0、16、28、31、24、9、0、0、0。
3)去除Old1中在temp中已经记录或属于同一轮廓的点,使其为0。即Old1=1、2、19、0、0、0、14、36、0、0。
4)将Old1中非0项代替temp中的0项,则temp=1、2、16、28、31、24、9、19、14、36,temp即为交叉后的子代。
变异操作:
变异为新个体的产生提供了机会,由于算法同时对轮廓切割顺序和轮廓起始点进行优化,所以这里变异分为两种:一是随机获得染色体中的某一位,随机修改为属于同一轮廓的其他顶点;二是随机获得两个位置点,逆转这两位置点之间的所有点。同生物界一样,变异发生的概率很低,在本算法中是动态变化的,随着最优解未改变代数的增加而增加,并为其设置上限。
b)蚁群算法部分与衔接
蚁群算法应用了MMAS算法,并作了改进,其与传统的蚁群系统相比主要有以下几方面的不同:
1)与蚁群系统相似,为了充分利用循环最优解和到目前为止找出的最优解,在每次循环之后,只有一只蚂蚁进行信息素更新。这只蚂蚁可以是找出当前循环中最优解的蚂蚁(迭代最优解),也可以是从实验开始以来的最优解的蚂蚁(全局最优解),本文算法是每5代利用全局最优解,否则用迭代最优解。
2)为避免搜索的停滞,将信息素轨迹量的值域范围限制在[τmin,τmax]区间内。而在蚂蚁系统中信息素轨迹量不被限制,使得一些路径上的轨迹量远高于其他边,从而易于陷入局部最优解。
3)算法中通过遗传算法得到了一定的路径信息素,所以把信息素的初始值设置为τA=τB+τC。这里τB是一个根据具体问题规模给定的一个信息素常数,τC是遗传算法求解结果转换的信息素。
4)当全局最优解在一段时间内未改变,则引入了变异因子[10],具体操作同遗传算法部分的变异。
信息素轨迹更新:
在MMAS中只有一只蚂蚁用于在每次循环后更新信息轨迹。因此,轨迹更新规则为:
其中:Δτbestij=1/f(sbest),f(sbest)表示迭代最优解或全局最优解的值,1-ρ为信息素挥发因子。而τmin与τmax具有一定的比例关系:
其中n为解的个数,avg=n/2,Pbest一次搜索找到最优路径的概率,从而已知一个Pbest值,就可以为τmin设置一个合适的值。
蚂蚁路径构造:
不同与一般蚁群算法利用禁忌表,由于对于下一可访问的点限制条件比较复杂,算法中直接获取下一可访问的点集,然后依据信息素概率选择下一访问点。
1)复位Index中是否已切割列。切割路径的起始位置为编程原点,所有蚂蚁都从编程原点出发。
2)判断最新切割点是否为编程原点,若是跳到步骤6;若不是,跳到步骤3。
3)判断其父代是否只有1个子代,若其父代只有1个子代,则父代被选中,Allow中记录父代的所有顶点;若不止1个子代,跳到步骤4。
4)若父代为轮廓1,由于轮廓1并不表示实际轮廓,而是表示可加工区域。跳到步骤6;若父代不为轮廓1,跳到步骤5。
5)判断父代的子代是否已全部切割,若子代已全部切割,则父代被选中;若还有子代未切割,Allow中记录其未切割的兄弟轮廓的顶点。返回本步骤。
6)Allow中记录未切割且没有子代的轮廓的顶点。
7)从Allow中按轮盘赌法概率获得下一切割起始结束点,更新Index中的是否已切割列。
3 优化算例
根据本文算法,采用Matlab编写优化程序,对图1所示零件轮廓路径优化。控制参数如下:蚁群算法部分m=100,α=2,β=2,Q=1e5,1-ρ=0.15,Pbest=0.135,δ=0.15。m为蚂蚁个数,α为信息素重要程度因子,β为启发函数重要程度因子,Q为常量,1-ρ为信息素轨迹的衰减系数,npopulation为信息素平滑系数。遗传算法部分n Population=200,p Crossover=0.85,cross Percent=0.5,p Mutation=0.1,max Shock=0.75;n Population为种群个体数量,p Crossover为交叉概率,cross Percent为交叉比例,p Mutation为变异概率。Max Shock为最大突变概率。遗传算法迭代次数为30次,遗传算法求解结果转换的信息素值是经过路径加2。优化结果如表1所示。
表2中AA1为只利用本算法的蚁群算法部分,开始时信息素设置一个较大的数,第一次迭代后就会将信息素轨迹初始化为τmax。AA2为利用最近邻算法获得每个轮廓的切割起始点,然后利用蚁群算法只对轮廓切割顺序优化,CAM软件为韩光FS3015配套CAM软件。
从表2中可以看到GAAA很好地避免了算法陷入局部最优解,从图4、图5的比较中看到GAAA能很快的搜索到全局最优解。如图6全局最优解为:1,37,17,19,34,28,11,26,10,5。
4 结语
在激光切割行业中,由于开光切割的时间花费是无法减少的,因此需要研究如何缩小空程花费,以便提高加工效率。建立了以时间距离最短的空行程路径优化数学模型,并采用了GAAA算法,有效的解决了这一问题。且同单独的蚁群算法相比,GAAA算法能更快的搜索到最优解周围,而且不易陷入局部最优解。同先利用最近邻算法确定轮廓切割起始点后再利用蚁群算法求解该问题相比,GAAA得到的平均解提高了26%,同韩光FS3015配套CAM软件所得解的平均值相比提高了60%。
摘要：激光切割机的路径优化问题是激光切割行业的一个关键问题,针对其特点将其归纳为广义旅行商问题,利用改进的遗传蚁群算法来求解该问题。算法以时间距离最短为目标函数,对轮廓切割顺序及轮廓切割起始点同时进行优化。为了让算法所得解能够快速聚集在最优解附近而又不至于陷入局部最优解,利用遗传算法快速随机的全局搜索能力来产生蚁群算法初期的信息素分布,蚁群算法采用最大最小蚂蚁算法同时在其加入变异因子。仿真结果表明取得了非常好的效果。
关键词：激光切割,路径优化,广义旅行商问题,遗传蚁群算法
参考文献
[1]张永康.激光加工技术[M].北京:化学工业出版社,2004.
[2]李泳,张宝峰.复杂轮廓激光切割路径优化算法的研究[J].天津理工大学学报,2007,23(3):20-22.
[3]杨建军,刘保业,鞠录岩.激光切割路径优化的双重编码改进遗传算法[J].解放军理工大学学报(自然科学版),2012,13(6):35-37.
[4]王跃东,李卫,扬卫波.求解GTSP问题的自适应遗传算法[J].计算机工程与应用,2011,47(27):52-54.
[5]Jinhui Yang,Xiaohu Shi,Maurizio Marchese,Yanchun Liang.An ant colony optimization method for generalized TSP problem[J].PROGRESS IN NATURAL SCIENCE,2008,18(11):68-70.
[6]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展,2003,40(9):21-24.
[7]Han Huang,Xiaowei Yang,Chunguo Wu,et al.Hybrid Chromosome Genetic Algorithm for Generalized Traveling Salesman Problems[J].Advances in Natural Computation,2005,36(12):15-17.
[8]李士勇,陈永强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004.
[9]王美华,田绪红,廖鸿翔.求解广义旅行商问题的混合染色体遗传算法[J].计算机工程与应用,2009,45(27):38-40.
【混合蚁群算法】相关文章：
蚁群算法模型07-03
遗传蚁群算法05-28
优化蚁群算法08-10
智能蚁群算法09-05
蚁群算法及应用研究06-07
改进的蚁群算法08-22
蚁群算法的改进策略09-02
基于蚁群算法的TSP问题研究01-27
蚁群算法求解独立学院自动排课问题研究09-12