1、算法简介

两种基于群智能的算法：蚁群算法和粒子群算法，前者模仿蚂蚁觅食，后者模仿鸟类觅食。

蚁群算法（ant colony optimization, ACO），是一种用来在图中寻找优化路径的概率型算法，其灵感来源于蚂蚁寻找食物过程中发现路径的行为。

蚁群算法主要用来解决路径规划等离散优化问题，如调度问题、旅行商问题等。

2、旅行商问题

即TSP问题（Travelling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。

假设有一个旅行商人要拜访n个城市，需选择一条路线，要求所有城市走一遍回到起点，同时使所走路程最短，即满足：

• 所走路径是所有路径中最短的
• 每个城市只能拜访一次
• 从某城市出发，最后回到该城市

3、蚁群算法基本思想

蚂蚁沿不同的路径出去寻找食物，找到食物就马上返回。

这样短路径的蚂蚁来回一次时间短，单位时间内走过的蚂蚁数目就多，洒下的信息素自然会多，从而吸引更多蚂蚁，洒下更多信息素。而长路径恰好相反。

因此，越来越多的蚂蚁会聚集到短路径上来，从而找到最短路径。

名词解释

• 信息素：蚂蚁在经过的地方分泌的激素，信息素多的地方代表经过这里的蚂蚁多
• 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率越大

4、蚁群算法步骤

1. 初始化：将m只蚂蚁随机放置
2. 更新禁忌表：将当前位置添加到禁忌表
3. 确定行走方向：根据转移概率选择下一点
4. 求信息素增量：每只蚂蚁游玩一周后，计算每条边上的信息素增量
5. 判断终止条件：判断周游次数是否满足终止条件

5、蚁群算法的特点

1. 正反馈，可以较快发现较好解
2. 分布式，易于并行实现
3. 启发式搜索，反映了搜索中的先验性、确定性因素的强度
4. 鲁棒性强，不易受个体影响

蚁群算法的缺陷

• 需要较长搜索时间
• 容易出现停滞现象

蚁群算法改进

• 搜索速度改进，引入侦察蚁、工蚁
• 搜索策略改进，加入扰动、添加牵引力引导蚂蚁朝全局最优搜索

6、结果展示

如下图所示，红色的圆点代表城市坐标，蓝色的线代表搜索出来的结果。