现代优化算法-蚁群算法

《现代优化算法-蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、现代智能优化算法颜学峰实验十六楼415房间Email：xfyan@ecust.edu.cnTel:64253254(o)、13671876906华东理工大学信息学院自动化研究所二○○八年十月现代智能优化算法模拟退火遗传算法蚁群优化算法蚁群优化算法—蚂蚁生物行为蚂蚁搬家，天要下雨。蚂蚁群体行为。相互协作的一群蚂蚁可以战胜比自己强壮的昆虫，并把它搬回巢；而单个蚂蚁则不能。相互协作的一群蚂蚁可以很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。——不但引起

2、昆虫学家，而且也引起数学及计算机方面的专家和工程师的兴趣。蚁群优化算法—蚂蚁生物行为昆虫学家通过大量的研究发现：蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径的目的。蚂蚁个体通过在其所经过的路上留下一种称之为“信息素”（pheromone）或“迹”的物质来实现与同伴之间的信息传递。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。蚁群优化算法—蚂蚁生物行为信息素随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行

3、动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到蚁巢到食物源的最短路径。蚁群优化算法—蚂蚁生物行为蚁群实现找到蚁巢到食物源的最短路径示意图障碍物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。蚁群

4、优化算法—蚂蚁生物行为蚁群实现找到蚁巢到食物源的最短路径示意图障碍物ABCDEH15151515初始时，各有30只蚂蚁在B和D点遇到障碍物，开始选择路径。由于此时路径上无迹，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往H，15只选往C（图2）。经过一个单位时间以后，路径BHD被15只蚂蚁爬过，而路径BCD上则被30只蚂蚁爬过，BCD上的信息量是BHD上信息量的两倍。图2蚁群优化算法—蚂蚁生物行为蚁群实现找到蚁巢到食物源的最短路径示意图障碍物ABCDEH10102020图3此时，又有30只蚂蚁离开B和D，于是20只选择往C方向，而另外10只则

5、选往H（图3）。这样，更多的信息量被留在更短的路径BCD上。随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径BCD。相对弱小，功能并不强大的个体是完成复杂的工作。蚁群优化算法—算法提出一个著名的组合优化问题：旅行商问题（TSP,travelingsalesmanproblem），一个商人欲到n个城市推销商品，每个两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。蚁群优化算法—算法提出一般旅行商问题TSP，数学模型描述：选择ij

6、路线为1，否则为0避免产生回路走入城市j只有一次从城市i出发只有一次蚁群优化算法—算法提出例子，一般旅行商TSP问题的解。ABDEC如图所示，从A城市出发回到A城市一个TSP问题的解是ABCEDA，即图中红色线条路径。这个解满足以上四个约束条件。蚁群优化算法—算法提出NP问题：至今为止，还没有一个有能求得最优解的多项式时间算法的组合优化问题称为NP问题。TSP问题就是一个著名的NP问题。在如何解决这个问题方面已经有了大量的研究。这其中包括遗传算法，退火算法，动态规划等等。蚁群优化算法—算法提出TSP问题与蚁群寻径行为比较：TSP问题蚁群寻径行为解路径寻优过

7、程选择路径最短路径（最优解）最短路径蚁群优化算法—算法提出在20世纪90年代，意大利学者Dorigo等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟进化算法，蚁群优化算法。并用该方法求解TSP问题（及其他组合优化问题，如分配问题、Job-shop调度问题等），取得了一系列较好的实验结果。蚁群优化算法—算法提出蚁群优化算法的核心思想有三条：第一，选择机制：迹越多的路径，被选中的概率越大；第二，迹更新机制：路径越短，迹增加越快；第三，协作机制：个体之间通过迹进行信息交流。蚁群优化算法—算法流程蚁群优化算法实现（以TSP问题为例

8、）：第一步，初始化，将m只蚂蚁放入到n个随机选择的城市中。第二步，