蚁群算法及算例课件

1、蚁 群 优 化 算 法（ACO算法）一、概述二、蚂蚁系统（AS）三、算例四、改进的ACO算法一、概述（一）算法背景蚁群的自组织行为特征 1、高度结构化的组织虽然蚂蚁的个体行为极其简单，但由个体组成的蚁群却构成高度结构化的社会组织，蚂蚁社会的成员有分工，有相互的通信和信息传递。 2、自然优化蚁群在觅食过程中，在没有任何提示下总能找到从蚁巢到食物源之间的最短路径；当经过的路线上出现障碍物时，还能迅速找到新的最优路径。 3、信息正反馈蚂蚁在寻找食物时，在其经过的路径上释放信息素（外激素）。蚂蚁基本没有视觉，但能在小范围内察觉同类散发的信息素的轨迹，由此来决定何去何从，并倾向于朝着信息素强度高的方向移

2、动。 4、自催化行为某条路径上走过的蚂蚁越多，留下的信息素也越多（随时间蒸发一部分），后来蚂蚁选择该路径的概率也越高。 （二）算法的产生与发展 1、产生受蚁群觅食行为启发，意大利学者M.Dorigo于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群的新型智能优化算法“蚂蚁系统（Ant system,简称AS）”，并用该法求解旅行商问题，获得了较好的效果。 2、发展后来，提出者及许多研究者对该算法作了各种改进，将其应用于更为广泛的领域，如图着色问题、二次分配问题、工件排序问题、车辆路径问题、车间作业调度问题、网络路由问题、大规模集成电路设计等。近些年来，M.Dorigo等人把蚂蚁算法进一步

3、发展成一种通用的优化技术“蚁群优化（Ant Colony Optimization,简称ACO）”，并将所有符合ACO框架的算法称为“蚁群优化算法（ACO algorithm）”。 3、展望初步的研究结果已显示出ACO算法在求解复杂优化问题，特别是离散优化问题方面的优越性。虽然严格的理论基础尚未奠定，但从当前的应用效果来看，此算法具有光明的发展前景。（三）特点是一种基于多主体的智能算法，不是单个蚂蚁行动，而是多个蚂蚁同时搜索，具有分布式的协同优化机制。本质上属于随机搜索算法（概率算法），具有概率搜索的特征。是一种全局搜索算法，能够有效地避免局部最优。（四）优点求解问题的快速性由正反馈机制决定；

4、全局优化性由分布式计算决定，避免蚁群在寻优空间中过早收敛；有限时间内答案的合理性由贪婪式搜索模式决定，使能在搜索过程的早期就找到可以接受的较好解。 4、每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。 5、所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。 6、更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。 7、达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。（二）参数含义及符号蚂蚁数量；蚂蚁编号；时刻；城市数；城市 之间的

5、距离；启发式因子（能见度），反映蚂蚁由 城市 转移到城市 的启发程度；边 上的信息素量；（三）计算公式1、转移概率 计算公式：蚂蚁 下一步允许选择的城市集合。信息素的相对重要程度；启发式因子的相对重要程度；2、启发式因子计算公式：3、信息素计算公式正常数，蚂蚁 在本次周游中所走路径的长度。 当所有蚂蚁完成1次周游后，各路径上的信息素为：开始时，令（四）算法步骤1、初始化参数：开始时每条边的信息素量都相等。2、将各只蚂蚁放置各顶点，禁忌表为对应的顶点。3、取1只蚂蚁，计算转移概率 ，按轮盘赌的方式 选择下一个顶点，更新禁忌表，再计算概率，再选 择顶点，再更新禁忌表，直至遍历所有顶点1次。4、计算

6、该只蚂蚁留在各边的信息素量 ，该蚂蚁 死去。5、重复34，直至 只蚂蚁都周游完毕。6、计算各边的信息素增量 和信息素量 。7、记录本次迭代的路径，更新当前的最优路径，清空 禁忌表。8、判断是否达到预定的迭代步数，或者是否出现停滞 现象。若是，算法结束，输出当前最优路径；否， 转2，进行下一次迭代。三、算例5个点的货郎担问题 参数设置：最优解保留策略蚂蚁系统（带精英策略的蚂蚁系统ASelite） 蚁群系统（ACS） 最大-最小蚂蚁系统（MMAS） 基于优化排序的蚂蚁系统（ASrank）最优最差蚂蚁系统（BWAS） 一种新的自适应蚁群算法（AACA） 基于混合行为的蚁群算法（HBACA） 改 进

