1、算法简介
两种基于群智能的算法：蚁群算法和粒子群算法，前者模仿蚂蚁觅食，后者模仿鸟类觅食。
蚁群算法（ant colony optimization, ACO），是一种用来在图中寻找优化路径的概率型算法，其灵感来源于蚂蚁寻找食物过程中发现路径的行为。
蚁群算法主要用来解决路径规划等离散优化问题，如调度问题、旅行商问题等。
2、旅行商问题
即TSP问题（Travelling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。
假设有一个旅行商人要拜访n个城市，需选择一条路线，要求所有城市走一遍回到起点，同时使所走路程最短，即满足：
- 所走路径是所有路径中最短的
- 每个城市只能拜访一次
- 从某城市出发，最后回到该城市
3、蚁群算法基本思想
蚂蚁沿不同的路径出去寻找食物，找到食物就马上返回。
这样短路径的蚂蚁来回一次时间短，单位时间内走过的蚂蚁数目就多，洒下的信息素自然会多，从而吸引更多蚂蚁，洒下更多信息素。而长路径恰好相反。
因此，越来越多的蚂蚁会聚集到短路径上来，从而找到最短路径。
名词解释
- 信息素：蚂蚁在经过的地方分泌的激素，信息素多的地方代表经过这里的蚂蚁多
- 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率越大
4、蚁群算法步骤
- 初始化：将m只蚂蚁随机放置
- 更新禁忌表：将当前位置添加到禁忌表
- 确定行走方向：根据转移概率选择下一点
- 求信息素增量：每只蚂蚁游玩一周后，计算每条边上的信息素增量
- 判断终止条件：判断周游次数是否满足终止条件
5、蚁群算法的特点
- 正反馈，可以较快发现较好解
- 分布式，易于并行实现
- 启发式搜索，反映了搜索中的先验性、确定性因素的强度
- 鲁棒性强，不易受个体影响
蚁群算法的缺陷
- 需要较长搜索时间
- 容易出现停滞现象
蚁群算法改进
- 搜索速度改进，引入侦察蚁、工蚁
- 搜索策略改进，加入扰动、添加牵引力引导蚂蚁朝全局最优搜索
6、结果展示
如下图所示，红色的圆点代表城市坐标，蓝色的线代表搜索出来的结果。
