基于相邻节点间特征改进的蚁群算法

刘阳阳　庄恒国　张亚楠

摘要摘要：蚁群算法是解决组合优化问题比较有效的方法。该方法采用分布式并行计算机制，易于与其它方法结合，并具有较强的鲁棒性，但也存在搜索时间长、易陷入局部最优解等问题。在研究多种改进的蚁群算法基础上，提出一种改进的蚁群算法来求解TSP问题。改进算法根据相邻节点间的相对距离特征，对路径解进行变异，诱导蚁群快速寻找到更优解。同时引入信息素挥发因子自适应调整机制和公共路径思想，调节算法收敛速度，以保证算法的全局搜索能力。实验结果表明，改进算法相比于MMAS、DMPSOACO等算法，求解精度和收敛速度都有所提高，所选取的测试实例中，平均解相对已知最优解的偏差百分比平均可达到0.63%。

关键词关键词：蚁群算法；组合优化问题；相邻节点

DOIDOI：10.11907/rjdk.171001

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2017）005003103

0引言

蚁群算法是一种模拟自然界中蚂蚁觅食行为的启发式搜索算法，于20世纪90年代由意大利Dorigo等学者[13]提出。后续各国研究者也提出多种优秀的蚁群优化算法求解组合优化问题。例如，文献[4]提出了蚁群系统（Ant Colony System，ACS），相对于早期的蚂蚁系统（Ant System，AS），强调了对新路径的开发程度，以某一既定概率选择最优路径，不像AS确定性地选择最优路径；文献[5]为了克服蚁群算法中存在的停滯问题，提出了一种最大-最小蚂蚁系统（Max-Min Ant System，MMAS），将信息素控制在一定范围内，寻径结束后仅更新最优路径的蚂蚁信息素；文献[6]在蚁群算法中引入遗传算法思想，以达到提升ACS算法性能的目的；文献[7]对信息素模型进行了改进，建立了以城市为端点、城市间路径为中心轴的能量等势场模型；文献[8]为描述寻优过程中的全局信息，定义了一种新的方向信息素，较好地克服了算法停滞现象，提高了解的全局性。本文从蚁群算法在旅行商问题中（Travelling Salesman Problem，TSP）的应用出发，提出了一种基于路径特征改进的蚁群算法。本文算法根据相邻城市间的关系对路径进行变异，扩大蚁群的种群多样性，以便在算法停滞前发现更短路径，不断趋向最优路径解。同时引入信息素挥发因子自适应调整机制和公共路径思想，调节收敛速度，以提升全局搜索能力。

1蚁群算法

在蚁群算法中，第k只蚂蚁由城市i选择到下一个城市j的规则是：

其中，q0是（0，1）之间的常数，q是（0，1）之间均匀分布的随机数，τij（t）表示城市i和城市j之间路径上的信息素浓度，dij为两个城市之间的距离。启发式因子α反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度；启发式因子β反映蚂蚁在运动过程中启发信息在指导蚁群搜索中的相对重要程度；allowedk表示第k只蚂蚁当前的可行城市集合。由式（1）、式（2）组成的伪随机规则倾向于选择短且信息素浓度更大的一条路径移动。每次搜索结束后，每条路径的信息素按公式（4）～（6）进行更新：

τij（t+1）=（1-ρ）τij（t）+ρΔτij（4）

Δτij=∑mk=1Δτkij（5）

公式（5）中，Δτkij为：

Δτkij=QLk，若第k只蚂蚁在本次循环经过路径（i，j）0，若第k只蚂蚁在本次循环不经过路径（i，j）（6）

其中，m表示蚂蚁总个数，ρ表示信息挥发速率，τij表示蚂蚁在本次循环中留在路径（i，j）上的信息量，Δτij表示本次循环中所有经历过路径（i，j）的蚂蚁留在该路径上信息量的增量，Q表示蚂蚁循环一周所释放的总信息量，Lk表示第k只蚂蚁在本次循环中所走路径的长度。这种信息的更新规则可以使算法信息正反馈性能增强，提高系统搜索的收敛速度。

2算法策略

2.1信息素自适应更新策略

信息素挥发因子ρ反应了整个蚁群系统的进化状态，当ρ越大，收敛速度越快，但会影响算法的全局搜索能力。通过减小ρ，增强随机性，却可能使算法的收敛速度降低。为了在“探索”和“利用”间保持平衡，文献[9]、[10]中都采用了不同的自适应调整方案来动态调整ρ值。改进算法中选用简单而有效的自适应策略来调整ρ，公式如下：

ρ（t+1）=ξ·ρ（t） []ξ·ρ（t）≥ρminρmin[]ξ·ρ（t）<ρmin（7）

式中，ρmin为ρ的最小值，以防止ρ过小而降低算法的收敛速度，ξ∈（0，1）为挥发因子调节系数。算法初期赋予ρ较大的值，以前搜索过的解被选择的可能性较大，收敛速度快。为防止陷入局部收敛，后期会逐渐降低ρ值，使未被遍历的路径信息素增大，提高了全局搜索能力。通过对挥发系数进行自适应地改变，既可以提高解的全局性，又可以保证收敛速度。

2.2路径变异思想

2.2.1蚁群寻径轨迹

本文通过城市间的相对距离分析路径特征，取Eil51和KroA100两个实例的中间解和最优解，统计路径中相邻节点间的关系。