7、的蚂蚁算法四、改进的蚁群优化算法特点、状态转移规则伪随机比率规则 设 为常数， 为随机数，如果 ，则蚂蚁转移的下一座城市是使 取最大值的城市；若 ，仍按转移概率确定。、全局更新规则只有精英蚂蚁才允许释放 信息素，即只有全局最优解所属的边才增加 信息素。 、局部更新规则蚂蚁每次从城市 转移到 城市 后，边 上的信息素适当减少。 一般， 取值较大。（二）蚁群系统 规则和都是为了使搜索过程更具有指导性，即使蚂蚁的搜索主要集中在当前找出的最好解邻域内。规则则是为了使已选的边对后来的蚂蚁具有较小的影响力，以避免蚂蚁收敛到同一路径。（三）最大最小蚂蚁系统 关于 的取值，没有确定的方法，有的书例子中取为0.

8、01，10；有的书提出一个在最大值给定的情况下计算最小值的公式。1、每次迭代后，只对最优解所属路径上的信 息素更新。特点2、对每条边的信息素量限制在范围 内，目的是防止某一条路径上的信息素量远 大于其余路径，避免过早收敛于局部最优解。 （四）基于优化排序的蚂蚁系统特点：每次迭代完成后，蚂蚁所经路径由小到大排序，并根据路径长度赋予不同的权重，路径越短权重越大。信息素更新时对 考虑权重的影响。 特点：主要是修改了ACS中的全局更新公式，增加 对最差蚂蚁路径信息素的更新，对最差解进 行削弱，使信息素差异进一步增大。 （五）最优最差蚂蚁系统（六）一种新的自适应蚁群算法特点：将ACS中的状态转移规则改为

9、自适应伪随机 比率规则，动态调整转移概率，以避免出现 停滞现象。说明：在ACS的状态转移公式中， 是给定的常数；在AACA中， 是随平均节点分支数ANB而变化的变量。ANB较大，意味着下一步可选的城市较多， 也变大，表示选择信息素和距离最好的边的可能性增大；反之减小。（七）基于混合行为的蚁群算法特点：按蚂蚁的行为特征将蚂蚁分成4类，称为4个子蚁群，各子蚁群按各自的转移规则行动，搜索路径，每迭代一次，更新当前最优解，按最优路径长度更新各条边上的信息素，如此直至算法结束。 蚂蚁行为蚂蚁在前进过程中，用以决定其下一步移动到哪个状态的规则集合。 1、蚂蚁以随机方式选择下一步要到达的状态。2、蚂蚁以贪婪

10、方式选择下一步要到达的状态。3、蚂蚁按信息素强度选择下一步要到达的状态。4、蚂蚁按信息素强度和城市间距离选择下一步要到达的状态 。蚂蚁行为五、蚁群算法与遗传、模拟退火算法的比较实验结果表明：1、蚁群算法所找出的解的质量最高，遗传算法次之，模拟退火算法最低。2、蚁群算法的收敛速度最快，遗传算法次之，模拟退火算法最慢。蚁群算法之所以能够快速收敛到全局最优解，是因为该算法的个体之间不断进行信息交流和传递。单个个体容易收敛于局部最优，多个个体通过合作可以很快地收敛于解空间的最优解的附近。讨 论1、对已学过的算法作出某种改进。2、介绍自学的一种新的算法。3、查阅文献，介绍某算法在某领域的一个应用。4、应

11、用某算法解决一个实际问题。正常数，蚂蚁 在本次周游中所走路径的长度。 当所有蚂蚁完成1次周游后，各路径上的信息素为：开始时，令ktitabuk10AABCDE22220.470.0950.1180.315119.12.117BA,BCDE2220.5930.2370.1691.686CA,B,CDE220.670.331.0DA,B,C,DE21.01.0EA,B,C,D,E空集-ktitabuk30CCABDE22220.0690.620.2070.103911.13.222BC,BADE2220.7450.1490.1062.686AC,B,ADE220.2730.7270.917EC,B

12、,A,ED21.02.0DC,B,A,E,D空集-ktitabuk40DDABCE22220.0840.2110.2870.422119.12.367ED,EABC2220.5930.1690.2371.686AD,E,ABC220.830.171.2BD,E,A,BC21.01.0CD,E,A,B,C空集-ktitabuk50EEABCD22220.2710.0780.1090.543911.13.686DE,DABC2220.1460.3660.4881.367CE,D,CAB220.10.92.222BE,D,C,BA21.02.0AE,D,C,B,A空集-ABCDEA09.1+9.1+

