文档介绍：现代优化算法-蚁群算法
现代智能优化算法
模拟退火
遗传算法
蚁群优化算法
蚁群优化算法—蚂蚁生物行为
蚂蚁搬家，天要下雨。
蚂蚁群体行为。
相互协作的一群蚂蚁
最短路径（最优解）
最短路径
蚁群优化算法—算法提出
在20世纪90年代，意大利学者Dorigo等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟进化算法，蚁群优化算法。并用该方法求解TSP问题（及其他组合优化问题，如分配问题、Job-shop 调度问题等），取得了一系列较好的实验结果。
蚁群优化算法—算法提出
蚁群优化算法的核心思想有三条：
第一，选择机制：迹越多的路径，被选中的概率越大；
第二，迹更新机制：路径越短，迹增加越快；
第三，协作机制：个体之间通过迹进行信息交流。
蚁群优化算法—算法流程
蚁群优化算法实现（以TSP问题为例）：
第一步，初始化，将m只蚂蚁放入到n个随机选择的城市中。
第二步，选择机制：每一只蚂蚁每一步的行动是，根据一定的依据选择下一个它还没有访问的城市；
第三步，迹更新机制：在完成一步（从一个城市到达另外一个城市）或者一个循环（完成对所有n个城市的访问）后，更新所有路径上的残留信息浓度。
第四步，判断是否停止算法，停止则输出最优结果；否则，返回第二步。
蚁群优化算法—算法流程
选择机制，选择下一个城市的依据主要是两点：
1）t 时刻连接城市 i 和 j 的路径上残留信息（迹）的浓度—— 。
2）由城市 i 转移到城市 j 的启发信息，该启发信息是由要解决的问题给出的—— ，在TSP问题中一般取，其中，表示城市 i，j 间的距离，在这里可以称为先验知识。
蚁群优化算法—算法流程
选择机制，
那么，t 时刻位于城市 i 的蚂蚁 k 选择城市 j 为目标城市的概率是：
：残留信息的相对重要程度；
：启发信息的相对重要程度；
：所有可能的目标城市，即还没有访问的城市。为了避免对同一个城市的多次访问，每一只蚂蚁都保存一个列表tabu(k)，用于记录到目前为止已经访问的城市；
：t时刻蚂蚁由 i 城市到 j 城市的概率。
蚁群优化算法—算法流程
迹更新机制，
为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂蚁完成对所有n个城市的访问后（也即一个循环结束后）或每走一步（从一个城市到下一个城市后），必须对残留信息进行更新处理， Morigo介绍三种迹更新机制：
1）ant-cycle算法
2）ant-density算法
3）ant-quantity算法
蚁群优化算法—算法流程
迹更新机制——ant-cycle算法，
在每一只蚂蚁完成对所有n个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入。
：残留信息的保留部分；
：残留信息被削弱的部分，小于1；
：蚂蚁k在时间段t到t+n内的访问过程中，在i到j的路径上留下的残留信息浓度；
Q ：为常量；
Lk ：蚂蚁k在本次循环中所选择路径的总长度。
蚁群优化算法—算法流程
迹更新机制——ant-cycle算法，
：蚂蚁k在时间段t到t+n内的访问过程中，在i到j的路径上留下的残留信息浓度；
Q ：为常量；
Lk ：蚂蚁k在本次循环中所选择路径的总长度；如果没有选择i到j的路径，则
蚁群优化算法—算法流程
迹更新机制——ant-density算法，
在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入。
蚂蚁k选择i到j的路径
蚂蚁k没有选择i到j的路径
蚁群优化算法—算法流程
迹更新机制——ant-quantity算法，
在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入。
蚂蚁k选择i到j的路径
蚂蚁k没有选择i到j的路径
蚁群优化算法—算法流程
迹更新机制——三种算法的比较，
ant-cycle算法的效果最好，这是因为它用的是全局信息——Q/Lk；
ant-density、ant-quantity算法用