基于拥挤度的改进蚁群算法

(上海大学 机电工程与自动化学院，上海 201900)

蚁群算法是意大利学者Dorigo于1992年提出的一种群智能仿生算法[1]。该算法模拟蚁群觅食行为，蚁群会在觅食所经过的路径上留下一种名为信息素的化学物质[2]。蚂蚁之间靠感知信息素强度寻找最优觅食路径。蚁群算法具有高鲁棒性、分布式计算、正反馈、易与其他算法融合的优点[3]。而这些优点可用于解决一系列NPC(Non-Deterministic Polynomial Complete)问题。目前，蚁群算法已被广泛用于解决旅行商问题、指派问题、调度问题以及图着色等问题[4]。但蚁群算法也存在着一些问题，如搜索时间较长、易陷入局部最优、收敛速度过慢、易产生停滞现象[5]。针对这些不足，很多专家学者都提出了自己的改进方法。例如安葳鹏[11]通过引入最大代价与最小代价来优化蚁群算法的信息素更新机制；方春城[12]将网格地图模型与蚁群算法相结合来优化机器人行走路径。

蚁群算法的核心技术在于其信息素更新方式和状态转移概率选择[6]。其中信息素矩阵的构造尤为关键，信息素引导着蚂蚁做各种路径选择，蚁群的状态转移也基于蚁群的信息素矩阵。因此对信息素矩阵的重新构造便可提供一种改进的蚁群算法，比如ACS(Ant Colony System)算法[7]、MMAS(Max-Min Ant System)算法[8]、自适应蚁群算法[9]、混合行为蚁群算法[10]。

为改善蚁群算法易陷入局部最优的情况，本文引入拥挤度算子来增强蚁群之间的信息交流，改善信息素矩阵的分布，避免蚁群因局部信息素过大而过早陷入停滞状态。同时通过全局信息素更新和局部信息素更新对信息素矩阵进行自适应调整，提前预防早熟现象。在路径调整过程中结合一项高效的变异操作，在增强全局搜索能力的同时又提高算法的收敛速度。

对于拥挤度概念，前人也有相关研究，王剑[13]将鱼群算法的拥挤度因子引入蚁群算法，但其仅考虑了整体的拥挤情况，未考虑局部路径情况，而本文将两种情况都纳入考虑范围。而对于邻域搜索概念，段海滨[14]将连续空间上的相邻下一节点定义为邻域。而本文中是将离散空间中以某一点为圆心的附近若干点划分为邻域,着重缩小搜索范围，提高搜素效率。

1 传统蚁群算法模型

本文以平面TSP(Traveling Salesman Problem，旅行商问题)为例求解基本蚁群算法模型。该模型采用全局信息素更新和局部信息素更新相结合的方法，信息素的挥发和释放动作只对至今全局最优蚂蚁所走的路径更新。蚂蚁每选择一条路径，都通过局部信息素更新规则削弱该路径上的一定量信息素，增加蚁群探索其他路径的可能性。

1.1 状态转移规则

在蚁群系统中，m只蚂蚁在n个城市中并行构建TSP路径。初始时刻，蚂蚁被分别置于随机选出的城市中，各城市之间每条路径的信息素皆相等。在构建路径的过程中，蚁群采用一种伪随机比例规则来确定蚂蚁k下一步将要访问的城市j。其过程为

(1)

(2)

采用这种伪随机比例规则产生的城市，既可以保证蚂蚁利用路径的先验知识选择当前最有可能的最优解，又以一定的概率探索新的路径。通过调整参数q0，可以调节算法对新路径的探索概率，达到蚁群算法在探索新路径和保持较优路径之间的平衡。

1.2 局部信息素更新

在每只蚂蚁经过一条路径时，都将会对该路径上的信息素进行局部更新，即

τij=(1-ζ)·τij+ζ·τ0，τ0∈(0,1)

(3)

式中，ζ为一固定参数;τ0为初始信息素的值，一般取值为1/n·Lnn。其中，Lnn为由最近邻域启发式方法得到的路径长度。通过局部信息素的更新，达到削弱该条路径信息素的效果。使该条路径信息素不会过大增长，从而保证了搜索其他路径的可能，避免陷入局部最优解。

1.3 全局信息素更新

在所有蚂蚁都遍历城市之后，开始进行全局信息素更新。全局信息素更新只对当前最优蚂蚁所走的路径作用。全局信息素更新公式为

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

