1.3　蚁群算法

蚁群算法是一种模拟蚂蚁觅食行为的元启发式优化算法，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是意大利学者M. Dorigo等在1991年提出的一种群智能启发式算法，并首先被用于解决TSP（旅行商问题）。蚁群算法本质上是一种隶属进化算法的启发式全局优化算法。

1.3.1　基本思想

蚁群在寻找食物时，总能找到一条最优的路径。这是因为蚂蚁在寻找食物时会在路径上释放出一种特殊的信息素。蚂蚁在寻找食物的过程中，可以感知这种信息素的存在和强度。开始时，环境中没有信息素，蚂蚁完全随机地寻找路径。随后，蚂蚁会根据先前蚂蚁遗留下来的信息素来选择路径，路径上信息素的强度越高，该路径被选择的概率越大。同时，信息素是一种挥发性物质，随着时间推移会慢慢减少。如果每只蚂蚁在单位距离上遗留的信息素相同，那么较短路径上的信息素浓度就会更高，最终蚁群会找出最优路径。

在开始时刻，首先将m只蚂蚁随机地放到n座城市，并将每只蚂蚁的禁忌表tabu中的第一个元素设置为它此时所在的城市，让各城市之间路径上的信息素量相同。设τ_ij（0）=c，c为较小的常数，让每只蚂蚁根据路径上的信息素量和启发式信息独立地选择它要去的下一个城市。在时刻t，蚂蚁k从城市i转移到城市j的概率为

式中，J_k（i）表示可供蚂蚁k下一次选择的城市的集合，J_k（i）={1，2，…，n}-tabu_k。

tabu_k表记录了蚂蚁k已经走过的城市。当所有的城市都进入tabu_k表，表明蚂蚁k完成了一次周游，此时蚂蚁k走过的路径便是TSP问题的一个可行解。η_ij是一个启发因子，表示蚂蚁从城市i转移到城市j的期望大小。η_ij通常为城市i到j的距离的倒数。α和β表示信息素和期望启发因子的相对重要程度。当所有的蚂蚁完成一次周游时，各个路径上的信息素根据式（1-4）更新。

式中，ρ（0<ρ<1）为信息素的蒸发系数；1-ρ表示信息素的持久性系数；Δτ_ij表示此次迭代中路径（i，j）上的信息素增量；为第k只蚂蚁在本次迭代中留在路径（i，j）上的信息素量。

如果蚂蚁k没有经过路径（i，j），则的值设为0。表示为

式中，Q为正常数，L_K表示第k只蚂蚁在此次周游中所走过路径的长度。

1.3.2　算法流程

蚁群算法运行的具体流程如下。

步骤1：初始化参数令时间t=0，循环次数N_c=0，最大循环次数G；设置蚂蚁个数为m，元素个数为n，有向图每条边上的初始化信息为τ_ij（t）=c，其中c表示常数，且初始时刻Δτ_ij（0）=0。

步骤2：增加循环次数N_c=N_c+1。

步骤3：设置蚂蚁的禁忌表索引号k=1。

步骤4：设置蚂蚁的数目k=k+1。

步骤5：根据式（1-3）计算后的概率选择元素j，j∈{J_k（i）}。

步骤6：修改禁忌表指针，蚂蚁将移动到选择好的新元素，并把该元素移动到蚂蚁个体的禁忌表中。

步骤7：若集合C中的元素没有遍历完，即k<m，则返回步骤4；否则继续执行下一步。

步骤8：记录此次迭代的最佳路线。

步骤9：根据式（1-4）、式（1-5）更新每条路径上的信息。

步骤10：若N_c≥G，结束循环输出最优结果；否则返回步骤2。

1.3.3　伪代码