现代优化算法-蚁群算法.ppt

现代智能优化算法,颜学峰实验十六楼415房间Email：华东理工大学信息学院自动化研究所二八年 十 月,现代智能优化算法,模拟退火,遗传算法,蚁群优化算法,蚁群优化算法蚂蚁生物行为,蚂蚁搬家，天要下雨。蚂蚁群体行为。相互协作的一群蚂蚁可以战胜比自己强壮的昆虫，并把它搬回巢；而单个蚂蚁则不能。相互协作的一群蚂蚁可以很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。不但引起昆虫学家，而且也引起数学及计算机方面的专家和工程师的兴趣。,蚁群优化算法蚂蚁生物行为,昆虫学家通过大量的研究发现：蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径的目的。蚂蚁个体通过在其所经过的路上留下一种称之为“信息素”（pheromone）或“迹”的物质来实现与同伴之间的信息传递。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。,蚁群优化算法蚂蚁生物行为,信息素随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到蚁巢到食物源的最短路径。,蚁群优化算法蚂蚁生物行为,蚁群实现找到蚁巢到食物源的最短路径示意图,图1,图1中设A是蚁巢，E是食物源，H、C为障碍物，由于障碍物的存在，由A外出觅食或由E返回巢穴的蚂蚁只能经由H或C到达目的地。BH和HD距离为1单位，BC和DC距离为0.5单位。假设蚂蚁以“1单位长度/单位时间”的速度往返于A和E，每经过一个单位时间各有30只蚂蚁离开A和E到达B和D。,蚁群优化算法蚂蚁生物行为,蚁群实现找到蚁巢到食物源的最短路径示意图,初始时，各有30只蚂蚁在B和D点遇到障碍物，开始选择路径。由于此时路径上无迹，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往H，15只选往C（图2）。经过一个单位时间以后，路径BHD被15只蚂蚁爬过，而路径BCD上则被30只蚂蚁爬过，BCD上的信息量是BHD上信息量的两倍。,图2,蚁群优化算法蚂蚁生物行为,蚁群实现找到蚁巢到食物源的最短路径示意图,图3,此时，又有30只蚂蚁离开B和D，于是20只选择往C方向，而另外10只则选往H（图3）。这样，更多的信息量被留在更短的路径BCD上。随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径BCD。,相对弱小，功能并不强大的个体是完成复杂的工作。,蚁群优化算法算法提出,一个著名的组合优化问题：旅行商问题（TSP,traveling salesman problem），一个商人欲到 n 个城市推销商品，每个两个城市 i 和 j 之间的距离为 dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。,蚁群优化算法算法提出,一般旅行商问题TSP，数学模型描述：,选择 ij 路线为1，否则为0,避免产生回路,走入城市j只有一次,从城市i出发只有一次,蚁群优化算法算法提出,例子，一般旅行商TSP问题的解。,如图所示，从A城市出发回到A城市一个TSP问题的解是ABCEDA，即图中红色线条路径。这个解满足以上四个约束条件。,蚁群优化算法算法提出,NP问题：至今为止，还没有一个有能求得最优解的多项式时间算法的组合优化问题称为NP问题。TSP问题就是一个著名的NP问题。在如何解决这个问题方面已经有了大量的研究。这其中包括遗传算法，退火算法，动态规划等等。,蚁群优化算法算法提出,TSP问题与蚁群寻径行为比较：,蚁群优化算法算法提出,在20世纪90年代，意大利学者Dorigo等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟进化算法，蚁群优化算法。并用该方法求解TSP问题（及其他组合优化问题，如分配问题、Job-shop 调度问题等），取得了一系列较好的实验结果。,蚁群优化算法算法提出,蚁群优化算法的核心思想有三条：第一，选择机制：迹越多的路径，被选中的概率越大；第二，迹更新机制：路径越短，迹增加越快；第三，协作机制：个体之间通过迹进行信息交流。,蚁群优化算法算法流程,蚁群优化算法实现（以TSP问题为例）：第一步，初始化，将m只蚂蚁放入到n个随机选择的城市中。第二步，选择机制：每一只蚂蚁每一步的行动是，根据一定的依据选择下一个它还没有访问的城市；第三步，迹更新机制：在完成一步（从一个城市到达另外一个城市）或者一个循环（完成对所有n个城市的访问）后，更新所有路径上的残留信息浓度。第四步，判断是否停止算法，停止则输出最优结果；否则，返回第二步。,蚁群优化算法算法流程,选择机制，选择下一个城市的依据主要是两点：1）t 时刻连接城市 i 和 j 的路径上残留信息（迹）的浓度。2）由城市 i 转移到城市 j 的启发信息，该启发信息是由要解决的问题给出的，在TSP问题中一般取，其中，表示城市 i，j 间的距离，在这里可以称为先验知识。,蚁群优化算法算法流程,选择机制，那么，t 时刻位于城市 i 的蚂蚁 k 选择城市 j 为目标城市的概率是：,：残留信息的相对重要程度；：启发信息的相对重要程度；：所有可能的目标城市，即还没有访问的城市。为了避免对同一个城市的多次访问，每一只蚂蚁都保存一个列表tabu(k)，用于记录到目前为止已经访问的城市；：t时刻蚂蚁由 i 城市到 j 城市的概率。,蚁群优化算法算法流程,迹更新机制，为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂蚁完成对所有n个城市的访问后（也即一个循环结束后）或每走一步（从一个城市到下一个城市后），必须对残留信息进行更新处理，Morigo介绍三种迹更新机制：1）ant-cycle算法2）ant-density算法3）ant-quantity算法,蚁群优化算法算法流程,迹更新机制ant-cycle算法，在每一只蚂蚁完成对所有n个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入。,：残留信息的保留部分；：残留信息被削弱的部分，小于1；：蚂蚁k在时间段t到t+n内的访问过程中，在i到j的路径上留下的残留信息浓度；Q：为常量；Lk：蚂蚁k在本次循环中所选择路径的总长度。,蚁群优化算法算法流程,迹更新机制ant-cycle算法，,：蚂蚁k在时间段t到t+n内的访问过程中，在i到j的路径上留下的残留信息浓度；Q：为常量；Lk：蚂蚁k在本次循环中所选择路径的总长度；如果没有选择i到j的路径，则,蚁群优化算法算法流程,迹更新机制ant-density算法，在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入。,蚂蚁k选择i到j的路径,蚂蚁k没有选择i到j的路径,蚁群优化算法算法流程,迹更新机制ant-quantity算法，在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入。,蚂蚁k选择i到j的路径,蚂蚁k没有选择i到j的路径,蚁群优化算法算法流程,迹更新机制三种算法的比较，ant-cycle算法的效果最好，这是因为它用的是全局信息Q/Lk；ant-density、ant-quantity算法用的是局部信息Q、Q/dij。,蚁群优化算法算法流程,迹更新机制优点：1）保证了残留信息不至于无限累积，如果路径没有被选中，那么上面的残留信息会随时间的推移而逐渐减弱，这使算法能“忘记”不好的路径；2）即使路径经常被访问也不至于因为 的累积，而产生 使启发信息的作用无法体现。,蚁群优化算法算法流程,算法流程框图ant-cycle,蚁群优化算法算法流程,算法复杂度：如果程序终止于NC次循环后，这个算法的复杂度为O（NC*n2*m）。一般情况下，m一般取值与n为同一数量级，因此整个算法的复杂度O（NC*n3）,蚁群优化算法优缺点,优点：1）正反馈，能迅速找到较好的解；2）分布式计算，可以避免过早地收敛；3）强启发，能在早期的寻优中迅速找到合适（可行）的解；4）强鲁棒性，对基本蚁群优化算法稍加修改，便可以应用于其他问题；5）易于与其他优化算法结合，以改善其优化性能。,蚁群优化算法优缺点,缺点：1）算法有众多参数（如残留信息的相对重要程度、启发信息的相对重要程度、Q常数、残留信息的保留部分）需要确定，并且算法对参数敏感；2）求解时间较长，蚁群算法的复杂度可以反映这一点；3）易出现停滞现象，即算法搜索进行到一定程度后，所有个体发现的解都完全一致，不能对解空间进一步进行搜索。,蚁群优化算法改进,蚁群算法的各种改进：1）MAX-MIN ANT SYSTEM（MMAS）算法2）自适应蚁群优化算法3）自适应调整信息素的蚁群算法4）自适应调整（残留信息的保留部分）的蚁群算法5）带杂交算子的蚁群算法6）在解决TSP问题分段算法Section_MMMAS7）在解决TSP问题相遇算法MMMAS,蚁群优化算法改进,1）MAX-MIN ANT SYSTEM（MMAS）算法只对最佳路径增加迹的浓度，从而更好地利用了历史信息；为了避免算法过早收敛于并非全局最优的解，将各条路径可能的迹浓度限制于，超出这个范围的值被强制设为 或者为，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上；将各条路径上迹的初始浓度设为，这样便可以更加充分地进行寻优。,蚁群优化算法改进,2）自适应蚁群优化算法问题：蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度慢；正反馈原理旨在强化性能较好的解，却容易出现停滞现象。解决：从选择策略方面进行修改，采用确定性选择和随机选择相结合的选择策略，并在搜索过程中动态地调整确定性选择的概率。进化到一定代数后，进化方向已经基本确定，这时对路径上信息量作动态调整，缩小最好和最差路径上的信息两的差距，并适当增大随机选择的概率，以利于对解空间的更完全搜索。,蚁群优化算法改进,2）自适应蚁群优化算法该算法由下式确定蚂蚁 k 从 i 城市转移到 s 城市：,蚁群优化算法改进,3）自适应调整信息素的蚁群算法问题：蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度慢；正反馈原理旨在强化性能较好的解，却容易出现停滞现象。解决：根据搜索进展情况，动态修改需要增加的信息素的方法。算法采用时变函数Q（t）来替代调整信息素 中常量Q，即，Q（t）随着人工蚂蚁搜索过程做实时的调整和变化,蚁群优化算法改进,3）自适应调整信息素的蚁群算法自适应调整策略：通过对算法的监控，实时判断算法的搜索状态，如果一段时间内获得的最优解没有变化，则减少要添加的信息素，即减少 中的Q（t）。,Q（t）时变函数几个例子，针对不同情况使用,蚁群优化算法改进,4）自适应调整（残留信息的保留部分）的蚁群算法问题：当问题规模比较大时，由于信息素的挥发系数 1-的存在，使那些从未被搜索到的解上信息素会减少到接近于0，降低了算法的全局搜索能力，而且 过大时，以前搜索过册解被选择的可能性过大，也会影响到算法全局搜索能力；通过减少，虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低。解决：自适应调整 的值，的初始值为=1；当算法求得的最优值在N次循环内没有明显改进时，减为：,蚁群优化算法连续问题,最初的蚁群算法思想起源于离散型的网络路径问题，因此，在一般函数优化问题中，必须对许多实施细节加以修正。第一，转移概率,蚁群优化算法连续问题,第二，强度更新方程,寻优过程：,蚁群优化算法连续问题,一般函数优化的蚁群优化算法流程：,