蚁群算法

算法背景及原理

蚁群算法是一种智能优化算法，在TSP商旅问题上得到广泛使用。蚁群算法于1992年由Marco Dorigo首次提出，该算法来源于蚂蚁觅食行为。由于蚂蚁没有视力，所以在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。通常，蚂蚁会以较大的概率优先选择信息素浓度高的路径，并且释放一定的信息素，使该条路径上的信息素浓度增高，进而使蚂蚁能够找到一条由巢穴到食物源最近的路径。但是，随着时间的推移，路径上的信息素浓度会逐渐衰减。

算法应用

蚁群算法被应用于数据分析、机器人协作求解、电力、通信、水利、交通、建筑等领域。该算法最初是用来解决TSP问题，但是经过多年发展，已经逐渐渗透到其他领域中，例如车辆调度问题、图着色问题等，其中，最成功的是在组合优化问题中的应用。其中，TSP是指从原点出发，经过若干个给定的需求点，最终返回原点的最短路径，也就是著名的旅行商问题（Traveling Saleman Problem,TSP）。

算法特点

（1）自组织算法

组织力和组织指令来自系统内部

（2）并行算法

蚂蚁搜索过程彼此独立，仅通过信息素进行通信（3）正反馈算法

信息素堆积是一个正反馈的过程

算法步骤

（1）初始化个各个参数

在计算之处需要对各参数进行初始化，如蚂蚁数量m、信息素因子

、启发函数因子

、信息素挥发因子

、信息素常数Q、最大迭代次数t等 。

蚁群算法的参数选择需要一栏经验或者试错，所以在参数设置方面，需要注意：

蚂蚁数量m如果数量设置过大，将会使每条路径上信息素趋于平均，使正反馈作用减弱，从而使收敛速度减慢；如果蚂蚁数量m如果数量设置过小，可能会导致一些从来没有被搜索过的路径信息素浓度减少为0，从而使算法过早收敛，解的全局最优性降低。一般将蚂蚁数量设置为目标数的1.5倍。

信息素常量Q如果设置过大会导致蚁群的搜索范围减小，造成算法过早收敛，使种群陷入局部最优；如果设置过小会使每条路径上信息含量差别较小，容易陷入混沌状态。信息素常量根据经验一般取值在[10,100]。

最大迭代次数t如果设置过大会导致算法运行时间过长；设置过小会导致可选路径较少，使种群陷入局部最优。最大迭代次数一般取值[100,500]，建议取值为200。

信息素因子

表示蚂蚁运动过程中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度。如果参数设置过大，蚂蚁选择之前走过的路径的可能性较大，容易使算法的随机性减弱；如果该参数设置过小，会导致蚁群的搜索范围过小，进而使算法过早收敛，使种群陷入局部最优。一般取值在[1,4]之间。

启发函数因子

表示启发式信息在指导蚁群搜索过程中的相对重要程度。如果该参数设置过大，会使收敛速度加快，但是容易陷入局部最优；如果该参数设置过小，会导致蚁群搜索随机性变大，很难找到最优解。根据经验该参数的取值范围一般在[0,5]之间。

信息素挥发因子

表示信息素的消失水平。该参数设置过大会使信息素发挥较快，容易导致较优路径被排除；该参数设置过小导致各路径上信息素含量差别较少，使收敛速度降低。取值范围通常在[0.2,0.5]之间。

（2）构建解空间

将各个蚂蚁随即放置在不同的出发地，对于每个蚂蚁k（

），计算下一个待访问城市，直至每个蚂蚁都访问完所有城市。

蚂蚁在构建路径的每一步中，采用轮盘赌法选择下一要到达的城市。选择每一个路径的概率表示为：

其中，i、j分别表示每段路径的起点和终点，

表示时间t时由i到j的信息素浓度，

的值等于路径长度

的倒数，allowedk表示未访问过的节点的集合。

根据当前路径ij上的信息素浓度

以及启发式函数

便可确定从起点i选择终点j 的概率

。对公式进行分析可知，两地的距离越短，信息素浓度越大的路径被选择的概率应该越大

（3）更新信息素

计算各个蚂蚁经过的路径长度L，记录当前迭代次数中的历史最优解，即最短路径；同时，对各个城市所连接的路径的信息素浓度进行更新

信息素更新的表达式为：

也就是。第t+1次循环后从城市i到城市j上的信息素含量等于第t次循环后从城市i到城市j上的信息素含量乘以信息素残留系数

并加上新增信息素含量，其中新增信息素含量可表示为所有蚂蚁在城市i到城市j的路径上留下的信息素总和。新增信息素含量根据不同规则可以将蚁群算法分为以下三种模型，分别是蚁周模型、蚁量模型以及蚁密模型，具体大家可根据需要进行学习。

（4）判断是否达到终止条件

蚁群算法的终止条件是：判断是否达到最大迭代次数。

算法流程图如下图所示。

蚁群算法的相关介绍到这里就结束了， 代码分享链接如如下：

链接：https://pan.baidu.com/s/1gsIzSQxQLWQXy3Erxb4kFQ

提取码：640a

END