1、算法简介

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

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

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

2、旅行商问题

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

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

所走路径是所有路径中最短的每个城市只能拜访一次从某城市出发，最后回到该城市3、蚁群算法基本思想

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

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

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

名词解释

信息素：蚂蚁在经过的地方分泌的激素，信息素多的地方代表经过这里的蚂蚁多正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率越大4、蚁群算法步骤初始化：将m只蚂蚁随机放置更新禁忌表：将当前位置添加到禁忌表确定行走方向：根据转移概率选择下一点求信息素增量：每只蚂蚁游玩一周后，计算每条边上的信息素增量判断终止条件：判断周游次数是否满足终止条件5、蚁群算法的特点正反馈，可以较快发现较好解分布式，易于并行实现启发式搜索，反映了搜索中的先验性、确定性因素的强度鲁棒性强，不易受个体影响

蚁群算法的缺陷

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

蚁群算法改进

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

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