多蚁群伪并行优化算法第33卷33第23期No.23计算机工程ComputerEngineering2007年l1月December2007?人工智能及识别技术?;1000—_3428(2007)23—_o199—_o3文献标识码:A:TP18多蚁群伪并行优化算法刘利强,袁赣南,戴运桃(1.哈尔滨工程大学自动化学院,哈尔滨150001;2.哈尔滨工程大学理学院,哈尔滨150001)摘要:针对传统蚁群算法容易出现早熟和停滞现象,提出了一种多蚁群伪并行优化算法,将蚁群分成假设干个子蚁群,在各子蚁群中引入信息素甲滑机制,通过设计迁移算子,使多个子蚁群并行,协同寻优,从而使算法跳离局部最优解.类比实验说明,该算法比传统的蚁群算法具有更好的搜索全局最优解的能力.关键词:蚁群算法;信息素平滑;迁移算子;多蚁群Multi—antColonyVirtualParallelOptimizationAlgorithmLIULi.qiang,YUANGan.nan,DAIYun.tao(1.CollegeofAutomation,HarbinEngineeringUniversity,Harbin150001;2.CollegeofSciences,HarbinEngineeringUniversity,Harbin150001)[Abstract]Toovercomethelimitationofprecocityandstagnationinclassicalantcolonyalgorithm,thispaperpresentsamulti—antcolonyvirtualparalleloptimizationalgorithm.Theantcolonyisdividedintoseveralchildrenantcolonies,andthepheromoneflatnesssystemisusedineachchildantcolony.Bydesigninganimmigrantoperator,theparallelandcooperatingoptimizationofchildrenantcoloniesateobtained.Contrastiveexperimentsshowthatthealgorithmhasabettercapabilityofglobaloptimizationthantraditionalantcolonyalgorithm.[Keywords]antcolonyalgorithm;pheromoneflatness;immigrantoperator;multi—antcolony受到自然界中真实蚁群觅食行为的启发,20世纪9O年代初,DorigoM通过构造人工蚂蚁,设计了最初的蚁群优化算法——蚂蚁系统(antsystem,AS)J.该算法是一种基于多主体的模拟进化全局搜索算法,它采用分布式控制,具有自组织性和正反应性,优化过程不依赖于优化问题本身的严格数学性质,并且具有潜在的并行性0.人们对蚁群算法的研究已经显示出该算法在求解复杂优化问题(特别是离散优化问题)方面的优越性.蚁群算法也存在一些缺乏,蚁群算法在构造解的过程中,随机选择策略使得算法的进化速度变慢,正反应原理旨在强化性能较好的解,却容易出现停滞现象,从而以极大的概率引导蚁群走向局部最优解.l根本蚁群算法模型自然界中的蚁群具有自组织行为,在没有视觉的情况下,能够找出从食物源到蚁巢的最短路径.此外,蚁群还具有极强的环境适应能力,当原先最短的路径上出现障碍物时,能够再发现一条新的最短路径0.生物学家经过仔细研究发现蚂蚁之间通过一种称之为"信息素(pheromone)"的物质进行间接通信,相互协作来发现最短路径.蚂蚁在运动过程中,不但能够在它所经过的路径上留下该物质,而且能够感知它的存在及强度,并朝着该物质强度高的方向移动,以此指导自己的运动方向j.因为蚁群优化算法首先被应用于解决旅行商问题(travelingsalesmanproblem,TSP),所以根本蚁群优化算法模型一般使用TSP问题来进行描述,下面针对个城市的TSP问题给出了根本蚁群的优化算法模型.蚂蚁从起始点开始按随机比例规则根据转移概率来选择将要移动到的城市.在f时刻,蚂蚁k在城市i选择城市f的转移概率为'咖¨wf0otherwise其中,allowedk={0,1,…,一1}表示蚂蚁k下一步允许选择的城市;r,为边(√)上的信息素强度;,为边(√)的能见度;为信息启发式因子,表示信息素对路径选择的重要性;为期望启发式因子,表示启发信息对路径选择的重要性.经过个时刻,蚂蚁完成一次循环,各路径上的信息素量根据下式进行调整:【f+n)=(1一p)×(f)+△pe(0,1)(2)△=∑△(3)k=lfQ/L,蚂蚁k在本次循环中经过的路径t/j)△:4(4)}l0否则其中,P为信息素挥发因子;m为蚁群中蚂蚁的数目;Q为信息素强度,为常数;为蚂蚁k在一次循环中走过的路径长度.2多蚁群伪并行优化算法设计不管是DorigoM提出的根本蚁群算法,还是大局部学者所提出的改良蚁群算法,都是基于单种蚁群,单种信息素的算法,主要模拟了实际蚁群信息系统的一局部】.多蚁群伪并行优化算法的思想是将一个总的蚁群分成假设干个子蚁群,不同的蚁群赋以不同的控制参数,对各蚁...