基于挥发系数的自适应蚁群算法

蚁群算法综述摘要：群集智能作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点, 其理论和应用得到了很大的发展。

作为群集智能的代表方法之一,蚁群算法ACO (Ant Colony Optimization, 简称ACO) 以其实现简单、正反馈、分布式的优点得到广泛的应用。

蚁群算法是由意大利学者M. Dorigo 提出的一种仿生学算法。

本文主要讨论了蚁群算法的改进及其应用。

在第一章里介绍了蚁群算法的思想起源及研究现状。

第二章详细的介绍了基本蚁群算法的原理及模型建立，并简要介绍了几种改进的蚁群优化算法。

第三章讨论了蚁群算法的最新进展和发展趋势展望。

关键词：群集智能，蚁群算法，优化问题1 引言1.1 概述人类的知识都来自于对自然界的理解和感悟，如天上的闪电，流淌的河流，挺拔的高山，汪洋的大海，人们从中学会了生存，学会了征服自然和利用自然。

自然界中也存在着很多奇特的现象，水中的鱼儿在发现食物时总能成群结队，天上的鸟儿在迁徙时也是组成很多复杂的阵型，蚂蚁在发现食物时总能找到一条最短的路径。

无论鱼儿，飞鸟或是蜜蜂，蚂蚁他们都有一个共同的特点好像有一种无形的力量将群体中的每个个体组织起来，形成一个统一的整体。

看似庞杂的种群却又有着莫大的智慧，让他们能够完成一个个体所无法完成的使命。

整个群体好像一个社会，形成一个有机整体，这个整体对单个个体要求不高，诸多个体组合起来数量庞大，却极具协调性和统一性，这就是群智能。

群智能算法是利用其个体数量上的优势来弥补单个个体的功能缺陷，使整个群体看起来拥有了个体所无法企及的能力和智慧。

单个个体在探索过程的开始都是处于一种盲目的杂乱的工作状态，因此这些个体所能找到的最优解，对于群体而言却并非是最优的而且这些解也都是无规则的，随着越来越多的个体不断探索，单个个体受到其他成员的影响，大量的个体却逐渐趋向于一个或一条最优的路线，原本杂乱的群体渐渐呈现一种一致性，这样整个群体就具有了寻找最优解的能力。

蚁群算法（ACO）解决TSP问题⼀、蚁群算法1.基本原理蚁群算法（Ant Colony Optimization，ACO）是⼀种基于种群寻优的启发式搜索算法，有意⼤利学者M.Dorigo等⼈于1991年⾸先提出。

该算法受到⾃然界真实蚁群集体在觅⾷过程中⾏为的启发，利⽤真实蚁群通过个体间的信息传递、搜索从蚁⽳到⾷物间的最短路径等集体寻优特征，来解决⼀些离散系统优化中的困难问题。

经过观察发现，蚂蚁在寻找⾷物的过程中，会在它所经过的路径上留下⼀种被称为信息素的化学物质，信息素能够沉积在路径上，并且随着时间逐步挥发。

在蚂蚁的觅⾷过程中，同⼀蚁群中的其他蚂蚁能够感知到这种物质的存在及其强度，后续的蚂蚁会根据信息素浓度的⾼低来选择⾃⼰的⾏动⽅向，蚂蚁总会倾向于向信息素浓度⾼的⽅向⾏进，⽽蚂蚁在⾏进过程中留下的信息素⼜会对原有的信息素浓度予以加强，因此，经过蚂蚁越多的路径上的信息素浓度会越强，⽽后续的蚂蚁选择该路径的可能性就越⼤。

通常在单位时间内，越短的路径会被越多的蚂蚁所访问，该路径上的信息素强度也越来越强，因此，后续的蚂蚁选择该短路径的概率也就越⼤。

经过⼀段时间的搜索后，所有的蚂蚁都将选择这条最短的路径，也就是说，当蚁巢与⾷物之间存在多条路径时，整个蚁群能够通过搜索蚂蚁个体留下的信息素痕迹，寻找到蚁巢和⾷物之间的最短路径。

