蚁群优化算法.ppt

《蚁群优化算法.ppt》由会员分享，可在线阅读，更多相关《蚁群优化算法.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、蚂蚁的生活习性蚂蚁的生活习性蚁群优化的起源蚁群优化的起源n蚁群优化(ant colony optimization,ACO)，又名蚁群算法。n1991年意大利学者M.Dorigo在其博士学位论文中首先提出。n通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。蚁群优化的特征蚁群优化的特征n一种典型的群体智能模式。n充分利用蚁群能通过个体间简单的信息传递来进行寻优。n通过正反馈、分布式协作进行路径寻优。正反馈原理：蚂蚁释放信息素(pheromone)。蚁群优化的正反馈机制蚁群优化的正反馈机制旅行商问题（旅行商问题（TSP）n旅行商问题（traveling salesman

2、 problem,TSP）。n一名商人要遍历多个城市，各个城市之间可达且距离已知，如何找到在访问每个城市一次后再回到起点的最短路径。TSP问题举例问题举例TSP问题的解问题的解BCDEFGHIJABCDEFGHIJA路径 1路径2：信息素强度信息素强度：启发程度启发程度蚂蚁蚂蚁 k 由位置由位置 i 移动移动 j 到的概率到的概率蚁群优化描述蚁群优化描述蚁群优化描述蚁群优化描述广州广州南宁南宁长沙长沙福州福州:信息素强度信息素强度:启发因子启发因子蚁群优化描述蚁群优化描述信息素残留信息素残留系数，系数，(0,1)信息素增量信息素增量 启发程度与启发程度与距离成反比距离成反比 概率分配的实现方法

3、概率分配的实现方法一等奖一等奖一等奖一等奖二等奖二等奖二等奖二等奖三等奖三等奖三等奖三等奖轮轮盘盘赌赌0 0.15 0.45 10.15 0.30 0.55概率概率1 1概率概率2 2概率概率3 3概率概率积累概率积累概率蚁群优化的流程蚁群优化的流程带精英策略的蚂蚁系统带精英策略的蚂蚁系统当前最优解当前最优解精英蚂蚁精英蚂蚁带精英策略的蚂蚁系统带精英策略的蚂蚁系统n带精英策略的蚂蚁系统（Ant System with elitist strategy）是最早的改进蚂蚁系统。n精英策略的思想是保留住一代中的最适应个体。n蚂蚁系统中的精英策略：n每次循环之后给予最优解以额外的信息素量。n这样的解被

4、称为全局最优解（global-best solution）。n找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)。带精英策略的蚂蚁系统带精英策略的蚂蚁系统n信息素根据下式进行更新其中带精英策略的蚂蚁系统带精英策略的蚂蚁系统n 表示精英蚂蚁引起的路径(i,j)上的信息素量的增加。n 是精英蚂蚁的个数。n 是所找出的最优解的路径长度。带精英策略的蚂蚁系统的特征带精英策略的蚂蚁系统的特征n可以使蚂蚁系统找出更优的解。n找到这些解的时间更短。n精英蚂蚁过多会导致搜索早熟收敛。比较两组概率比较两组概率n第一组概率：0.02 0.10 0.02 0.70 0.03 0.03 0.08 0.02 A

5、 B C D E F G Hn第二组概率：0.15 0.13 0.10 0.12 0.10 0.15 0.11 0.14 A B C D E F G H较优的解，取不到怎么办？较优的解，取不到怎么办？蚁群系统蚁群系统n蚁群系统(Ant Colony System,ACS)是由Dorigo和Gambardella在1996年提出的。n蚁群系统做了三个方面的改进：n状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法。n全局更新规则只应用于最优的蚂蚁路径上。n在建立问题解决方案的过程中，应用局部信息素更新规则。蚁群系统状态转移规则蚁群系统状态转移规则n一只位于节点r的蚂蚁通过应用

6、下式给出的规则选择下一个将要移动到的城市s其中，S根据下列公式得到蚁群系统状态转移规则蚁群系统状态转移规则nq是在0,1区间均匀分布的随机数。nq0的大小决定了利用先验知识与探索新路径之间的相对重要性。n上述状态转移规则被称为伪随机比例规则。n特点是算法倾向于选择短的且有着大量信息素的边作为移动方向。比较两组概率比较两组概率n第一组概率：0.02 0.10 0.02 0.70 0.03 0.03 0.08 0.02 A B C D E F G Hn第二组概率：0.15 0.13 0.10 0.12 0.10 0.15 0.11 0.14 A B C D E F G H总是取到该较优的解，怎么办

7、？总是取到该较优的解，怎么办？局部最优局部最优全局最优全局最优0 0 A BA B x xy y局部最优与全局最优局部最优与全局最优最大最大-最小蚂蚁系统最小蚂蚁系统n蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生。n最大-最小蚂蚁系统(Max-Min Ant System,MMAS)能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能。最大最大-最小蚂蚁系统最小蚂蚁系统n为了充分利用循环最优解和到目前为止找出的最优解，在每次循环之后，只有一只蚂蚁进行信息素更新。n这只蚂蚁可能是

8、找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁。n为避免搜索的停滞，在每个解的元素上的的信息素轨迹量的值域范围被限制在 区间内。信息素轨迹更新信息素轨迹更新n在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹。n经修改的轨迹更新规则如下：n 表示迭代最优解或全局最优解的值。信息素轨迹的限制的原因信息素轨迹的限制的原因n不管是选择迭代最优还是全局最优蚂蚁来进行信息素更新，都可能导致搜索的停滞。n停滞现象发生的原因：在每个选择点上一个选择的信息素轨迹量明显高于其他的选择。n避免停滞状态发生的方法：影响用来选择下一解元素的概率，它直接依赖于信息素轨迹和启发信息。nMMAS通过限制信息素轨迹的影响，可以避免各信息素轨迹之间的差异过大。