基于可变天气因素的MMAS改进算法

焦宗浩，高绍姝，李克文

(中国石油大学 计算机与通信工程学院，山东 青岛 266580)

0 引 言

随着人工智能[1]的飞速发展，专家学者逐渐从生活中寻求更先进的思想，如从自然界中模拟生物群体解决生存问题的行为，其中蚁群算法[2]是模拟蚂蚁觅食、粒子群算法[3]是模拟鸟群觅食。蚁群算法(ant colony optimization，ACO)是在20世纪90年代由意大利学者M. Dorigo根据蚁群觅食活动提出的，后经德国学者Stützle提出一种改进的蚁群算法——最大最小蚂蚁系统(MAX-MIN ant system，MMAS)，该方法广泛应用于各种领域[4-8]，其工作原理是在每次循环过程中仅选择一只最优蚂蚁进行信息素的更新，该更新方式加快了收敛速度，但同时容易陷入局部最优。针对MMAS存在的问题，现有的文献一般是通过改进信息素的更新方式[9,10]、调整蚂蚁的转移规则[11]、采用自适应方法[12,13]等，或者是将MMAS与其它算法结合，如邻域搜索[14]、模拟退火策略[15]，甚至是蚁群算法[16]等。这些算法在一定的程度上提升了蚂蚁的全局搜索能力，但精度有待提高。本文通过可变天气因素对蚁群影响，提出一种基于可变天气因素的最大最小蚂蚁系统(VW-MMAS)，通过随机的信息素挥发机制，改变信息素的残留程度，增强其搜索的能力，提高解的精度。

1 相关概念

1.1 基本蚁群算法

我们以求解平面上n城市的旅行商问题(TSP)为例，来说明传蚁群算法原理。TSP问题是指，给定一组城市坐标，城市数量为n，求得一条遍历所有城市的最短回路的问题，其中除了出发的城市以外其它城市仅允许走一次。首先初始化蚁群数量m，信息启发因子α，期望启发因子β，信息素挥发系数ρ，各路径上的信息素τij，其中在初始时刻每条路径的信息素浓度设为相等，即τij=C(C为较小的常数)；然后在每次迭代过程中，每只蚂蚁随机选择一个城市作为起始城市，再使用轮盘赌的方法，按照式(1)选择下一个城市

(1)

τij(t)=(1-ρ)τij(t-1)+Δτij(t)

(2)

1.2 最大最小蚂蚁系统

最大最小蚂蚁系统(MMAS)是在ACO上改进，克服ACO容易陷入局部最优、收敛速度慢、花费时间长等缺点，其主要改进方向是以下3个方面：

(1)将信息素τij限制在τmin与τmax之间，即τmin≤τij≤τmax， 该策略避免最优路径上的信息素和未访问路径的信息素差距过大，导致搜索的停滞；

(2)将初始信息素设置为τmax， 该策略使得算法在初始阶段有更多的搜索可能；

(3)在每次迭代之后，只允许路径最优蚂蚁更新信息素，可以是当前迭代最优，也可以是历史最优。其信息素更新方式按照式(3)进行

(3)

2 改进的最大最小蚂蚁系统

虽然群体蚂蚁有着明确的分工行为模式，但是其觅食行为仍受着外界环境的影响，如地形、天气等外在因素。根据蚂蚁的生活习性发现，在不同的天气之后蚂蚁的觅食行为有所不同，主要原因是在不同天气信息素的残留程度不同，如在雨天之后，雨水冲刷了信息素，导致信息素的整体减少，信息素之间的差距减少，使得蚂蚁在雨天过后觅食范围明显扩大。因此本文提出的可变天气因素最大最小蚂蚁系统(VW-MMAS)是针对不同天气情况下，设置不同的信息素挥发系数，从而改进最大最小蚂蚁系统，更新全局信息素的残留程度，扩大其蚂蚁的搜索范围，避免快速陷入局部最优，停止迭代。

2.1 基于可变天气因素改进MMAS算法

由于实际的天气是复杂多样的，为了说明本文所提出的改进方法的有效性，实验以3种天气情况为例，分别是雨天、阴天、晴天。通过在不同的天气情况下设置不同的信息素挥发系数，根据实际情况将信息素挥发系数按照可变天气因素排序；同时考虑到在不同天气情况下，外出觅食的蚂蚁数量有所不同，本文假设在雨天挥发系数最大且蚂蚁不觅食，在阴天挥发系数最小且随机选择一定数量蚂蚁觅食，在晴天挥发系数中等且全部蚂蚁外出觅食。采用上述的改进方式能够有效增加全局的搜索能力，避免快速陷入局部最优。

