蚁群优化算法PPT

蚁群优化算法AntColonyOptimization2算法介绍•群智能算法群智能是一种由简单智能的个体通过某种形式的聚集协同而表现出智能行为。它在没有集中控制，不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。群智能算法通过模仿生物界的进化机理和群体协作行为而提出的仿生类随机搜索算法。去人工蜂群算法细菌觅食算法萤火虫算法粒子群算法人工鱼群算法鸟群算法3蚁群算法的提出GambardellaMacroDorigo4蚁群算法的发展2001年至今1996年-2001年意大利学者Dorigo1991年Dorigo1991年启发各种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为5蚁群算法原理如何找到最短路径？类比：大肠杆菌在人体肠道内觅食的过程•信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。•正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。6蚁群算法原理自然蚂蚁的智能特点7蚁群算法原理人工蚂蚁的模型8蚁群算法原理自然蚁群与人工蚁群相似之处在于：都是优先选择信息素浓度大的路径。两者的区别在于：（1）人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。（2）人工蚁群选择路径时不是盲目的，而是按一定规律有意识地寻找最短路径。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。9求解组合优化问题的蚁群算法10基本蚁群算法蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：()(),()()()0,kisiskkisisijxallowkttsallowttPtsallowtPkij信息更新公式为：1(1)(1)(),01ijijijnkijiiktt11基本蚁群算法针对蚂蚁释放信息素问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：1.Ant-cycle/kij0,kkiiQL，第只蚂蚁从城市访问城市其他2.Ant-quantityij/kij0,kiiQd，第只蚂蚁从城市访问城市其他3.Ant-densitykij0,kiiQ，第只蚂蚁从城市访问城市其他其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度；d为城市间的距离。。12蚁群算法的主要特点采用分布式控制每个个体只能感知局部的信息个体可以改变环境具有自组织性是一类概率型的全局搜索方法优化过程不依赖于优化问题本身的严格数学性质是一种基于多主体(Multi-Agent)的智能算法具有潜在的并行性13蚁群算法参数选择蚁群数量m的选择·子集越大信息正反馈的作用不明显，搜索的随机性增强，造成收敛速度变慢;反之，子集越小，搜索的随机性减弱，虽然收敛速度较快，但是会使算法的全局性能降低，影响算法的稳定性。信息素挥发度的选取信息素挥发度的大小对蚁群算法的收敛性能影响极大;当比较小时，搜索的全局性好，但收敛速度变慢;当比较大时，收敛速度比较快，但是容易陷入局部最优。14蚁群算法参数选择因子和的选取启发式因子的大小则反映了在蚁群路径搜索中的随机性因素作用的强度;启发式因子的大小反映了在蚁群路径搜索中确定性因素作用的强度。总信息量Q的选取总信息量Q越大，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。蚂蚁的初始分布所有蚂蚁初始时刻放在同一个城市;蚂蚁分布在不同的城市中。15蚁群算法时间复杂度及优缺点·M.Dorigo曾经对经典的TSP问题求解复杂度进行过深入的研究，所得到的经验结果表明，算法的时间复杂度为O(NC·n2·m)，NC表示迭代次数，n表示城市数，m则表示参与搜索的蚂蚁数量。当参与搜索的蚂蚁数量m大致与规模大小n相等时，算法的时间复杂度变为O(NC·n3)较强的鲁棒性分布式计算易于与其他方法结合需要较长的搜索时间容易出现停滞现16带精英策略的蚂蚁系统–每次循环之后给予最优解以额外的信息素量–这样的解被称为全局最优解（global-bestsolution）–找出这个解的蚂蚁被称为精英蚂蚁(elitistants)带精英策略的蚂蚁系统（AntSystemwithelitiststrategy,ASelite）是最早的改进蚂蚁系统。遗传算法中的精英策略蚂蚁系统中的精英策略–传统的遗传算法可能会导致最适应个体的遗传信息丢失–精英策略的思想是保留住一代中的最适应个体17带精英策略的蚂蚁系统信息素根据下式进行更新*(1)()ijijijijtt其中1mkijijk,0,kkijQkL如果蚂蚁在本次循环中经过路径(i,j)否则**,0,ijQL如果边(i,j)是所找出的最优解的一部分否则18带精英策略的蚂蚁系统表示精英蚂蚁引起的路径(i,j)上的信息素量的增加是所找出的最优解的路径长度特点：是精英蚂蚁的个数L可以使蚂蚁系统找出更优的解找到这些解的时间更短精英蚂蚁过多会导致搜索早熟收敛19蚁群系统蚁群系统的状态转移规则0argmax{[(,)][(,)]},,kuallowedruruqqsS如果按先验知识选择路径否则其中，S根据下列公式得：到()(),()()()0,kijijkkisisijsallowedttjallowedttPtotherwise一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s：20蚁群系统蚁群系统全局更新原则1,(,)0,gbLrs如果(r,s)全局最优路径否则(,)(1)(,)(,)rsrsrs只有全局最优的蚂蚁才被允许释放信息素。目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。全局更新在所有蚂蚁都完成它们的路径之后执行，用下式对所建立的路径进行更新：21蚁群系统蚁群系统局部更新原则类似于蚁密和蚁量模型中的更新规则蚂蚁应用下列局部更新规则对它们所经过的边进行信息素更新(,)(1)(,)(,)01rsrsrs其中，实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的一个路径长度nnLnn0Ln1局部更新规则可以有效地避免蚂蚁收敛到同一路径22Max-MinAntSystem（MMAS）信息素轨迹更新原则在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改的轨迹更新原则如下：表示迭代最优解或全局最优解的值。在蚁群算法中主要使用全局最优解，而在MMAS中则主要使用迭代最优解。(1)()ijbestijijtt1()ijbestbestfs23Max-MinAntSystem（MMAS）信息素轨迹的限制MMAS对信息素轨迹的最小值和最大值分别施加了和的限制，从而使得对所有信息素轨迹，有的选取要基于两点假设：1.最优解在搜索停滞发生之前不久被找出。2.对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定minmaxminmax()ijtmax11()()ijttioptitfsmin24Max-MinAntSystem（MMAS）信息素轨迹的平滑化基本思想：通过增加选择有着低强度信息素轨迹量解元素的概率以提高探索新解的能力平滑机制有助于对搜索空间进行更有效的探索*max()()(()())ijijijtttt*()()ijijtt其中,01,和分别为平滑化之前和之后的信息素轨迹量25Max-MinAntSystem（MMAS）26蚁群算法的应用27蚁群算法的应用TSP问题问题描述：旅行商按一定的顺序访问n个城市，使得每个城市都被访问且仅能被访问一次而使花费代价最小，从图论的观点来看，就是找出一个最短的封闭回路。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长TSP在许多工程领域具有广泛的应用价值，例如电路板布线、机器人控制、交通路由等。28蚁群系统在TSP问题中的应用29蚁群算法求解TSP问题下面以TSP为例说明基本蚁群算法模型。首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:表示边（i，j）上的信息素浓度；是启发信息，d是城市i和j之间的距离；α和β反映了信息素与启发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。)1(,0,)],([)],([)],([)],([),(otherwisetabujifsisijijijiPktabuskk),(ji),(/1),(jidjiktabu30蚁群算法求解TSP问题当所有蚂蚁完成周游后，按以下公式进行信息素更新。其中，ρ为小于1的常数，表示信息的持久性。)2()()(1mkkijijijijijtnt)3(0otherwiselijLQkkkij其中，Q为常数；表示第k只蚂蚁在本次迭代中走过的路径长度。kL31InitializationDistributetheants,ModifythetabuCalculatetheprobabilityofmovingbetweencitiesi++Updatepheromonebetweencitiesi=city.NMeettherequirementofthesolutionNumberoftraversecityi=1outputMovetojandmodifythetabuNYCalculatethedistanceeachantwalkstheloopYNEachantchoosethenextcity32实现过程33实现过程34实现过程35实现过程36中国旅行商问题1.5602e+04ACATSP(C,100,10,1,5,0.1,100)37遗传算法和蚁群算法在求解TSP问题上的对比分析38细菌觅食机理趋向性操作设细菌种群大小为S，一个细菌所处的位置表示一个问题的候选解，细菌i的信息用D维向量表示为12[,,,],1,2,,iiiiDiS细菌i在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的位置表示为细菌i的每一步趋向性操作表示如下：(1,,)(,,)()()iijkljklCijC(i)0表示向前游动的步长单位表示旋转后选择的一个随机前进方向开始i=i+1iS?计算细菌i的适应度值，存储细菌i当前适应度值为最好的值旋转初始化m=0计算新位置上细菌i的适应度值msNm=m+1新位置的适应度值更好？将新位置的适应度值存储为细菌i目前最好的适应度值在该随机方向上继续游动一步长单位结束设m=sN否是否是是否()j39细菌觅食机理•聚群行为“抱团”在细菌趋向最佳生存环境的过程中，菌落的个体根据自身当前的适应度值对其他所有细菌释放信息，吸引素和排斥素，即信息素。同时，此细菌接受其他所有细菌的释放的吸引素和排斥素，在其所有信息素的作用下修改自己的适应值。保证向局部环境变好的位置移动。在一个菌落中，上述个体间的信息素浓度计算方法可表示为：40算法简介41细菌觅食机理聚群行为“抱团”其中，Jcc(θ,P(j,k,l))是一种随种群分布状态变化的目标函数，当它被叠加到问题的实际目标函数时，就表示了细菌与最佳个体的相对距离变化趋势；S表示种群的大小；p指明了优化问题的维度。类比：其他群智能算法的聚群行