《基于协同合作的蚁群优化算法》由会员分享，可在线阅读，更多相关《基于协同合作的蚁群优化算法（5页珍藏版）》请在金锄头文库上搜索。
1、2009 0569基于协同合作的蚁群优化算法庞思睿 孙文生 北京邮电大学 北京 100876摘 要 蚁群优化是一种模拟蚂蚁觅食的群集智能搜索算法，基本蚁群算法收敛性较差，易陷入局部最优解。本文在基本蚁群算法的基础上，提出一种新的蚁群优化算法，通过在信息素局部更新中引入信息素扩散模型，在信息素全局更新中引入随机扰动机制，发挥蚂蚁之间的协同合作能力，提高了算法的收敛速度。以TSP为例的仿真实验表明，该算法具有较强的寻优能力、较好的鲁棒性和有效性。关键词 蚁群算法；群集智能；旅行商问题引言蚁群优化(Ant Colony Optimization，ACO)由意大利学者M.Dorigo等人于20世纪90
2、年代初提出，是继遗传算法、人工神经网络等优化算法之后的又一种启发式搜索算法1-3。ACO在求解复杂优化问题方面有一定优越性，成功解决了很多复杂的组合优化问题。至今，ACO的应用已拓展到动态环境的路径规划4、通信网路由优化等多种领域。研究表明，ACO是一种模拟种群进化的算法，具有随机搜索、全局优化、分布式和正反馈等优点，同时也存在搜索时间长、易陷于局部最优、受参数影响大等缺点。为避免发生早熟或停滞现象，很多学者提出了改进算法5-7。文献5改进了信息素(pheromone)的更新机制，在搜索过程中由获得最好解的蚂蚁更新信息素以加速收敛，并通过控制信息素的变化范围来克服停滞现象；文献6提出了一种具有
3、变异特征的蚁群算法，采用逆转变异机制加快局部搜索；文献7提出了一种基于信息素扩散模型的蚁群算法，在加快收敛速度的同时避免陷入搜索停滞。本文提出了一种基于协同合作的蚁群优化算法，该算法采用新的扩散模型实现信息素局部更新，采用随机扰动机制实现信息素的全局更新，发挥了蚁群之间的协同合作能力，使收敛速度更快，全局优化能力更强。实验结果表明，本文提出的算法在控制参数的敏感性、寻优能力、以及防止早熟或停滞等方面均远远优于基本蚁群优化算法。1 基本蚁群算法在求解不同性质的问题时，蚁群算法的模型也有所不同，但主要思想都是生成一定数量的蚂蚁，通过每只蚂蚁搜索路径建立可行解。先将蚂蚁随机放置在若干节点上，每只蚂蚁
4、从初始节点出发，根据路径上信息素浓度和启发信息以某种概率策略选择下一个节点，直到建立可行解。每只蚂蚁根据解的优劣程度，更新路径上的信息素。如此周而复始，直到蚁群找到最优解。以n个城市的旅行商问题(Traveling Salesman Problem, TSP)为例来说明基本蚁群算法(Ant Colony System，ACS)8。TSP是指旅行商按一定顺序访问每一个城市，每个城市仅能访问一次，最后回到起点，且路径最短。TSP的实质是在n个节点的完全图上找到一条最短的哈密顿(Hamilton)路径，是一个易于描述却难于处理的NP难题。1.1 下一城市的选择设m是蚁群中蚂蚁的数量，dij(i，j=
5、1，2，n)表示城市i和城市j之间的距离，表示 时刻在城市i与城市j路径上信息素的浓度。初始时刻，各条路径上信息素的浓度相等，(C为常数)。蚂蚁通过概率策略选择下一个要访问的城市，令表示在 时刻蚂蚁k从城市i转移到城市j的概率，则基金项目：国家自然科学基金项目(60772112)Broad Angle for Technology信息通信技术70(1)其中：表示路径(i, j)的能见度，通常取值为1/dij；称为信息素启发式因子，表示信息素在选择概率上的作用，0；称为期望启发式因子，表示路径长度在选择概率上的作用，0；禁忌表(k=1,2,m)用来记录蚂蚁k所经过的城市；allowedk表示蚂蚁
6、k下一步允许访问的城市集合9。1.2 信息素的局部更新每只蚂蚁选择一个城市后，按式(2)更新该路径上的信息素。(2)(3)其中，表示信息素挥发因子，1-表示信息素残留因子，0，1； 是蚂蚁k从初始城市到当前城市已走过的路径长度10。1.3 信息素的全局更新经过n个时刻，所有蚂蚁都完成了一次周游，清空禁忌表，并按式(4)更新本次周游中最佳路径上的信息素。(4)表示第k只蚂蚁在本次循环发现的最优路径(i, j)上留下的信息素值，M.Dorigo曾给出三种不同的蚁群算法模型11：蚁周系统(Ant-Cycle System)、蚁量系统(Ant-Quantity System)、蚁密系统(Ant-Den
7、sity System)，差别在于全局信息素更新方式不同。对于求解TSP，蚁周系统的性能较好，即(5) 其中，Q为常数，Lk表示第k只蚂蚁在本次循环中走过路径的长度。算法中通常设置一个周游次数计数器NC，当达到设定值时算法结束，输出迄今为止发现的最短路径，即为所求TSP的解。2 基于协同合作的蚁群优化算法本文提出了一种基于协同合作的蚁群优化算法，其中，下一城市选择原则与基本蚁群算法相同，不同的是在信息素的局部更新中引入了扩散模型，在全局更新中增加了取优蚂蚁的数量。该算法增强了蚂蚁间的协同合作，改善了基本蚁群优化算法收敛速度慢，易收敛到局部优化解的缺点。2.1 信息素扩散模型文献7提出了一种基于
8、信息素扩散模型的蚁群算法，制定了一种信息素扩散挥发规则，其优点是比较接近真实蚂蚁的行为，寻优效果较好，但扩散模型较复杂，无信息素的局部更新机制，本文在此基础上提出了一种更加简单有效的信息素扩散模型(见图1)。假定蚂蚁处于原点O时，信息素的浓度为，信息素将以原点O为中心，以r为半径在圆形范围内扩散，如图1所示。设圆内存在一点l，为原点o到点l的距离，则L点接收到的信息素浓度 由式(6)确定(6)2.2 基于协同合作的信息素局部更新机制蚂蚁在爬行过程中，每经过一个城市，都要向邻近的路径上扩散信息素。若蚂蚁k走过两个城市i和j，其距离为dij，则蚂蚁k将采用图1所示的信息素扩散模型，分别以城市i和城
9、市j为中心，以r为半径向周围的路径上扩散信息素。城市l与城市i、j相连的路径(i, l)和(j, l)都会因信息素扩散而引起浓度的变化，变化量分别为图1 信息素扩散模型lrdlO技术广角2009 0571和，下面推导和的表达式。设蚂蚁k在城市i和城市j的信息素浓度，为小于1的参数；扩散半径， 为所有城市的平均距离。结合式(6)，可推得路径(i, l)、(j, l)上信息素浓度的变化、分别为(7)(8)在本文提出的算法中，将式(7)和式(8)代入式(2)，采用新的信息素扩散方式来对信息素进行局部更新。与基本蚁群算法的信息素更新机制相比，信息素的扩散方式发挥了蚁群之间的协同合作能力，局部更新更加灵
10、活，更加接近真实情况。蚂蚁每走一步，改变了多条路径上的信息素浓度，加快了收敛速度。2.3 加入扰动机制的信息素全局更新机制蚂蚁在行进过程中采用了协同合作的信息素局部更新方式，加快了算法的局部寻优速度，同时也增大了局部收敛的可能性。为了防止陷入局部最小解，应该使解空间产生某种方式的随机扰动。目前，已有文献介绍了在蚂蚁寻路过程中加入随机扰动机制的方法，文献12提出了一种在蚂蚁寻路过程中，引入遗传算法作为随机扰动的方法。本文采用如下扰动方式：改变基本蚁群算法的信息素全局更新机制，选取本次循环中最优的个解(对应只蚂蚁走过的闭合路径，本文取=0.2m)进行信息素全局更新，从而防止早熟或停滞。实验表明，加
11、入随机扰动策略，使得解的收敛速度更快，同时避免了局部收敛的发生。2.4 改进蚁群优化算法的步骤综上所述，基于协同合作的蚁群优化算法的具体实现步骤如下：Step1：初始化参数，读入城市信息，计算城市距离矩阵；将m只蚂蚁随机分配到n个城市，将出发城市添加到每只蚂蚁的禁忌表中。Step2：按概率选择下一个城市：蚂蚁k按式(2)和式(3)，计算城市的转移概率，并根据赌轮盘规则选择下一个城市j，将j加入禁忌表。Step3：信息素局部更新：根据信息素扩散模型，蚂蚁k分别按式(7)和式(8)更新相应路径上的信息素。Step4：若蚂蚁k的禁忌表未满，转至Step2。Step5：信息素全局更新：当m只蚂蚁完成周
12、游后，计算各蚂蚁走过的路径长度，更新迄今为止最优解，并选取本次循环中个最优解，按式(4)进行信息素全局更新。Step6：若达到终止条件，输出最优解。3 仿真实验3.1 算法有效性和收敛性为了验证本文提出的蚁群优化算法的性能，选用TSPLIB (http:/www.iwr.uni-heidelberg. de/groups/comopt/software/TSPLIB95/tsp/)中的实例Olive30进行仿真实验，并与基本蚁群算法、文献7算法进行比较。实验独立进行30次，统计结果如表1所示，取其中的16组数据，优化结果如表2所示。参数设置：m=30，=6，NCmax=100，=1，=2，q0
13、=0.98，=0.6，=0.4，Q=100由表1和表2的数据可见：基本蚁群算法得到的最表1 独立实验30次的统计结果本文算法415423417.53337指标最好解最差解平均值达到最好解的次数基本蚁群算法418459427.43543文献7算法415428418.65516表2 两种算法实验结果比较14164234209422422415实验编号本文算法基本蚁群算法文献7算法实验编号本文算法ACS文献7算法24154224161041643341534154324181141542241544204254211241941842054194184181341842642264194324221
14、4415425422741644441515423424422841543941516418423419Broad Angle for Technology信息通信技术72差解较多，表明基本蚁群算法极易收敛到局部最小解。文献7算法可得到较优的解，且相对稳定。本文算法的实验结果与文献7基本相当，均能有效改善基本蚁群算法的全局优化能力。与文献7算法相比，本文的算法规避了较为冗繁的计算模型，提高了计算效率，具有较快的收敛速度。图3为本文算法求解Olive30得到优化解为415时的闭合路径。3.2 算法鲁棒性文献1指出，基本蚁群优化算法的性能受参数影响很大，算法的鲁棒性较差。为考察本文算法的鲁棒性，在
15、实验中令取值为0.54，分别用本文算法、基本蚁群算法及文献7算法对Olive30求解30次并取平均值，优化结果如表3所示。可见，基本蚁群算法的优化解受值影响较大，且在30次中有明显收敛于局部的最优解的情况，而文献7算法与本文算法均具有较好的鲁棒性。但本文算法采用较为精简的扩散模型，在收敛速度上有较大提高。4 结论本文在基本蚁群算法的基础上，提出一种基于协同合作的蚁群优化算法，改进基本蚁群算法的信息素更新机制，提高了蚂蚁在选路时的协同合作能力。仿真实验表明，该算法能较好地发现全局最优解，并具有较快的收敛速度、较高的稳定性和较强的鲁棒性，在综合性能上远高于基本蚁群算法，且在计算效率上优于文献7给出
16、的算法。参考文献1234567图2 本文算法与文献7算法最优解进化比较图3 Olive30的路径图表3 不同值下的计算结果本文算法415.22416.60418.41418.01418.96值0.51234基本蚁群算法426.41430.03433.60440.42438.23文献7算法416.51415.23419.67418.55418.78ColorniA, Dorigo M. Heuristics from nature for hard combinatorial optimization problemsJ. International Trans Operational Research, 1996,3(1):1-21Dorigo M,Gambardella L M.Ant colony system:A cooperative
