资源描述：
《蚁群算法求解连续空间优化问题的一种方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2002/13(12)2317-07©2002JournalofSoftware软件学报Vol.13,No.12∗蚁群算法求解连续空间优化问题的一种方法1,211陈崚,沈洁,秦玲1(扬州大学计算机科学与工程系,江苏扬州225009);2(南京大学计算机软件新技术国家重点实验室,江苏南京210093)E-mail:yzlchen@pub.yz.jsinfo.nethttp://www.yzu.edu.cn摘要:针对蚁群算法不太适合求解连续性优化问题的缺陷,提出用蚁群算法求解连续空间优化问题的一种方法.该方法将解空间划分成若干
2、子域,在蚁群算法的每一次迭代中,首先根据信息量求出解所在的子域,然后在该子域内已有的解中确定解的具体值.以非线性规划问题为例所进行的计算结果表明,该方法比使用模拟退火算法、遗传算法具有更好的收敛速度.关键词:蚁群算法;优化;遗传操作;非线性规划问题中图法分类号:TP18文献标识码:A人们从仿生学的机理中受到启发,提出许多用于解决复杂优化问题的新方法,统称为元启发(metahueristic)算法,如遗传算法、进化策略、模拟退火、蚁群算法、禁忌搜索(tabusearch)算法等,并成功地应用于实际问题.蚁群算法(antcolonyalgorit
3、hm,简称ACA)是最近几年才提出来的一种新型的模拟进化算法.它是由意大利学者[1]Dorigo,Mahiezzo,Colorni等人受到人们对自然界中真实的蚁群集体行为的研究成果的启发而首先提出来的.他们充分利用蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,通过人工模拟蚂蚁搜索食物的过程中个[2]体之间的信息交流与相互协作,最终找到从蚁群到食物源的最短路径的原理从而解决了TSP问题,取得了很[3][4,5][6]好的结果.随后,蚁群算法被用来求解job-shop调度问题、指派问题、序列求序(sequentialordering)等N
4、P完全问题,显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的优越性,证明它是一种具有广阔发展前景的好方法.生物学的研究表明,虽然单个蚂蚁的能力非常有限,但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力.这种能力是靠其在所经过的路径上留下的一种挥发性分泌物(pheromone)来实现的.蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径.其选择一条路径的概率与该路经上分泌物的强度成正比.因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可
5、能性就越大.蚂蚁的个体之间通过这种信息的交流寻求通向食物的最短路径.这种优化过程的本质在于:(1)选择机制.分泌物越多的路径,被选择的概率越大.(2)更新机制,路径上面的分泌物会随蚂蚁的经过而增长,而且同时也随时间的推移逐渐挥发消失.(3)协调机制.蚂蚁之间实际上是通过分泌物来互相通信、协同工作的.蚁群算法正是充分利用了这样的优化机制,即通过个体之间的信息交流与相互协作最终找到最优解,使它具有很强的发现较优解的能力.但是,蚁群算法也有一些缺陷,如需要较长的搜索时间.这是因为蚁群中多个个体的运动是随机的,虽然通∗收稿日期:2001-09-25;
6、修改日期:2002-04-10基金项目:国家自然科学基金资助项目(60074013);国家高性能计算基金资助项目(00219);江苏省教育厅自然科学基金项目(99KJB520003);南京大学计算机软件新技术国家重点实验室开放基金资助项目作者简介:陈崚(1951−),男,江苏宝应人,教授,主要研究领域为并行算法,并行体系结构;沈洁(1954−),男,江苏姜堰人,副教授,主要研究领域为系统优化,软件工程;秦玲(1979−),女,江苏泰兴人,硕士生,主要研究领域为算法设计,并行计算.2318JournalofSoftware软件学报2002,13
7、(12)过信息的交流能够向着最优路径进化,但是当群体规模较大时,很难在较短时间内从复杂无章的路径中找出一条较好的路径.为了充分利用学习机制,强化最优信息的反馈,Dorigo等人在基本的蚁群算法的基础上提出了称[7,8]为Ant-QSystem的更一般的蚁群算法,仅让每一次循环中最短的路径上的信息量作更新.为了克服在Ant-Q[9]中可能出现的停滞现象,Stutzle等人提出了MAX-MINAntSystem,允许各个路径上的信息量在一个限定的范围内变化.吴庆洪等人在蚁群算法中引入变异机制,既可克服停滞现象,又可取得较快的收敛速[10][6]度
8、.Gambardella等人提出了一种混合型蚁群算法HAS,在每次循环中蚂蚁建立各自的解后,再以各自的解为起点,用某种局部搜索算法求局部最优解,以此作为相应蚂蚁的解
