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