蚁群算法中，蚂蚁个体作为每⼀个优化问题的可⾏解。

⾸先随机⽣成初始种群，包括确定解的个数、信息素挥发系数、构造解的结构等。

然后构造蚁群算法所特有的信息素矩阵每只妈蚁执⾏蚂蚊移动算⼦后，对整个群体的蚂蚁做⼀评价，记录最优的蚂蚁。

之后算法根据信息素更新算⼦更新信息素矩阵，⾄此种群的⼀次选代过程完成。

整个蚂蚁群体执⾏⼀定次数的选代后退出循环、输出最优解。

2.术语介绍（1）蚂蚁个体。

每只蚂蚁称为⼀个单独的个体，在算法中作为⼀个问题的解。

（2）蚂蚁群体。

⼀定数量的蚂蚁个体组合在⼀起构成⼀个群体，蚂蚁是群体的基本单位。

改进的蚁群算法求解置换流水车间调度问题张丽萍【摘要】In order to avoid the shortcomings of ant algorithm for solving permutation flow shop scheduling problem that easily fall into local best situation and long calculation time, in this paper, an improved Max-MinAnt System (MMAS)algorithm which apply Nawaz-Enscore-Ham ( NEH ) heuristic algorithm to enhance the quality of the initial solutions and further improve the search capabil-ities through regulation of adaptive strategies is proposed . Finally we use the proposed algorithm to solve Taillard benchmarks set . Compared with other approaches , the experimental results show the effectiveness of the proposed algorithm .%针对蚂蚁算法在求解置换流水车间调度问题时易陷入局部最优以及计算时间较长的缺点，对最大最小蚂蚁系统( MMAS )进行了改进。

在该算法中，采用 NEH 启发式算法提高初始解质量，并通过自适应的调节策略进一步提高蚁群算法的搜索能力。

运用提出的混合算法求解 Taillard 基准测试集，并将测试结果与其他算法进行比较，验证了该调度算法的有效性。