从表1、表2可以看到，Eil51和KroA100两个实例的最优解中相邻两个城市的相对距离也较近，主要集中在[0，5）的范围内。而在中间解中，城市间距离分布不均，这是因为在算法迭代过程中，蚂蚁所释放的信息素不足以让蚂蚁快速选择长度较短的路径，前期还是选择了离自己相对较远的城市。本文将那些相对较远的城市对视为关键点对，将其进行有效变异，诱导蚁群算法快速收敛到更高质量的解。

2.2.2路径变异

依据上一小节的分析对关键点进行变异，结合局部搜索思想，本文提出一种基于路径特征改进的方法。假设当前路径为R（X1，X2，X3，…，Xn），相对距离阈值下界为Dis0，相对距离阈值上界为Dis1，当前路径长度为Len，对路径进行变异的步骤如下：

步骤1 按相对距离远近将R排序，得到Order数组。

步骤2 计算i←Order [k]，k>Dis0，记录城市点R[i+1]。

步骤3 查找与R[i]相对距离小于Dis1的点R[j]。

步骤4 计算将R[i+1]与R[j]间的路径进行翻转后的路径长度。如果长度小于Len，Len←Length（R），记录R[i+1]、R[j]。

步骤5 更新k←k+1，如果k

变异作用于每次迭代过程中所得到的路径。此外，在迭代过程中会记录蚁群最优及次优路径的公共部分，当前最优与次优路径得到的公共路径很有可能是全局最优路径的组成部分。利用公共路径寻径，不但能够减少算法中的大量重复计算，还可以诱导蚁群向最优路径变化[11]。

2.3算法步骤

综上所述，算法步骤归纳为如下：

步骤1 初始化参数：城市数、蚂蚁个数、蚁群算法迭代计数器、蚁群算法允许迭代最大次数、蚁群信息素等。

步骤2 将其中一部分蚁群，第一组按公式（1）、（2）进行城市选择，生成路径解，并对每条路径进行变异。

步骤3 记录步骤2解集中的最优和次优解，并计算出它们的公共路径。

步骤4 取步骤2的剩余蚁群，将步骤2的公共路径作为必经路段，非公共路径上的城市按公式（1）、（2）进行状态转移，与公共路径连成一条回路，生成路径解，并对每条路径进行变异。

步骤5 求解当次迭代最优解，如果小于当前最优解，更新最优和次优解，转步骤7；否则，转步骤6。

步骤6 当次迭代最优解小于当前次优解，更新次优解。

步骤7 按公式（4）～（6）更新信息素。

步驟8 蚁群算法迭代计数器加1，如果达到最大迭代次数，转步骤9，否则转步骤2。

步骤9 输出最优路径及其长度。

3实验结果与分析

初始各参数值，蚂蚁数量N_ant=城市规模/1.5，参数α=β=2.0，q0=0.5，信息素挥发因子初始值ρ=0.95，ρmin设为0.3。

表3比较了在本文算法中采用不同Dis0、Dis1值时，不同实例所得到的平均长度。

4结语

本文提出的改进算法根据路径特征对蚂蚁侦查到的路径进行变异，以丰富种群多样性，有助于跳出局部最优，增强算法的全局寻优能力。引入的公共路径和自适应调整机制可有效调节算法收敛速度。实验结果表明，在TSP问题上，改进算法相比MMAS、DMPSO-ACO算法不仅能够得到相对较好的解，收敛速度也有一定提升。平均解相对已知最优解的偏差百分比平均可达0.63%，最优解相对已知最优解的偏差百分比平均可达0.04%。在今后的研究中，会进一步分析不同参数组合之间的相互制约关系，并将算法应用到实际的组合优化问题中，以解决实际工作中的问题。

参考文献参考文献：

[1]COLORNI A，DORIGO M，MAIEZZO V.Distributted optimization by ant colonies[C].Proc of the ECAL′91 European Conf of Artificial Life.New York：Elsevier，1991：134144.

[2]DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agents[J].IEEE Transaction on Systems，Man，and Cybernetics，Part B：Cybernetics，1996，26（1）：2941.

[3]DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the travelling salesman problem[J].IEEE Transaction on，Evolutionary Computation，1997（1）：5366.

[4]GAMBARDELLA L M，DORIGO M.Solving symmetric and asymmetric TSPs by ant colonies[C].Proc of the 1996 IEEE Int Conf on Evolutionary Commutation ICEC96.Piscataway，NJ：IEEE，1996：622627.

[5]STUTZLE T，HOOS H H.Maxmin ant system[J].Future Generation Computer Systems，2000（16）：889914.

[6]TSAI C F，TSAI C W.A new approach for solving large travelling salesman problem using evolution ant rules[C].Proc of the 2002 Int Joint Conf on Neural Networks （IJCNN 2002）.Piscataway，NJ：IEEE，2002：15401545.

[7]冀俊忠，黄振，刘椿年.一种快速求解旅行商问题的蚁群算法[J].计算机研究与发展，2009，46（6）：968978.

[8]孟祥萍，片兆宇，沈中玉，等.基于方向信息素协调的蚁群算法[J].控制与决策，2013，28（5）：782786.

[9]DUAN H B，ZHANG X Y，WU J，et al.Maxmin adaptive ant colony optimization approach to multi UAVs coordinated trajectory replanning in dynamic and uncertain environments[J].Journal of Bionic Engineering，2009（6）：161173.

[10]马颖，田维坚，樊养余.量子扩展蚁群连续优化改进算法[J].计算机工程与设计，2015，36（9）：24492554.

[11]申铉京，刘阳阳，黄永平，等.求解TSP问题的快速蚁群算法[J].吉林大学学报：工学版，2013，43（1）：147151.

[12]刘全，陈浩，张永刚，等.一种动态挥发率和启发式修正的蚁群优化算法[J].计算机研究与发展，2012，49（3）：620627.

[13]ZHENG JIANGUO，WU DAQING，ZHOU LIANG.Traveling salesman problem using an enhanced hybrid swarm optimization algorithm[J].Journal of Donghua University，2014，31（3）：362367.

责任编辑（责任编辑：黄健）