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

蚁群优化算法—算法流程蚂蚁k没有选择i到j的路径蚂蚁k选择i到j的路径迹更新机制——ant-density算法，在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将必威体育精装版的蚂蚁访问路径的信息加入。蚁群优化算法—算法流程蚂蚁k没有选择i到j的路径蚂蚁k选择i到j的路径迹更新机制——ant-quantity算法，在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将必威体育精装版的蚂蚁访问路径的信息加入。蚁群优化算法—算法流程迹更新机制——三种算法的比较，ant-cycle算法的效果最好，这是因为它用的是全局信息——Q/Lk；ant-density、ant-quantity算法用的是局部信息——Q、Q/dij。蚁群优化算法—算法流程迹更新机制——优点：1）保证了残留信息不至于无限累积，如果路径没有被选中，那么上面的残留信息会随时间的推移而逐渐减弱，这使算法能“忘记”不好的路径；2）即使路径经常被访问也不至于因为的累积，而产生使启发信息的作用无法体现。蚁群优化算法—算法流程NC=0，将m只蚂蚁放到n个节点上开始对所有蚂蚁置初始城市到tabu（k）NC=MAX吗？对所有蚂蚁计算概率，选择下一个城市并将蚂蚁移到下一个城市j，将j加入到tabu（k）tabu（k）满吗？更新最佳路径，清空tabu（k），NC=NC+1得到最佳路径，结束算法流程框图ant-cycle蚁群优化算法—算法流程算法复杂度：如果程序终止于NC次循环后，这个算法的复杂度为O（NC*n2*m）。一般情况下，m一般取值与n为同一数量级，因此整个算法的复杂度O（NC*n3）蚁群优化算法—优缺点优点：1）正反馈，能迅速找到较好的解；2）分布式计算，可以避免过早地收敛；3）强启发，能在早期的寻优中迅速找到合适（可行）的解；4）强鲁棒性，对基本蚁群优化算法稍加修改，便可以应用于其他问题；5）易于与其他优化算法结合，以改善其优化性能。现代智能优化算法颜学峰实验十六楼415房间Email：华东理工大学信息学院自动化研究所

二○○八年十月现代智能优化算法模拟退火遗传算法蚁群优化算法蚂蚁搬家，天要下雨。蚂蚁群体行为。相互协作的一群蚂蚁可以战胜比自己强壮的昆虫，并把它搬回巢；而单个蚂蚁则不能。相互协作的一群蚂蚁可以很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。——不但引起昆虫学家，而且也引起数学及计算机方面的专家和工程师的兴趣。蚁群优化算法—蚂蚁生物行为蚁群优化算法—蚂蚁生物行为昆虫学家通过大量的研究发现：蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径的目的。蚂蚁个体通过在其所经过的路上留下一种称之为“信息素”（pheromone）或“迹”的物质来实现与同伴之间的信息传递。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。蚁群优化算法—蚂蚁生物行为信息素随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到蚁巢到食物源的最短路径。蚁群优化算法—蚂蚁生物行为蚁群实现找到蚁巢到食物源的最短路径示意图障碍物ABCDEHd=1d=1d=0.5d=0.5图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。蚁群优化算法—蚂蚁生物行为蚁群实现找到蚁巢到食物源的最短路径示意图障碍物ABCDEH15151515初始时，各有30只蚂蚁在B和D点遇到障碍物，开始选择路径。由于此时路径上无迹，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往H，15只选往C（图2）。经过一个单位时间以后，路径BHD被15只蚂蚁爬过，而路径BCD上则被30只蚂蚁爬过，BCD上的信息量是BHD上信息量的两倍。图2蚁群优化算法—蚂蚁生物行为蚁群实现找到蚁巢到食物源的最短路径示意图障碍物ABCDEH10