基于信息素更新和挥发因子调整的改进蚁群算法孟晓琳;黄天民;陈尚云【摘要】为了改进基本蚁群算法容易导致算法停滞、陷入局部最优解和收敛速度较慢的问题,提出一种改进的蚁群算法,主要是将信息素局部更新和全局更新结合,增加各路径的被选择机会,避免算法停滞;另外,由于信息素挥发因子ρ的大小直接关系到算法的全局搜索能力和收敛速度,提出在算法的初期、中期和后期分别设置不同的ρ,以此增加算法的全局搜索能力,又能在一定程度上加快算法的收敛.改进算法的性能在Oliver 30和att48问题上得到验证,本方法与基本蚁群算法相比要更优,收敛速度更快,体现了此种改进的有效性.【期刊名称】《成都大学学报（自然科学版）》【年(卷),期】2015(034)001【总页数】4页(P48-51)【关键词】蚁群算法;信息素更新;挥发因子【作者】孟晓琳;黄天民;陈尚云【作者单位】西南交通大学数学学院,四川成都611756;西南交通大学数学学院,四川成都611756;西南交通大学数学学院,四川成都611756【正文语种】中文【中图分类】TP301.620世纪90年代，学者Macro Dorigo首先提出了蚁群算法，其迅速成为启发式算法研究的热点，它在解决传统算法无法解决的组合优化和NP等难题上能够取得很好的效果，并且具有解决复杂问题的能力.同时，蚁群算法的鲁棒性较强，能进行分布式计算，同其他优化算法结合容易，而且算法没有复杂的数学操作，对软硬件要求不高，但是该算法搜索时间较长，很容易陷入局部最优解[1-2].为了克服蚁群算法的缺点，许多学者对其进行了研究，并提出了相应的改进算法[3-6].在此基础上，本研究提出一种将信息素局部更新和全局更新相结合，并对挥发因子ρ进行分段设置，以此来增强蚁群算法的全局搜索能力，并采用TSP实例对算法进行验证，证明了本改进算法的有效性.设m表示蚂蚁的数量，dij(i,j=1,2,…，n)表示城市i、j之间的距离，bi(t)表示t时刻位于城市i的蚂蚁个数，则，bi(t),τij(t)表示t时刻在i和j连线上残留的信息素，初始时刻，各路径上的信息素浓度相等，设τij(0)=C，C为常数.在搜索过程中，每只蚂蚁根据状态转移概率来判断路径的选择，t时刻蚂蚁k由城市i到j的状态转移概率用(t)来表示，式中，allowedk表示蚂蚁k下一步允许选择的城市，α表示路径上的信息量对蚂蚁选择路径的影响程度，ηij(k)表示启发因子，即由城市i转移到j的期望程度，β表示启发因子对蚂蚁选择路径的影响程度[3].每只蚂蚁对路径做出选择后将移动至下一城市，并且将当前蚂蚁所在城市放入禁忌表tab uk中，当禁忌表包含所有城市时，表示已经完成一次迭代，计算每只蚂蚁所走的路径并保留最短路径.路径上的信息素会随着时间的推移而渐渐减弱，经过n个时刻，路径ij的信息素将按照式(2)进行更新，式中，ρ表示信息素挥发因子，Δτij(t)表示本次迭代中路径ij上的信息素增量，(t)表示第k只蚂蚁在本次迭代中留在路径ij上的信息素，其表达式为，式中，Q表示常数，Lk表示第k只蚂蚁在本次迭代中走过的路径长度[4].本研究对基本蚁群算法做了2点改进：其一，针对基本蚁群算法容易出现早熟和停滞现象，进行了信息素更新的改进；其二，为了使算法的全局搜索能力和收敛速度均得到提高，进行了信息素挥发因子的改进.2.1 信息素的局部更新与全局更新在基本蚁群算法中，信息素的更新方式有可能导致这样的现象：新的最优路径尚未出现时，当前最优路径上的信息素就会按照信息素更新公式不断增多.这使得当前最优路径上的信息素可能会因为过度增多而大于新的最优路径上信息素，最终导致算法停滞.对此，本研究提出一种局部更新和全局更新信息素结合的方法，其思路是：对于第k只蚂蚁，它每经过一条路径ij，设经过该路径的时间为n，则在时刻t+n，该路径上的信息素会用式(4)进行更新.τij(t+n)=(1-ρ)τij(t)+ρτij(0)式中，ρ为信息素挥发因子；τij(0)为信息素初始值.当蚂蚁k经过(i,j)时，式(4)就会减小该路径上的信息素，降低其他蚂蚁选中该路径的概率，增加探索其他边的机会.相较于基本蚁群算法，此改进可以避免因某一路径信息素累计量过大而导致算法停滞.同时，每次迭代结束以后，对于当前最优路径上的信息素用式(5)进行全局动态更新，式中，Δτij(t)为全局更新信息素增量，LNC为当前迭代即第NC次迭代的最优路径长度，Lbest为当前最优路径长度.此改进有利于蚂蚁根据当前最优路径动态地调整信息素，随着迭代进行，有更优路径出现后，LNC和Lbest的差值会逐渐减小.相应地，信息素增量减小直至0，此时，当前最优路径上只进行信息素蒸发.与基本蚁群算法相比，这样能使当前最优路径上的信息素浓度更为突出，但又不至于造成算法停滞，使当前最优路径的变化更快地反映在信息素分布上.2.2 分段调整信息素挥发因子蚁群算法中，信息素挥发因子ρ的大小直接关系到算法的全局搜索能力和收敛速度，基本蚁群算法中的ρ是(0，1)区间的某个固定值.当ρ过小时，已经被搜索过的路径被再次选择的可能性过大，容易出现局部收敛；反之，当ρ过大时，虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低[6].对此，本研究提出一种分段调整信息素挥发因子的方法，即随着迭代次数的增加，将算法分为初期、中期和后期.在算法初期，将ρ设置为较大的值，这样可以使算法的全局搜索能力增强，在中期和后期适当减小ρ的值，使得算法可以较快地收敛到最优解.这样既增加了算法的全局搜索能力，又可以在一定程度上加快算法的收敛.具体规则为，其中，NC表示算法的迭代次数，NC-max表示最大迭代次数.在整个迭代过程的前四分之一，将ρ取值为最接近1的值0.9，可以在初始阶段提高算法的全局搜索能力；然后，将ρ设置为中间数值0.5，使算法既不至于陷入局部收敛，又能加快收敛速度；到了迭代过程的后四分之一，将ρ值取为0.1，因为此时的搜索结果已经基本确定，适时可以加快算法的收敛速度.2.3 算法实现根据以上的改进思路，改进后的算法实现的具体步骤为：1)参数初始化α，β，Q，NC-max，m,令迭代计数器NC=1.2)随机选择每只蚂蚁的初始位置，初始化禁忌表tk，按照式(6)设置ρ的值.3)按照式(1)选择路径，将所选城市添加到tk中，并按照式(4)更新局部信息素.4)若tk未满则转至步骤3)，若已满，得出蚂蚁此次的最优路径长度LNC，并更新Lbest的值.5)对当前的最优路径按照式(5)更新全局信息素，清空tk.6)若NC<NC-max，则NC=NC+1，并转至步骤2)，开始新一次的迭代，否则算法结束，输出最优路径长度Lbest.在仿真实验中，选用TSP LIB中的Oliver 30和att 48作为仿真算例，以验证本研究提出的改进算法性能，并与基本蚁群算法求解Oliver30 TSP和att48 TSP进行比较.基本蚁群算法采用的参数为：α=1，β=2，ρ=0.5，Q=100，NC-max=200，m=30[7]；本研究提出的改进算法的参数为：α=1，β=2，Q=100，NC-max=200，m=30.对2种算法分别测试20次，其结果如表1、2所示.从表1、2可以看出，经过20次的测试，采用本基本蚁群算法改进的算法求解Oliver 30和att 48所得最优值、最差值和平均值与基本蚁群算法相比均有所改善. 另外，在收敛速度上，本研究算法在150代以内几乎可收敛到最优值，但基本蚁群算法在180代到200代依然存在多次尚未收敛的情况.2种算法的最短距离及收敛情况如图1、2、3、4所示.图1和图2分别是基本蚁群算法测试att48 TSP问题的某一次最短距离和收敛情况.图3和图4分别是改进算法测试att48 TSP问题的某一次最短距离和收敛情况.由实验结果可见，随机选择的某一次实验结果中，基本蚁群算法测试att 48的最短距离是35 701.8073 km，收敛速度较慢，在迭代180次之后仍未收敛；改进算法测试att 48的最短距离是34 751.3419 km，收敛速度明显提升，在迭代150次左右达到最优.此表明，在求解Oliver 30和att 48问题上，本改进算法在求最优解和收敛速度上有明显优势.本研究通过引入信息素局部更新和全局更新相结合，以及分段式更新信息素挥发因子的方法，对基本蚁群算法进行了改进，达到了扩大解的搜索空间、兼顾搜索速度和搜索能力的目的.改进算法的性能在Oliver 30和att48问题上已经得到验证，但对于更大规模的数据，改进的算法是否能够使用还有待于进一步的研究.【相关文献】[1]王运涛,姚砺,毛力.基于混合行为的自适应蚁群算法[J].计算机仿真，2009，26(12)：151-153.[2]段海滨,王道波,于秀芬.蚁群算法的研究现状及其展望[J].中国工程科学，2007，9(2)：98-102.[3]方霞,席金菊.基于变异和启发式选择的蚁群优化算法[J].计算机工程与应用，2013，49(24)：24-27.[4]李成兵,郭瑞雪,李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用，2014，34(S1):131-132，165.[5]王沛栋.改进蚁群算法及在路径规划问题的应用研究[D].青岛：中国海洋大学，2012.[6]赵伟,蔡兴盛,曲慧雁.一种基于惩罚函数和新信息素更新方式的蚁群算法[J].计算机工程与科学，2013，35(3):103-107.[7]叶仕通,万智萍.一种基于改进全局信息素更新效率的蚁群算法及仿真[J].计算机应用与软件，2014，31(1):176-179.。