(4)

式中，ρ为信息素挥发因子；Δτij是信息素增量，由蚂蚁遍历一周释放的信息素与最优路径相除得到。

2 蚁群算法的改进

针对蚁群算法易陷入停滞的缺陷，本文提出一种基于拥挤度的动态信息素蚁群算法(Dynamic Pheromone Ant Colony System,DPACSC)，在蚁群释放信息素的过程中实时监测当前路径信息素含量和蚁群路径的情况，为蚂蚁提前做好分流准备，增加蚂蚁探索其他路径的可能，提前做好主动防御工作。

2.1 拥挤度

在路径选择过程中，蚂蚁会倾向于寻找信息素大的路径，同时由于蚁群算法的正反馈机制，信息素大的路径在搜寻过程中信息素的累积会越来越大，进而导致蚁群算法陷入局部最优，直至停滞。为了增加蚁群算法路径选择的多样性，提高蚁群算法全局搜索的能力，本文提出静态拥挤与动态拥挤的概念。

定义1 静态拥挤。设Pij是蚁群在某一轮循环后从i城市到j城市的路径转移概率。δ为接近于1的一个常数。当Pij>δ时，则定义路径i→j发生全局拥挤。

定义2 动态拥挤。设蚂蚁的总数为m,蚂蚁在时刻t时位于城市u，且在t+1时刻选择到达城市v的蚂蚁总数为k，则在时刻t，路径u→v的动态拥挤度定义为

(5)

2.2 状态转移规则更新

为防止蚁群算法过早集中于某些路径，增大蚁群全局搜索能力，结合拥挤度的概念，改进的状态转移规则算法为

(6)

(7)

在启发式信息相对重要性系数β的基础上增加拥挤度参数，由拥挤度参数来动态控制启发式信息在路径选择中的重要性，当该条路径在某一时刻变得拥挤时，则相对降低它在候选路径中的比例。

2.3 信息素更新方案

蚁群算法在构建解的过程中，会产生很多无用解，具体表现为：① 产生许多重复解，一直在进行无用迭代；② 构建许多明显不是最优解的路径，例如将两个相距很远的城市作为蚂蚁路径上的相邻解。针对问题①，引入拥挤度的概念，扩大蚂蚁选择路径的可能性来降低蚁群的重复解。同时加入下文的变异操作寻找更优异的解。针对问题②，提出“搜索域”概念，优先将最靠近当前城市的nk个城市置于“搜索域”中。但由于环境复杂性以及某些情况下最优解不在当前nk个城市中产生，造成漏解。因此设定如下“搜索域”方法。

假定在城市i处寻找下一城市j，首先寻找距离城市i最近的一处城市x，i→x的距离为dix，在此基础上叠加一项Δd的参数，以(dix+Δd)为半径，在此半径范围内的城市则为允许搜索的城市，其余归入禁忌表之中。

(8)

式中,allow为可搜索的城市集合；tabu为蚁群的禁忌表集合。在可选取的城市中采用伪随机概率选择公式和拥挤度结合的方法进行下一个城市选择。

2.4 变异操作

蚁群算法搜索路径的大部分操作都是对重复路径的查找。为避免这种重复操作，当路径重复次数达到S次时，则表明当前查找路径陷入局部最优解，开始进行两元素优化(2-opt)的变异操作[15]。在当前最优路径的城市访问顺序中选取两个城市进行互换。当互换的城市并非相邻顺序的城市时，则将两个城市之间的顺序完全颠倒。例如，TSP城市集C={c1,c2,c3,…,cn}，假设其中有两个城市节点i,j。交换节点i在j的前面，即顺序T=v1→v2…vi-1→vi→vi+1…vj-1→vj→vj+1…vn→v1,当进行交换顺序时，将vi到vj之间的顺序完全交换，即新的顺序为T=v1→v2…vi-1→vj→vj-1…vi+1→vi→vj+1…vn→v1。这时检验交换后的路径长度，若优于原路径长度，则替换原搜索顺序。在搜索时从前往后依次进行检验。本文在此基础上再次进行改良，针对2-opt算法的盲目实验替换，结合本文“搜索域”方案，使交换的两元素限定在一定区域内，减少了实验的操作步骤。经过试验，本方法可一定程度上加快实验收敛速度，基本可保证在100次迭代左右便搜索到较好的路径。

