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

现代智能优化算法 颜学峰 实验十六楼415房间 Email：xfyan@ecust.edu.cn Telo) 华东理工大学 信息学院自动化研究所 二○○八年 十 月 现代智能优化算法 模拟退火 蚁群优化算法—蚂蚁生物行为 蚂蚁搬家，天要下雨。 蚂蚁群体行为。 相互协作的一群蚂蚁可以战胜比自己强壮的昆虫，并把它搬回巢；而单个蚂蚁则不能。 相互协作的一群蚂蚁可以很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。——不但引起昆虫学家，而且也引起数学及计算机方面的专家和工程师的兴趣。 蚁群优化算法—蚂蚁生物行为 昆虫学家通过大量的研究发现：蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径的目的。 蚂蚁个体通过在其所经过的路上留下一种称之为“信息素”（pheromone）或“迹”的物质来实现与同伴之间的信息传递。 随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。 蚁群优化算法—蚂蚁生物行为 信息素随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。 因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到蚁巢到食物源的最短路径。 蚁群优化算法—蚂蚁生物行为 蚁群优化算法—蚂蚁生物行为 蚁群优化算法—蚂蚁生物行为 蚁群优化算法—算法提出 蚁群优化算法—算法提出 蚁群优化算法—算法提出 蚁群优化算法—算法提出 蚁群优化算法—算法提出 蚁群优化算法—算法提出 蚁群优化算法—算法提出 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—算法流程 蚁群优化算法—优缺点 蚁群优化算法—优缺点 蚁群优化算法—改进 蚁群优化算法—改进 蚁群优化算法—改进 蚁群优化算法—改进 蚁群优化算法—改进 蚁群优化算法—改进 蚁群优化算法—改进 蚁群优化算法—连续问题 蚁群优化算法—连续问题 蚁群优化算法—连续问题 1）MAX-MIN ANT SYSTEM （MMAS）算法 只对最佳路径增加迹的浓度，从而更好地利用了历史信息； 为了避免算法过早收敛于并非全局最优的解，将各条路径可能的迹浓度限制于 ，超出这个范围的值被强制设为 或者为 ，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上； 将各条路径上迹的初始浓度设为 ，这样便可以更加充分地进行寻优。 2）自适应蚁群优化算法 问题：蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度慢；正反馈原理旨在强化性能较好的解，却容易出现停滞现象。 解决：从选择策略方面进行修改，采用确定性选择和随机选择相结合的选择策略，并在搜索过程中动态地调整确定性选择的概率。进化到一定代数后，进化方向已经基本确定，这时对路径上信息量作动态调整，缩小最好和最差路径上的信息两的差距，并适当增大随机选择的概率，以利于对解空间的更完全搜索。 2）自适应蚁群优化算法 该算法由下式确定蚂蚁 k 从 i 城市转移到 s 城市： 3）自适应调整信息素的蚁群算法 问题：蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度慢；正反馈原理旨在强化性能较好的解，却容易出现停滞现象。 解决：根据搜索进展情况，动态修改需要增加的信息素的方法。算法采用时变函数Q（t）来替代调整信息素 中常量Q，即 ， Q（t）随着人工蚂蚁搜索过程做实时的调整和变化 3）自适应调整信息素的蚁群算法 自适应调整策略：通过对算法的监控，实时判断算法的搜索状态，如果一段时间内获得的最优解没有变化，则减少要添加的信息素，即减少 中的Q（t）。 Q（t）时变函数几个例子，针对不同情况使用 4）自适应调整 （残留信息的保留部分）的蚁群算法 问题：当问题规模比较