13、1=19.21111.1+11.1+11.1+1=34.3B11.1+11.1+11.1+1=34.309.1+9.1+1=19.211C111.1+11.1+11.1+1=34.309.1+9.1+1=19.21D1111.1+11.1+11.1+1=34.309.1+9.1+1=19.2E9.1+9.1+1=19.21111.1+11.1+11.1+1=34.30信息素矩阵ktitabuk15AABCDE19.21134.30.450.0050.0060.5380.76911.121.258EA,EBCD1134.30.0040.0060.990.4934.643DA,E,DBC134.3

14、0.0210.9790.5811.683CA,E,D,CB34.31.00.8834.3BA,E,D,C,B空集-ktitabuk25BBACDE34.319.2110.7750.2170.0050.003911.144.24AB,ACDE1134.30.0090.0110.9811.66EB,A,ECD134.30.0060.99434.5DB,A,E,DC34.31.011.43CB,A,E,D,C空集-ktitabuk35CCABDE134.319.210.0030.8370.1560.004911.140.98BC,BADE34.3110.990.0060.00434.64AC,B,A

15、DE134.30.0110.98911.56EC,B,A,ED34.31.034.3DC,B,A,E,D空集-ktitabuk45DDABCE1134.319.20.0050.0120.5350.449911.121.38CD,CABE134.310.0030.9920.00534.58BD,C,BAE34.310.9960.00434.44AD,C,B,AE34.31.011.43ED,C,B,A,E空集-ktitabuk55EEABCD19.21134.30.2170.0030.0050.775911.144.24DE,DABC1134.30.0080.0210.97111.78CE,D,

16、CAB134.30.0030.99734.41BE,D,C,BA34.31.034.3AE,D,C,B,A空集- 至此出现了停滞现象，算法结束。 已找到最优解：AEDCBA,目标函数值为9。 试用蚁群算法求解6个点的对称TSP。已知资料如下。ABCDEFA05756217870B5702365161C5620355160D21363506868E78515168013F70616068130练 习参数设置：令开始时，令已 知 资 料 表ABCDEA021083B10257C91036D104302E27510EABCD参数设置：算 例 正常数，蚂蚁 在本次周游中所走路径的长度。 当所有蚂蚁完成

17、1次周游后，各路径上的信息素为：开始时，令ktitabuk10AABCDE22220.470.0950.1180.315119.12.117BA,BCDE2220.5930.2370.1691.686CA,B,CDE220.670.331.0DA,B,C,DE21.01.0EA,B,C,D,E空集-ktitabuk20BBACDE22220.540.270.110.08911.13.686AB,ACDE2220.180.220.601.117EB,A,ECD220.170.832.4DB,A,E,DC21.00.667CB,A,E,D,C空集-ktitabuk30CCABDE22220.069

18、0.620.2070.103911.13.222BC,BADE2220.7450.1490.1062.686AC,B,ADE220.2730.7270.917EC,B,A,ED21.02.0DC,B,A,E,D空集-ktitabuk40DDABCE22220.0840.2110.2870.422119.12.367ED,EABC2220.5930.1690.2371.686AD,E,ABC220.830.171.2BD,E,A,BC21.01.0CD,E,A,B,C空集-ktitabuk50EEABCD22220.2710.0780.1090.543911.13.686DE,DABC2220.

19、1460.3660.4881.367CE,D,CAB220.10.92.222BE,D,C,BA21.02.0AE,D,C,B,A空集-ABCDEA09.1+9.1+1=19.21111.1+11.1+11.1+1=34.3B11.1+11.1+11.1+1=34.309.1+9.1+1=19.211C111.1+11.1+11.1+1=34.309.1+9.1+1=19.21D1111.1+11.1+11.1+1=34.309.1+9.1+1=19.2E9.1+9.1+1=19.21111.1+11.1+11.1+1=34.30信息素矩阵ktitabuk15AABCDE19.21134.30.450.0050.0060.5380.76911.121.258EA,EBCD1134.30.0040.0060.990.4934.643DA,E,DBC134.30.0210.9790.5811.683CA,E,D,CB34.31.00.8834.3BA,E,D,C,B空集-ktitabuk25BBACDE34.319.2110.7750.2170.0050.003911.144.24AB,ACDE1134.30.0090.0110.9811.66EB,A,EC