群体智能优化算法

第18卷第8期计算机技术与发展Vol. 18 No.82008年8月COMPUTER TECHNOLOCY AND DEVELOPMENTAug. 2008群体智能优化算法王艳玲,李龙澍,胡哲(安徽大学计算机科学与技术学院,安徽合肥230039)摘要:群体智能优化算法利用群体的优势,在没有集中控制并且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了基础。介绍了两种群体智能算法模型:蚁群算法模型和粒子群算法模型,研究了两种算法的原理机制、基本模型、流程实现、改进思想和方法;通过仿真把蚁群算法与其他启发式算法的计算结果作对比,验证了蚁群算法具有很强的发现较好解的能力,不容易陷入局部最优;微粒群算法保留了基于种群的并行的全局搜索策略,采用简单的速度-位移模型操作,在实际应用中取得了较高的成功率。关键词:群体智能;蚁群算法;粒子群算法;启发式算法中图分类号:TP18文献标识码:A文章编号:1673- 629X(2008)08 -0114- 04Swarm Intelligence Optimization AlgorithmWANG Yan-ling,LI Long-shu, HU Zhe(School of Computer Science and Tech. , Anhui Univ. ,Hefei 230039 ,China)Abstract:By the use of groups' advantages, in the absence of centralized control and without providing the overall model situation, swarmnelligence optimum algorithm provides the foundation on finding complex distributed solutions to the problem. Introduces the two swarmintelligence algorithm models: ant colony algorithm model and the particle swam algorithm model, researches on principle mechanism, thebasic model,process realization and improved ideas and methods; and by comparing the calculation results of the ant c∞olony algorithm andother heuristic algorithm through the simulation,proved that the ant c∞olony algorithm has a strong ability to find better solutions, and isnot easy for a local optimum. The algorithm which besed on the population of reservations, parallel global search strategy, using simplyspeed - displacemnent model operation,has been made in a higher success rate in practical application.Key words:swarm itelligence; ant colony optimization algorithm;pericle swarm optimization; heuristic algorithm0引言法( Particle Swarm Optimization,PSO)[3]。前者是对蚂受社会性昆虫行为的启发,计算机工作者通过对蚁群落食物采集过程的模拟，已经成功运用在很多离社会性昆虫的模拟产生了一系列对于传统问题的新的散优化问题上;后者是源于对鸟群捕食行为的研究,算解决方法,这些研究就是群体智能的研究。群体智能法简单容易实现并且没有许多参数需要调整,目前已中的群体指的是“--组相互之间可以进行直接通信或广泛应用于函数优化、神经网络训练、模糊系统控制以者间接通信(通过改变局部环境)的主体,这组主体能及其他遗传算法的应用领域。够合作进行分布问题求解”。而所谓群体智能指的是“无智能的主体通过合作表现出智能行为的特性”。群1蚁群优化算法体智能在没有集中控制并且不提供全局模型的前提1.1 蚊群算法原理下,为寻找复杂的分布式问题的解决方案提供了基础。受蚂蚁觅食时的通信机制的启发,20世纪90年在计算智能领域有两种基于群体智能的算法:蚁代Dorigo提出了蚁群算法来解决经典的“旅行商问群算法(Ant Colony Optimization,ACO)1,2]和粒子群算题”。蚁群算法设计虚拟的“蚂蚁”将摸索不同路线,并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发,每只蚂蚁每次随机选择要走的路径,收稿日期:2007-11-27它们中国煤化工息素比较浓的路径。基金项目:国家自然科学基金资助项目(60273043);安徽省自然科根据"学基金资助项目(050420204)YCNMHC则，即可选择出最作者简介:王艳玲(1981-),女,安徽亳州人,硕士研究生,研究方向佳路线。出了这个异法利用」正反馈机制,使得较短为智能软件;李龙澍,教授,博士生导师.研究方向为智能软件。的路径能够有较大的机会得到选择,并且由于采用了第8期王艳玲等:群体智能优化算法●115●概率算法,所以它能够不局限于局部最优解。实验结蚁群系统:蚁群系统是对AS算法的选路和信息果表明蚁群优化算法具有较强的鲁棒性和搜索较好解更新策略作了相应的改进,即:的能力,但同时也存在一些缺陷,如收敛速度慢、易出1)采用伪随机比率选择规则的选路方式,即对于现停滞现象等。在城市i的蚂蚁按公式(3)选择下一个城市j:1.2 AS 算法模型fang .maex{茹. 嘱}ifq≤qo考虑到真实蚁群的行为与TSP问题的相似性,蚁否则,按公式(2)进行概率式搜索群算法(AS)首先被应用于平面上n个城市的TSP向题[41。n个城市的TSP问题即求从某-个城市出发,经其中,q是在[0,1]区间均匀分布的随机数,qo是一个过n- 1个城市各一次,最后回到出发点的最短环路。参数(0≤9qo≤1),s为根据方程式(3)给出的概率分为模拟实际蚂蚁的行为,首先引人如下记号:布所选出的一个随机变量。m表示蚁群中蚂蚁的数量;n表示城市的数量;2)局部信息更新。蚂蚁从城市i转移到城市j后，di表示城市i和城市j的距离;r;(t)表示t时刻在边路径(i,j)上的信息量按公式(4)进行更新:(i,j)上的信息素轨迹强度;w表示边(i,j)的能见tg=(1-E)●rqj+ξ●τo， ξ∈(0,1) (4)度,在蚂蚁算法中,的通常取城市i和城市j之间距离其中τo为常数,ξ∈(0,1) 为可调参数。的倒数,即n;= 1/dy;Of表示蚂蚁k在边(i,j)上留3)全局信息更新。针对全局最优解所属的边按公下的单位长度轨迹信息素量;帱表示蚂蚁k的转移概式(5)进行信息更新:率,j是尚未访问的城市。rj(t+ 1) = (1-p). r;(t)+ ρ° O增(t),p∈各路径上的信息量相等,设rj(0) = C(C为常(0,1)数)。每只蚂蚁根据路径上的保留信息独立地选择下一O增= 1/L曲(5)个城市。在时刻t,蚂蚁k从城市i转移到城市j的概率其中L劝为当前全局最优解的长度。格为:最大-最小蚂蚁系统(MMAS)[6]:与AS相比,主,ifj∈alwede要作了如下改进:端=(1)①每次循环结束后,只有最优解所属路径上的信否则息被更新;其中,a表示蚂蚁在运动过程中所积累的信息量的重②为了避免搜索时出现停滞现象,各路径上的信要程度;β表示蚂蚁在运动过程中启发信息在蚂蚁选息量被限制在范围[τman,Tmx]内;择路径中的重要程度。alwele = {0,1,2,,n-1}-③初始时刻,各路径上的信息量取最大值。所有tabuk表示蚂蚁k下一步允许选择的所有城市，列表.蚂蚁完成一次循环后,按公式(6)对路径上的信息作tabu,记录了当前蚂蚁k走过的城市,当所有n个城市全局更新:都加人到tabuy中时,蚂蚁k便完成了一次循环,此时rg(t+ 1)=(1- p).q;(t)+ p.0rm(t),p∈蚂蚁k所走过的路径便是问题的一个解。当所有蚂蚁完成一次循环后,各路径上的信息要根据(2)式调整:0ro= 1/Lm(6)rv(r+ n)=(1-p).τg(l)+Oτj ρ∈ (0,1)其中,Lou为本次循环的最优解。1.4算法流程Or。(t)= Z0t()(2)步骤1 nc ←0(nc为迭代步数或搜索次数);各其中pρ表示路径上信息的蒸发系数, 1- p表示信息的τ,和Oτ,的初始化;将m只蚂蚁置于n个顶点上;保留系数;0tj表示本次循环路径ij上信息的增量,如步骤2将每个蚂蚁的初时出发点置于当前解集果蚂蚁k没有经过路径i,则0塔的值为零,否则为中;对每个蚂蚁k(k = 1,2.**,m),按概率移至下一Q/L;(其中Q为常数, L&表示第k只蚂蚁在本次循环个顶点j;将顶点j置于当前解集;中所走过的路径的长度)。步骤3计算每 个蚂蚁的路径长度LQ(k = 1,2,1.3 蚁群优化算法中国煤化工针对AS算法的不足,一些学者提出了许多改进[HCNMHG轨迹强度;的蚂蚁算法,如蚁群系统、最大-最小蚂蚁系统和带精步骤5对各边弧(i,j),置 Otrj←0,nc←mc +英策略的蚂蚁系统[$]等。1;计算机技术与发展第18卷步骤6若nc <预定的迭代次数且无退化行为，2.2 基本粒子群模型则转步骤2;假设m个粒子组成-一个种群,在D维的空间步骤7输出 目前最好解。[Xmm,Xx]D中搜索。第i个粒子在第t代的位置为1.5蚊群算法的应 用及与其他算法的比较X;(t) = (xi1,Ii2."",xn),速度为V;(t) = (V1,V2,蚁群算法作为一种新的群体智能启发式优化算.. vp)。粒子本身目前所找到的最优解pBest为P;(t)法,主要用于求解组合优化问题,其中包括旅行商问题= (Pi,e.*",po),整个种群目前找到的最优解(TSP)、车间任务调度向题(VRP)7]、图着色问题gBest为Pg(t) = (P[+)2e.".pn)。按追随最好位置(GCP)[8]、有序排列问题(SOP)以及网络路由问题等。的原理,在每个迭代周期中，粒子按(7)、(8)式更新速为了说明蚁群算法的优点与不足,给出用ACS求度和位置。解TSP的实验结果,该实验中除ACS外的其他结果都vu(t+1)= w. vu(t) + c1●rand().(pu(t)-来源于文献[9],取10次实验的平均值。进行对比的xu(t)) +c2. rand().(pr(t)- xa(t))(7)优化算法有:模拟退火法(SA) ,进化计算(EP),遗传算xu(t+ 1)= xu(t) + vu(t)(8)法(GA)和模拟退火与遗传算法相结合的算法(AG)其中c1为认知因子,c2为社会因子,通常c1= c2=2,(见表1)。ACS的参数设为M= 10,β=2,qo=0.9,rand() 为[0,1]之间的随机数。为了使速度不至于过a= ρ=0.1,to= (n. Lm)-。大,把Vs限制在[Vai,V]之内,V.和Vx为常表1 TSP问题的多种优化算法对比数,通常Vma= Xmm，Vmx= Xmxo当vu> V,取标准问题名称ACSGAPSAACVu= Vmx;当ou< Vmin,取vu= Vmimo w为递减的惯Oliver304242120(30城市) (420.371) (NA) (423.74) (NA) (NA)性权值,- -般从0.9递减到0.4。迭代改数[1470] [3200][40000][24617] [12620]2.3粒子群优化EilS0432428426443436粒子群算法可以通过速度松弛迭代策略增强局部(50城市) (432.172) (N/A) (427.86) (N/A)(NA)搜索能力,加速收敛;用精英集团来增加多样性,提高迭代次数[2412] [25000] 00000] [68512] [2111]全局搜索能力。从实验结果可以发现,蚁群算法具有很强的发现速度松弛迭代策略为:如果当前粒子的适应度好较好解的能力,不容易陷人局部最优。这是因为该算于前一代粒子的适应度,那么下一代粒子的速度保持法不仅利用了正反馈原理,在一定程度上可以加快进不变,否则就按照速度更新方程(7)对速度更新。化过程,而且是一-种本质并行的算法,个体间不断进行精英集团选择:粒子在按(7)式更新速度时,从两信息交流和传递,有利于发现较好解。个方面获得信息,-一个是粒子本身的信息,本身目前所找到的最优解P;另一个是种群共享信息，整个种群2粒子群算法目前搜索到的最优位置Pg。事实上,有时其他一些粒2.1粒子群算法原理子的P;比Pg的解只是稍微差-一点,都是较好的解,但粒子群优化算法是--种基于种群的迭代搜索算由于(7)式只利用了Pg的信息，没有使那些较好P;的法,种群内的个体(粒子)不断追随最优个体进行寻优信息在种群中共享。精英集团的概念是,在每步迭代搜索。算法首先在搜索空间内随机初始化一群粒子,中,对P;的适应度从小到大排序取前k(≤m)个粒子每个粒子的位置是优化问题的一个解,将其带人目标.作为精英集团0,集团内的个体都有机会作为种群的函数计算出适应值,再根据此适应值的大小来衡量粒最优解Pg带人公式(7)进行计算。这样不但解决了种子的优劣。每个粒子的速度决定了其运动的方向和步群的多样性问题，同时使优势粒子的信息得到了充分长,粒子根据本身的记忆信息和整个种群的共享信息，利用。不断更新自己的速度和位置,去试探搜索空间内的不2.4算法流程同解。在迭代过程中,每个粒子更新速度时,总是在原步骤1初始化 m个粒子的位置和速度;来速度的基础上调整以趋向于两个位置,一个是粒子步骤2把每个粒子的位置 带入目标函数评价其本身目前所找到的最优解(pBest),另一个是整个种群优生中国煤化工目前找到的最优解(gBest) ,并期望在向两个位置移动|YHCNMHG值与其本身目前最优的过程中,发现更好的解,以取代pBest或gBest,通过位置P;的函数作比较,如果好于P,则将其作为目前种群中粒子的不断交互。逐渐收敛到最优解。最好位置P;第8期王艳玲等:群体智能优化算法步骤4对整个粒子群 目前最优位置进行P,排求解。可以不通过个体之间直接通信而是通过非直接序,前k个作为精英集团0k;通信进行合作,这样的系统具有更好的可扩充性。由步骤5每个粒子 从精英集团2中,随机选取P,于系统中个体的增加而增加的系统的通信开销在这里作为P十分小。系统中每个个体的能力十分简单,这样每个步骤6如果适应度变坏,P。 代人速度迭代方程，个体的执行时间比较短,并且实现也比较简单,具有简重新计算速度,否则,速度不变;单性。因为具有这些优点,虽说群体智能的研究还处步骤7检查速度各个分量是否在[Vm, Vx]于初级阶段,并且存在许多困难,但可预言群体智能的范围内,如果大于Vax设为V. ;如果小于V.设为研究代表了以后计算机研究发展的一-个重要方向。Vm; .步骤8按位置更新方程 ,更新粒子位置;参考文献:步骤9检查各个分量是否在[Xmgn,Xqx] 范围[1] Dorigo M,Cambrdella L M Ant Colony System:A Coopera-内,如果超出,在[Xmn,Xmx]内随机取- -个值, 设为该tive Leaming Approach to the Traveling Sales man Problem分量;[J]. IEEE Transactions on Evolutionary Computations, 1997,1(1):53 - 66.步骤10如果未达到预先设定的最大代数或未[2] Garnberdella L M,Dorigo M Solving Symmeric and Asym-达到足够好的函数值则返回步骤2。metric TSPs by Colornies[C]//In poeedings of the IEEE In-2.5粒子群算法的应用temational Conference on Evolutionary Computation(ICEC由于粒子群算法出色的性能,目前已广泛应用于'96).[s.I. ]:IEEE Pres,1996:622 - 627.函数优化、神经网络训练、模糊系统控制等众多领域。[3] Kennedy J,Eberhart R C. Paride swarm optinization[C]//下面简要介绍粒子群算法在神经网络中的应用。In: Procedings of IEEE Intemational Conference .on Neural当粒子群算法用于神经网络训练网络权值时,粒Networks. Piscataway,NJ:[s.n. ],1995:1942 - 1948.子就表示神经网络的-组权,粒子的纬度就是神经网[4] Dorigo M, Maricezo V,Colomi A. The ant systen: opimia-络中权值的个数。一般神经网络的初治值介工-1和tiom bya olony of c∞operating agents[J]. IEEE Transectionson Systems, Man, and Cybermetics,Part B, 1996,26(1):29-+1之间,训练结束后的权值也是一1和+1之间,因41此,粒子的范围可以设定为-1和+1之间。惯性因子[5] Bulnheimer B, Hartl R F, Srauss C. A New Rank - basedw的取值既要考虑到避免陷人局部极小,又要保证收Version of the ant st system:AComputational Study[ R]. Vien-敛性,算法的初期阶段让惯性因子w取较大的值，有利m: Institute of Management Science, University of Vienna,于跳出局部极小点,逐步调整w,使其递减,以保证算1997.法的收敛性。实验结果表明,粒子群优化算法训练的[6] Stuzle T,Hoos H H. MAX - MIN Ant System[J]. Future神经网络收敛速度明显加快。Generation Computer Systems,2000, 16(8):889 - 914.[7] Colormi A,Dorigo M,Maniezo V,et al. Ant system for job-3结束语shop scheduling[J]. Belgian Joumal of Operations Resarch,Stistis and Computer Scienoe(JORBEL), 1994, 34:39一群体智能是新兴的用于寻找全局最优解的算法，s3.已经广泛地应用于许多领域,取得很好的效果。群体8] Costa D,Hertz A. Ants can∞olor graphs[J]. Journal of Operae-智能的特点和优点是:群体中相互合作的个体是分布tional Research Society,1997 ,48:295 - 305.式的,这样更能够适应当前网络环境下的工作状态;没9] Durbin R,illshaw D. An Analogue Approach to the Travel.有中心的控制与数据,这样的系统更具有鲁棒性,不会ling Salesman Problem Using an Elastic Net Method[J]. Na-由于某一个或者某几个个体的故障而影响整个问题的ture, 1987(326):689 - 691.(上接第113页)[7] 金玉坚,刘 焱.新型网络信息检索效果评价指标体系设技术与发展,2007,17(9):66 - 70.计[J].现代情报,2005(4);185 - 188.[10] Zamir 0O,Erzioni 0. Web Daument Cusering:A Feasblity[8]李振龙.web信息检索的技术分析与发展策略研究[J].计中国煤化工R'98. New York:ACM箅机科学,2006,33(4):181 - 184.[9] 卫琳.基于搜索结果的个性化推荐系统研究[J].计算机YHCNMHG