在不同的天气下，设置不同的信息素挥发系数以及蚁群数量。首先设置信息素挥发ρr、ρc、ρs， 其中ρr表示雨天时挥发系数，ρc表示阴天时挥发系数，ρs表示晴天时挥发系数，信息素挥发系数从大到小排序为：ρr>ρc>ρs； 然后设置蚁群数量，晴天时蚂蚁数量ms， 阴天时蚂蚁数量mc(

2.2 信息素更新的改进

在最大最小蚂蚁系统中，只允许最优的蚂蚁留下信息素，导致其它路径的信息素随着迭代次数的增加而减少，这种方式虽然增强了最优路径的寻找，但同时增加了蚂蚁陷入局部最优的可能性。针对此问题，通过设置阈值，统计最优路径出现的次数，当时出现的次数大于阈值时，在式(3)更新的基础上，用式(4)再进行信息素的更新，该方式保持最优路径上的信息素不变，但增加其它路径上信息素，使得路径上信息素浓度差减小

(4)

2.3 VW-MMAS算法流程

步骤1 初始化各参数k,α,β,Q,Iternation，初始信息素设置为τmax， 迭代次数NC=0；

步骤2 按照2.1所述，设置3个随机挥发系数ρr,ρc,ρs及对应的蚁群数量mr,mc,ms, 在每次循环结束后随机选择一个挥发系数及对应的蚂蚁数量，作为当前迭代下的挥发系数及蚂蚁数量；

步骤3 统计信息素挥发系数ρr连续出现的次数是否大于阈值，若是转步骤2，否则转步骤4；

步骤4 将m只蚂蚁随机放入到n座城市中，并将城市放入禁忌表tabu中；

步骤5 每只蚂蚁按照概率(式(1))选择下一次要访问的城市，并将该城市放入禁忌表中，直到遍历完所有城市，计算其路径长度，并将每只蚂蚁的路径长度保存在distance_list中；

步骤6 当每只蚂蚁均遍历完城市之后，保存当前迭代最优路径bestRoute以及对应最短路径长度minDistance；

步骤7 按照式(3)将从步骤5中选出来的最优蚂蚁更新信息素；

步骤8 判断最优路径长度出现的次数是否已经超过设置的阈值，如果已经超出，按照式(4)进行更新信息素；

步骤9 禁忌表tabu清空，迭代次数NC=NC+1。 如果迭代次数没有达到最大值，则转向步骤2；否则输出最优解并退出循环。

流程如图1所示。

图1 改进算法VW-MMAS流程

3 仿真实验结果及讨论

为了评估VW-MMAS解决TSP问题的性能，实验分别使用遗传算法(GA)、粒子群算法(PSO)、蚁群算法(ACO)、最大最小蚂蚁系统(MMAS)以及本文提出的VW-MMAS对TSPLIB数据库中的TSP问题进行求解比较。其中GA中重要参数取值为：交叉概率pc=0.7， 变异概率pm=0.02， 种群数量m=100； PSO中重要参数取值为：α=1，β=0.9， 种群数量m=1000； ACO中重要参数取值为：α=0.8，β=2，Q=100，ρ=0.05， 种群数量m=2/3*n； MMAS中重要参数取值为：α=0.8，β=2，Q=100，τmin=0.1/n，τmax=1，ρ=0.05， 种群数量m=2/3*n； VW-MMAS中各参数的取值为：α=0.8，β=2，Q=100，τmin=0.1/n，τmax=1，ρr=0.3，ρc=0.2，ρs=0.15， 种群数量mr=0，mc=1/3*n，ms=2/3*n。 针对8个TSP问题，每种算法最大迭代次数MaxIter=1000， 并记录算法的最优解，结果见表1。

根据表1中的结果可以看到，本文所提出的VW-MMAS算法与GA、PSO、ACO、MMAS算法相比，在大部分的TSP问题上所得解的质量更好，甚至在大规模的TSP问题也有一个很好的解，证明了VW-MMAS算法在求解TSP问题上，所得解的精度有所提升或者保持良好。图2 展示了VW-MMAS算法在求解每个TSP问题时，最优的解决方案。

表2展示了对于每一个数据集，每种算法独立运行十次，求得的每个算法的最优解、最差解、平均解以及标准差，其中最优解表示每个算法对TSP问题最好的解决方案，最差解表示每个算法对TSP问题最差的解决方案，平均解以及标准差表示算法的可靠性以及稳定性，而标准差越小，表示该算法越稳定更能找到最优解，反之标准差越大，算法的稳定性越差。

从表2中，可以看出VW-MMAS算法在所有TSP问题上最优解、最差解、标准差上取得了一个较好的性能。同时VW-MMAS算法的标准差小于MMAS算法的标准差，表明其稳定性和可靠性优于MMAS；而相比较GA、PSO、ACO这3种算法，虽然VW-MMAS在少数TSP问题上的标准差偏大，但是在整体上由于其最优解好于其它算法，并且最差解及平均解的精度均有所提高，这意味着VW-MMAS算法在寻找最优解时更稳定可靠，而其它算法更容易陷入局部最优。

表1 不同TSP问题对应算法的实验结果

图2 VW-MMAS求解TSP问题最优路径

上述仿真实验结果表明，本文提出的VW-MMAS算法在解决TSP问题具有更好的精度，与其它算法相比，提供的最优解最小且标准差较小。

4 结束语

本文提出VW-MMAS算法是在MMAS算法的基础上，引入以下机制：

(1)结合可变天气因素，提出随机信息素挥发系数和蚁群数量机制，使用多个信息素挥发系数和蚁群数量代替原本仅使用单参数求解TSP问题，增加了信息素的变化情况，增强蚂蚁的搜索能力；

(2)由于在算法运行后期容易陷入局部最优，通过考虑城市之间的距离对蚂蚁路径搜索的影响，将其作为在陷入局部最优时信息素更新方式，增加了不是最优路径上信息素的浓度，缩小了信息素之间的差距，从而扩大蚁群的搜索范围。

通过仿真实验验证了VW-MMAS算法的有效性，与其它算法相比，解的精度更好而且标准差最小，表明算法的稳定性和可靠性。

表2 不同TSP问题对应算法比较