3 算法框架

基于拥挤度的动态信息素蚁群算法的步骤表述如下。

① 初始化参数α,β,q0,ζ,ρ,δ，蚂蚁变量t=1,城市变量m=1,循环次数NC。

② 查看是否达到最大的循环次数NC，若是，则直接退出算法，若不是，则更新各条路径信息素的值，保留各次最优路径。

③ 查看搜索相同路径次数是否超过S，若是,则进行局部2-opt的路径优化，如发现更优路径，则用该路径来替换搜索路径。

④ 随机分配蚂蚁至各个城市，并将该城市计入禁忌表之中。

⑤ 判断是否所有的蚂蚁均已完成搜索，若是，则返回步骤②，否则从第t+1只蚂蚁开始搜索路径。

⑥ 判断是否蚂蚁已完成所有城市的访问，若是，则返回步骤⑤，否则从第m+1个城市开始搜素路径，并检查搜索路径概率是否大于δ。

⑦ 按“搜索域”大小搜索可访问城市，并计算各条路径上的拥挤度大小。

⑧ 按上述的状态转移规则选择下一个城市的选取点，并将该点置入禁忌表中，返回步骤⑥。

⑨ 展示各条最优路径。

4 仿真实验

为使算法更具说服力，选用国际上经典的TSPLIB库中的12个案例(Eil51、Berlin52、St70、KroA100等)作为标准实验数据进行试验。对参数的初始化固定如表1所示。其中，蚂蚁数量设为城市数量的2/3， “搜索域”间距Δd设为初始间距dix的1/3。

利用Eclipse编写程序验证算法。表2为各TSP的官方数据。各问题求解结果如表3所示。图1～图8为所得路径结果。

表1 各参数设置

表2 各TSP官方最好记录

表3 典型TSP问题求解对比实例

SD:standard deviation

图1 KroA100

图2 St70

图3 Berlin52

图4 ch130

图5 Eil101

图6 KroA150

图7 KroB150

图8 TSP225

从表3可以看出，经过改进的蚁群算法在验证各个TSPLIB问题时，都可得到接近最优解的路径。从各算法性能比较(表5)中可以看出，有些结果要优于文献中的研究结果。标准偏差也在理想范围之内，说明在各个循环过程中，改进的蚁群算法可以得到较优解。对比文献中的结果，所提出的方法产生了较为理想的结果。其中，对比WFA with 2-opt可以看出，在城市数目较小的情况下，WFA with 2-opt可以得到较好的路径解，但随着城市数目增大，解质量开始下降。反观本算法，虽然在城市数目较小的情况下并未取得最优解，但与最优解的偏差都在可接受范围内。即使城市数目开始增多，但解质量并未随之变差，依旧在最优解附近。如KroA200问题中，WFA with 2-opt和PSO-ACO-3opt问题的标准偏差都已经很大，说明解已经开始不稳定。其中在和PSO-ACO-3opt算法的对比中，增加了两者算法的运行时间比较，如表4所示。

表4 算法的运行时间对比

通过表4可以看出，对于同一个TSPLIB问题，在相同的搜索次数内，PSO-ACO-3otp在求解时，将会花费较多时间，即使是最基本的Eil51问题，PSO-ACO-3opt将花费140.50 s的时间，而本算法只需6.737 s便可完成任务，在效率方面本算法更加优异。

表5 各算法性能比较

5 结束语

针对蚁群算法易陷入局部最优解的问题，提出了一种基于拥挤度的蚁群优化算法。通过引入静态拥挤度算子和动态拥挤度算子，蚁群算法参数可跟随信息素浓度变化而动态更新，增强了蚁群之间的信息交流，达到了改善信息素矩阵的目的。改进的蚁群算法能够提前主动预防早熟和停滞现象，提高了蚁群算法的全局搜索能力。同时加入的“搜索域”规则在求解过程中首先淘汰大部分劣质解，使算法在很少的步骤内就得到一组全局次优解，而引入的变异算子能对次优解进一步优化，增强蚁群算法的局部搜索能力。

蚁群算法作为一种新兴的仿生优化算法，还有许多值得研究的地方，很多理论问题也有待进一步探讨。但是随着研究的深入，蚁群算法也将和其他模拟进化算法一样，能够获得越来越多的应用。