蚁群优化算法

蚁群优化算法ACO一、蚁群算法的背景信息蚁群优化算法(ACO)是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者DorigoM等人于1991年首先提出，之后，又系统研究了蚁群算法的基本原理和数学模型，并结合TSP优化问题与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较，为蚁群算法的发展奠定了基础，并引起了全世界学者的关注与研究蚁群算法是一种基于种群的启发式仿生进化系统。蚁群算法最早成功应用于解决著名的旅行商问题(TSP)，该算法采用了分布式正反馈并行计算机制，易于与其他方法结合，而且具有较强的鲁棒性。二、蚁群算法的原理[1]蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。基本的ACO模型由下面三个公式描述：式（2-1）、式(2-2)和式(2-3)中：m为蚂蚁个数；n为迭代次数；i为蚂蚁所在位置；j为蚂蚁可以到达的置；为蚂蚁可以到达位置的集合；为启发性信息，这里为由i到j的路径的能见度，即；为目标函数，这里为两点间欧氏(Euclidean)距离；为由i到j的路径的信息素强度；为蚂蚁k由i到j的路径上留下的信息素数量；为路径权；为启发性信息的权；为路径上信息素数量的蒸发系数；Q为信息素质量系数；为蚂蚁k从位置i移动到位置j的转移概率。三、改进的蚁群算法[3]蚁群算法具有如下一些优点：①通用性较强，能够解决很多可以转换为连通图结构的路径优化问题；②同时具有正负反馈的特点，通过正反馈特点利用局部解构造全局解，通过负反馈特点也就是信息素的挥发来避免算法陷入局部最优；③有间接通讯和自组织的特点，蚂蚁之间并没有直接联系，而是通过路径上的信息素来进行间接的信息传递，自组织性使得群体的力量能够解决问题。但是，基本蚁群算法也存在一些缺点：①从蚁群算法的复杂度来看，该算法与其他算法相比，所需要的搜索时间较长；②该算法在搜索进行到一定程度以后，容易出现所有蚂蚁所发现的解完全一致这种“停滞现象”，使得搜索空间受到限制3.1基于遗传学的改进蚁群算法研究该文献[2]提出的算法弥补了基本蚁群算法中“容易陷入停滞状态”和“盲目随机搜索”的不足。文献中提出的解决办法是在每一次迭代搜索后，都把当前解和最优解进行交叉变异,这样既能搜索更大的解空间，又能使系统陷入局部最优后跳出停滞状态。这种基于遗传学的蚁群算法（G-蚁群算法）的基本思想是在以蚁群算法为主体的基础上引入遗传算法的思想，目的是让蚁群算法经过迭代产生遗传算法所需的初始种群数据，提高种群数据的多样性。然后，遗传算法经过选择、交叉和变异操作,将处理后的数据交由蚁群算法模块进行判断处理，若满足结束条件则退出系统，否则重新进行迭代操作。该文献中的交叉操作采用了Davis提出的OX交叉算子，即按照交叉概率Pc进行交叉操作，通过一个亲体中挑选出的子序列路径作为后代相对位置的子序列，变异操作以变异概率Pm执行变异操作，在子代序列路径中随机选择两点进行变异操作，在交叉变异操作结束后，判断当前解是否满足收敛条件，若满足收敛条件则更新当前最优解，返回蚁群算法程序,执行下一次的迭代操作。若不满足收敛条件则继续进行遗传算法的交叉变异操作。3.2蚁群系统（AntSystem，AS）蚁群系统是Gambardella等人于1996年提出的一种修正的蚁群算法。该算法的基本思想是：（1）引入一个新的常量，其取值范围为，在蚂蚁k每次选择路径之前先产生一个随机数，且有，有了这个随机数之后，蚂蚁k的路径将会按照下面的规则进行。在公式中，假设蚂蚁k当前所在的节点为i，那么蚂蚁k由节点i向点节j移动遵循的规则用公式PP表示如下：（2）对全局信息素更新策略的改进按照最短路径更新全局信息素，其具体更新方法如下：式（3-2）中其中为信息素挥发参数，；式（3-3）中，表示本次循环之后路径(i，j)上的信息素增量；表示到目前为止找出的全局最优路径。（3）对局部信息素更新策略也进行了改进式（3-4）表示蚂蚁从节点i转移到节点j后，其经过的路径(i,j)上的信息素更新的方式。其中，为常数，表示算法初始化时路径上的信息素浓度；为可调参数，。3.3精英蚁群系统（ElitistAntSystem，EAS）精英蚁群系统是对AS的第一次改进，是学者们为了解决基本蚁群算法求解大规模问题时收敛速度慢、不容易产生优化解而提出的。该算法具体的改进策略如:式（3-6）表示信息素增加强度定义方法，和以前的相同，是调整最优解的影响权重的参数，适当的设置该参数的值可以提高算法的性能；式（3-7）表示精英蚂蚁给路径（i，j）上所增加的信息素量。3.4最大最小蚁群系统（Max-MinAntSystem，MMAS）“最大最小蚁群系统”是德国学者ThomasStutzle等提出的另一种通用性较强的改进的蚁群算法。该算法相比基本蚁群算法作了如下一些改进：（1）一次循环结束后，并不是所有的蚂蚁都进行信息素更新，而是只对一只蚂蚁的信息素进行更新。这只蚂蚁只能是两类蚂蚁：在当前循环中找到最优解的蚂蚁或者是可能发现已知最优路径的蚂蚁。其信息素更新依照如下规则：式（3-9）中根据进行信息素更新的蚂蚁的类别可以是已知的最优解的路径长度或者是本次循环中的最优解的路径长度。（2）信息素浓度的限制。为了防止某条路径上的信息素出现大或者过小的极端情况，设定信息素浓度区间为。通过这种方式使得在某条路径上的信息素浓度增大到超过区间上限或者减小到低于区间下限时，算法采用强制手段对其进行调整，以此提高算法的有效性。（3）为了在开始吸引更多的蚂蚁进行搜索，信息素浓度初始化的值不再是一个常数，而是设置为区间的上限，并且选定一个较小的挥发系数，以此来得到更多的搜索路径。3.5排序蚁群系统（Rank-BasedAntSystem，ASrank）排序蚁群系统引入了遗传算法中排序的观念，其改进的基本原理是：每只蚂蚁释放的信息素挥发程度受到它们各自的等级的影响，按照各自等级的高低来决定挥发程度的高低。当每只蚂蚁都生成一条路径以后，根据其各自的路径长度进行由短到长的排序，路径长度越短的代表等级越高，反之越低。因此，在更新信息素时，并不是考虑所有的蚂蚁，只考虑比较“优秀”的只蚂蚁（表示蚂蚁的排名）。式（3-11）中，按照式（3-7）的方式计算；式（3-12）中，表示排名在第位的蚂蚁环游的长度。3.6几种改进的蚁群算法的比较（1）对比基本蚁群算法（ACA），AS算法、EAS算法、MMAS算法以及ASrank算法的共同之处就是它们都允许最优解所在的路径上的信息素进行加强，有效地利用了最优解，但是这样产生了一个弊端就是可能会导致搜索中出现停滞现象。（2）针对避免停滞现象，几种改进算法采取的策略不同。蚁群系统通过增加局部信息素的更新来减少路径上的信息素量，以此让后面的蚂蚁选择这条路径的可能性减小；在MMAS算法中，采用的是给定信息素量的上下限，以此使得路径上的信息素量不会小于下限（某一最小值），也不会超过上限（某一最大值），避免所有蚂蚁选择同一条路径，也就是避免了搜索中出现停滞现象。四、ACO应用进展及发展趋势4.1应用的进展[7]自从ACO在一些经典的组合规划问题如TSP和QAP等NP难的组合优化问题上取得成功以来,目前已陆续渗透到许多新的实际的工程领域中。(1)在各种工程和工业生产中的应用[4,5]。例如采用ACO的思想来求解大规模集成电路综合布线问题。在布线过程中，各个引脚对蚂蚁的引力可根据引力函数来计算。各个线网agent根据启发策略，像蚁群一样在开关盒网格上爬行，所经之处便布上1条金属线，历经1个线网的所有引脚之后，线网便布通了。(2)ACO在各种实际规划问题中的应用。例如在机器人路径规划中的应用[6]。机器人作为一种智能体，在复杂工作环境下的路径规划问题、多机器人之间的协作策略问题，在很大程度上类似于蚂蚁觅食优选路径以及蚂蚁群体中个体之间通过信息素形成协作。路径规划算法是实现机器人控制和导航的基础之一，试验证明ACO解决该问题有很大的优越性。另外，ACO在动态优化组合问题中也有应用，具体是在有向连接的网络路由和无连接网络系统路由中的应用。其他应用还包括蚂蚁人工神经网络、车辆路线问题（VehicleRoutineProb-lem,VRP）、在图像处理和模式识别领域的应用等等。4.2存在的问题[8]蚁群算法的研究成果令人瞩目，但作为一种较新的理论，它依然存在一些问题。(1)对于大规模组合优化问题，算法的计算时间而且复杂。由于蚁群算法的时间复杂度是，因此在处理较大规模的组合优化问题时，运算量较大，时间较长。(2)算法容易在某个或某些局部最优解的邻域附近发生停滞现象，造成早熟收敛，即搜索进行到一定程度后，所有蚂蚁发现的解完全一致，不能继续对解空间进一步搜索，不利于发现全局最优解。(3)不能较好的解决连续域问题。(4)由于蚁群算法中蚂蚁个体的运动过程的随机性，当群体规模设置较大时，很难在较短时间内从杂乱无章的路径中找出一条较好的路径。(5)信息素更新策略，路径搜索策略和最优解保留策略都带有经验性，没有经过严格的理论论证。因此基本蚁群算法的求解效率不高、收敛性较差、求解结果具有较大的分散性。4.3发展趋势随着蚁群算法在工程实践中应用的深入和系统复杂性的增加，需要处理的数据量也越来越大，这些问题的影响日益突出，使得单纯一到两种智能方法往往不能很好的解决问题。由于蚁群算法易与其他进化算法或者局部搜索算法结合。所以如何根据实际情况融合多种智能方法必将成为今后蚁群算法新的研究热点。目前，蚁群算法的研究大多集中在算法、模型的更新,以及软件的开发上，所处理的数据也都是静态的。硬件的运行速度要高于软件，如何利用硬件的优势，利用DSP，FPGA和PLC等硬件实现蚁群算法，并使它能够应用于实时系统将是以后研究的一个方向。参考文献[1]吴庆洪,张颖,马宗民.蚁群算法综述[A].2011.[2]张怀锋,宋顺林.基于遗传学的改进蚁群算法研究[M].2011.[3]曾云.基于改进蚁群算法的物流配送路径优化研究[D].北京:北京物资学院,2012.[4]庄昌文,范明钰,李春辉,虞厥邦.基于协同工作方式的一种蚁群布线系统[J].半导体学报,1999,20(5):400-406.[5]COELLOCAC,GUTIERREZRLZ,GARCIABM,etal.AutomatedDesignofCombinationalLogicCircuitsUsingtheAntSystem[J].EngineeringOptimization,2002,34(2):109-127[6]樊晓平,罗熊,易晟,张航.复杂环境下基于蚁群优化算法的机器人路径规划[J].控制与决策,2004,19(2):166-170.[7]叶志伟,周欣,夏彬.蚁群算法研究应用现状与展望[A].2010.[8]戴宏发,张源原,孙国强,刘成亮.蚁群算法研究现状及发展[A].2011