蚁群优化算法

蚁群优化算法AntColonyOptimization蚁群优化算法蚁群优化算法简介一蚂蚁系统二蚁群优化算法的改进版本三蚁群优化算法相关应用四ACO是一种全局最优化搜索方法，解决典型组合优化问题具有明显的优越性，具有鲁棒性强、全局搜索、并行分布式计算、易于其他算法结合的优点。蚁群优化算法（ACO）由Dorigo（多里格）等人于1991年提出，是模拟自然界真实蚂蚁觅食过程的一种随机搜素算法。1.1基本原理提出性质1.1基本原理A（1）蚂蚁没有发育完全的视觉感知系统，其在寻找食物的过程中是如何选择路径的呢？（2）蚂蚁往往像军队般有纪律、有秩序地搬运食物，它们通过什么方式进行群体间的交流协作呢？信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内间接通信的物质。蚂蚁随机选择路径，但是能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向前进。信息素1.1基本原理双桥实验蚁穴食物源（a）两个路具有同样的长度自身催化（正反馈）过程1.起初两条分支上不存在信息素，蚂蚁以相同的概率进行选择。2.随机波动的出现，选择某一条分支的蚂蚁数量可能比另外一条多。3.实验最终结果：所有的蚂蚁都会选择同一分支。1.1基本原理双桥实验（b）两条分支具有不同长度1.起初两条分支上不存在信息素，蚂蚁随机选择一条路径。2.短分支上的信息素积累速度比长分支的快。3.实验最终结果：所有的蚂蚁都会选择较短的分支。4.有很小比例的蚂蚁会选择较长的分支。路径探索1.1基本理论蚁穴食物源（c）30分钟后添加短分支30分钟后双桥实验1.实验最终结果：除了极少的蚂蚁选择较短的分支以外，整个群体几乎都困在较长的分支上。2.长分支上的信息素浓度高，而信息素的蒸发速度过于缓慢。1.1基本理论双桥实验总结1选择路径是一个概率随机过程，启发式信息多以及信息浓度大的路径被选中概率更大。2信息素会不断的蒸发。3路径探索也是必需的，否则容易陷入局部最优。1.1基本理论蚁群觅食现象蚁群优化算法蚁群搜索空间的一组有效解（种群规模m）觅食空间问题的搜索空间（问题的规模、解的维数n）信息素信息素浓度变量蚁巢到食物的一条路径一个有效解找到的最短路问题的最优解蚁群觅食现象和蚁群优化算法的基本定义对照表2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为1.2研究进展历史进展1.2研究进展算法进展蚂蚁系统(AS)1991年0k0k基于排列蚂蚁系统1997年rankAS蚁群系统(ACS)1997年连续蚁群(CACO)2000年超立方体AS(HC-ACO)2001年连续正交蚁群(COAC)2008年精华蚂蚁系统(EAS)1991年最大最小蚂蚁系统(EAS)1996年1.2研究进展理论进展总结1.收敛性证明。一些性能优越的ACO算法（MMAS和ACS）不管有没有使用局部搜素，都是值收敛的。2.将ACO纳入了基于模型的搜索框架中。趋势1.利用ACO算法去解决更为复杂的优化问题，例如：动态问题、随机问题、多目标问题。2、ACO算法的高效并行执行。3.更理论化的理解和刻画ACO算法在求解问题时的行为。4.与其他算法结合（粒子群算法）。蚁群优化算法蚁群优化算法简介一蚂蚁系统二蚁群优化算法的改进版本三蚁群优化算法相关应用四2.1TSP问题问题简述：已知有个城市的集合，任意两个城市之间均有路径连接，表示城市与之间的距离。旅行商问题就是需要寻找这样的一中周游方案：周游路线从某个城市出发，经过每个城市一次且仅一次，最终回到出发城市，使得周游的路线总长度最短。nn12,,,nCcccL,1,2,,ijdijnL第一个ACO——蚂蚁系统，就是以NP难的TSP问题作为应用实例提出的。2.2贪婪算法贪婪算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。基本理论312354512242ijWdP87页，四个城市间的距离矩阵如下：用贪婪算法求解：例如从城市A出发得ACDBA路径长度为：1+2+4+3=102.3蚂蚁系统理论AS系统三个版本：1.蚂蚁圈2.蚂蚁数量3.蚂蚁密度ij/kij0,kiiQd，第只蚂蚁从城市访问城市其他kij0,kiiQ，第只蚂蚁从城市访问城市其他/kij0,kkiiQL，第只蚂蚁从城市访问城市其他其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度。d为城市间的距离。信息素更新方式2.3蚂蚁系统理论AS算法（蚂蚁圈版本）对TSP的求解流程主要有两大步骤：路径构建和信息素更新1.路径构建定义5.1AS中的随机比例规则：对每只蚂蚁k，路径记忆向量按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在的城市为i，则其选择城市j作为下一个访问对象的概率为：KR(i,j)(i,j),j(i,u)(i,u)(i,j)0,kkkijuJiJiP其他其中，表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列中的城市集合。是一个启发式信息，通常由直接计算。表示边上的信息量,ij,=1/dijijkJikR,ij,ij2.3蚂蚁系统理论1.路径构建(i,j)(i,j),j(i,u)(i,u)(i,j)0,kkkijuJiJiP其他由公式知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重。时算法演变成了传统的随机贪婪算法；当蚂蚁完全只根据信息素浓度确定路径，算法快速收敛，构建出的最优路径与实际目标有较大的差异。实验表明：设置，比较合适。=0=0=1=25:2.3蚂蚁系统理论2.信息素更新1,(1),,mkkijijij初始化时：0=/nnmC1,j,0kkkCiRij否则m是蚂蚁的个数，是由贪婪算法构造的路径的长度。nnC是信息素的蒸发率，规定通常设置为是第k只蚂蚁在它经过的边上释放的信息素量；表示路径的长度，它是中所有边的长度和。kR01=0.5,kijkC2.3蚂蚁系统理论参数设置参数参数的意义蚂蚁数目m影响着算法的搜素能力和计算量信息素挥发因子影响蚂蚁个体之间相互影响的强弱，关系到算法的全局搜索能力和收敛速度初始信息素量决定算法在初始化阶段的探索能力，影响算法的收敛速度02.3蚂蚁系统理论参数设置1蚂蚁数目过多，迭代的计算量大且被搜索过的路径上信息素变化比较平均，此时全局搜索能力增强，但收敛速度减慢2蚂蚁数目过少时，算法的探索能力变差，容易出现早熟现象。特别是当问题的规模很大时，算法的全局寻优能力会十分糟糕3在用蚂蚁系统、精华蚂蚁系统、基于排列的蚂蚁系统和最大最小蚂蚁系统求解TSP时，m取值等于城市数目时有较好性能。蚂蚁数目2.3蚂蚁系统理论参数设置1信息素挥发因子较大，信息素挥发速率大，从未被蚂蚁选择过的边上信息素急剧减少到接近0，降低算法的全局探索能力。2信息素挥发因子较小，算法具有较高的全局搜索能力，但是由于每个路径的信息素浓度差距拉大较慢，算法收敛速度较慢。信息素挥发因子3对于AS和EAS，；基于排列的蚂蚁系统，；MMAS,;ACS,,算法的综合性能提高。=0.5=0.1=0.02=0.12.3蚂蚁系统理论参数设置1初始信息素量太小，未被蚂蚁选择过的边上信息素太少，蚂蚁很快就全部集中在一条局部最优的路径上，算法易早熟。2初始信息素太大，信息素对搜索方向的引导能力增长十分缓慢，算法收敛慢。初始信息素量3对于AS；EAS，；，；MMAS,;ACS,0=/nnmC0=(e+m)/nnC0=0.5r(r-1)/nnCrankAS0=1/nnC0=1/nnnC2.4蚂蚁系统算法初始化每条边上的信息素量1对每只蚂蚁，随机选择一个出发城市2对每只蚂蚁根据启发式信息和信息素浓度选择下一个访问城市3计算每只蚂蚁构建的路径长度，更新每条边上的信息素量4判断是否满足结束条件52.4蚂蚁系统算法结束条件1将最大循环数设定为500、1000、5000，或者最大的函数评估次数，等等。也可以使用算法求解到一个可接受的解作为终止条件。23当算法在很长一段迭代中没有得到任何改善时。2.4蚂蚁系统算法构建方式并行构建顺序构建所有蚂蚁都从当前城市移动到下一个城市。所有蚂蚁都从当前城市移动到下一个城市。当一只蚂蚁完成一轮完整的构建并返回到初始城市之后，下一只蚂蚁才开始构建两种构建方式，对于蚂蚁系统来说是等价的，因为他们都没有明显地改变算法的行为特征。对于其他ACO算法而言这两种方法就不等价了，例如：ACS算法。3.1精华蚂蚁系统提出背景：当城市的规模较大时，问题的复杂度呈指数级增长，仅靠AS系统中这样一个基础单一的信息素更新机制引导搜索偏向，搜索效率有瓶颈。能否用一张“额外手段”强化某些最可能成为最有路径的边，让蚂蚁搜索的范围更快、更正确地收敛呢？精华蚂蚁系统是对基础AS的第一次改进，它在原AS信息素更新原则上增加了一个对至今最优路径的强化手段。提出背景：当城市的规模较大时，问题的复杂度呈指数级增长，仅靠AS系统中这样一个基础单一的信息素更新机制引导搜索偏向，搜索效率有瓶颈。能否用一张“额外手段”强化某些最可能成为最有路径的边，让蚂蚁搜索的范围更快、更正确地收敛呢？蚁群优化算法蚁群优化算法简介一蚂蚁系统二蚁群优化算法的改进版本三蚁群优化算法相关应用四3.1精华蚂蚁系统信息素的更新：1,(1),,,mkbkijijijeij1,j,0kkkCiRij否则1,j,0bbbCiTij在路径上否则信息素的更新：参数e作为的权值，是算法开始至今最优路径的长度，其中搜索到至今最优路径用表示。,bijbCbT信息素的更新：3.2基于排列蚂蚁系统提出背景：在EAS提出后，有没有更好的一种信息素更新方式，它同样使各边的信息浓度得到加强，且对其余各边的信息素更新机制亦有改善？bT基于排列的蚂蚁系统就是这样的一种改进版本，在每一轮所有蚂蚁构建完路径后，将按照所得路径的长度进行排名，只有生成了至今最优路径的蚂蚁和排名在前（w-1）的蚂蚁才允许释放信息素，蚂蚁在边（i,j）上释放的信息素的权值由蚂蚁的排名决定。在EAS提出后，有没有更好的一种信息素更新方式，它同样使各边的信息浓度得到加强，且对其余各边的信息素更新机制亦有改善？bT3.2基于排列蚂蚁系统1,j,0bbbCiTij在路径上否则信息素的更新：1,(1),,,mkbkijijkijij1,j,0kkkCiRij否则bT至今最优路径不一定出现在当前迭代的路径中，各种蚁群算法均假设蚂蚁有记忆能力，至今最优路径总是能被记住。路径将获得最多的信息素量，排名越前的蚂蚁释放的信息素量越大，权值对不同路径的信息素浓度差异起了一个放大作用。一般=63.3最大最小蚂蚁系统最大最小蚂蚁系统提出背景：1.对于大规模的TSP，由于搜索蚂蚁的个数有限，而初始化时蚂蚁的分布是随机的，这会不会造成蚂蚁只搜索了所有路径中的小部分就以为找到了最好的路径，而真正优秀的路径并没有被探索到呢？2.当所有蚂蚁都重复构建着同一条路径的时候，意味着算法已经进入了停滞状态，有没有办法利用算法停滞后的迭代过程进一步搜索以保证找到更接近真实目标的解呢？3.3最大最小蚂