一种记忆区间蚁群算法及其仿真分析*

刘 振 王亚蛟

（1.海军航空大学岸防兵学院 烟台 264001）（2.92706部队 宁波 315813）

1 引言

蚁群优化算法作为一种经典的启发式智能优化算法，由Dorigo M率先提出［1]，经过二十多年的发展，已经广泛应用于故障诊断［2]、路径规划［3]、图像处理［4]、网址追踪［5]等问题。由于基本蚁群容易陷入局部极值并且收敛速度慢，国内外已经有许多学者提出了很多改进的蚁群算法，例如小生境蚁群算法［6]、协同进化蚁群算法［7]等，文献［8]提出一种改进蚁群算法用于网络编码资源最小化问题，基于特定问题设定启发式信息，同时提出一种多维信息素保留体制，文献［9]将蚁群算法与迭代局部搜索算法相结合。虽然已经有诸多学者对蚁群算法进行了改进，并有效提高了蚁群算法的收敛性能，但蚁群算法作为一种仿生智能进化算法，由于其迭代寻优过程的本质特点，导致其收敛速度和收敛性能方面仍然受到一定的限制。

从当前诸多改进方法可以看出，要想提高蚁群进化算法的优化性能，在保留蚂蚁的寻优特点以及整体优化流程的基础上，必须从蚂蚁路径选择方式和信息素更新方式出发对算法进行相应改进和推广。综合以上的分析和考虑，本文提出了一种转移概率为区间概率，并且信息素更新方式具有记忆特征的记忆区间蚁群算法（memory interval ant colony optimization，MIACO），将蚁群算法的信息素浓度推广为区间数，并对蚂蚁路径的概率选择方式进行了有效的改进，同时结合人类记忆特征［10]，对蚂蚁信息素的更新方式进行了扩展。

2 基本蚁群算法及其存在的问题

对于一个具有n个城市的TSP问题，共有n只蚂蚁进行迭代寻优，当第k只蚂蚁处于第i个城市时，其选择下一个城市的访问概率可以表示为

在式（1）中，τij为第i个城市和第j个城市之间的信息素浓度，ηij表示路径长度的启发式信息，dij表示城市之间的距离，α和β分别为信息素浓度和启发式信息的重要度影响因子，allowed(k)为第k只蚂蚁的下一步允许经过的路径集合。蚂蚁根据式（1）进行迭代搜索，当经过一定的迭代次数以后，完成一次遍历搜索，更新经过的每条边的信息素浓度，更新方法按式（2）进行。

从基本蚁群算法的进化过程可以看出，每只蚂蚁都以固定概率的选择下一个节点，势必存在一定的缺陷。首先信息素浓度和启发式信息都是固定的数值，选择方式较为单调，为提高选择过程中的多样性，可考虑采用区间参数信息和区间概率的选择方式，能够保证在选择较优路径的基础上，增加寻优过程中的随机性。其次蚂蚁都倾向于选择最优路径，因而信息素浓度容易累积在局部路径上，限制了寻优能力较强的蚂蚁的全局选优能力，不能充分协同利用蚁群优化算法的勘探（exploration）和开采（exploitation）能力，可考虑对路径的更新范围推广到次优路径，并对全局更新和局部更新采用基于人类记忆的更新方式。

3 记忆区间蚁群算法的提出

3.1 区间信息素浓度的初始化方法

在以往的蚁群进化算法中，在初始时刻，都是采用统一的信息素浓度，没有体现出启发式信息指导作用，因此为了提高算法的收敛性能，在算法初始化的过程中，提出区间信息素浓度为区间数的方法，其设置方法如式（3）所示：

3.2 区间概率的转移方法

当信息素浓度为区间数时，蚁群的转移概率也为区间概率形式，选择某一节点j的概率上限为

选择某一节点j的概率下限可以表示为

当得到某一节点概率区间以后，利用最大熵［11]方法得到精确的点概率。对于概率可按照式（6）求解最优化模型，获得点概率值：

3.3 区间信息素浓度的更新方法

按照认知心理学的界定，人类记忆的特点分为长时记忆、短时记忆和瞬时记忆［12]。不失一般性，本文只考虑长时记忆和短时记忆对信息素更新的影响。蚁群算法中信息素的更新方式有效地融合人类记忆的特性，对于全局最优路径及其部分次优路径，将其归入长时记忆的范畴，即记忆较为深刻的信息素，短时记忆在人类记忆方式中对应印象并不深刻的事物，在蚁群算法中，对应于一次寻优后得到的可行路径。

蚂蚁寻优过程中的信息素按照不同记忆方式，分为长时记忆更新方式和短时记忆更新方式，分别设置长时记忆因子系数和长时记忆挥发系数，短时记忆因子系数和短时记忆挥发系数。采用基于长时记忆的更新方式，对一次迭代完成后的最优路径及其次优路径的信息素进行全局更新，而在短时记忆方式中，则利用短时记忆因子系数和短时记忆挥发系数对相应路径及其次优路径信息素进行局部更新。

3.3.1 信息素的全局记忆更新方式

信息素更新方式对提高蚁群算法的全局收敛性能具有重要的作用，但通过蚁群算法信息素的更新方式可以看出，利用这种正反馈机制，有效增加了全局最优解信息素浓度的同时，也使得最优解和其它解之间的信息素浓度差距变大。在蚁群寻优过程中，次优解中的路径片段往往是潜在最优解的部分路径片段，因此为提高算法的收敛精度和收敛速度，本文提出除了更新当前最优路径以外，同时更新适应度较优的若干次优路径，提高进化过程中蚂蚁选择的多样性。

假定此时的最优路径值为fb，判断当前路径是否满足：

当路径满足式（7）时，则对该路径进行一次全局记忆更新。引入长时记忆因子系数λL，长时挥发系数ρL，此时的信息素浓度选择使用区间数的上限进行更新，即按照式（8）进行更新：

其中

3.3.2 信息素局部记忆更新方式

当蚂蚁经过的路径并非最优路径时，将其视为短时记忆路径。基本蚁群算法路径更新和选择方式的优点在于简单易行，收敛速度较快，但收敛的时间过长并且收敛效果并不优越，无法保证取得全局最优结果。因此针对基本蚁群算法存在的问题，将所有的路径进行排序，当t时刻处于节点i的某只蚂蚁按照式（1）选择某个节点j后，按照式（9）更新信息素浓度：

在式（9）中，Δτis为该段路径片段长度值的倒数，为短时记忆因子系数，ρE为短时记忆挥发系数。若路径Lij为节点i与相邻结点之间的最短路径，假定此时的次优路径为Lik，则按照式（9）更新信息素τik(t+1)，若路径Lij并不是节点i与下一节点之间的最短路径，假定此时的最优路径为Lih，则更新路径τih(t+1)。

通过上述的描述，可以总结本文提出的记忆区间蚁群算法（MIACO）的步骤如下。

步骤1初始化算法的参数信息，包括蚁群的规模，算法的循环迭代次数，按照式（3）初始化信息素浓度，以及α、β、λL、ρL、λE及ρE等参数；

步骤2判断是否满足结束条件，不满足则继续循环迭代，即t←t+1；

步骤3依据区间概率的方式，获得蚂蚁选择下一结点的区间概率其中概率的计算可按照式（4）和（5）；

步骤4依照式（6）获得选择概率的点概率值pij，第k只蚂蚁依据pij选择下一结点；

步骤5在完成一步行进后，将其标记为短时记忆，按照式（9）进行局部信息素更新；

步骤6当所有蚂蚁都完成一次遍历后，根据式（7）选择符合长时记忆更新方式的候选路径集合，并按照式（8）进行更新；

步骤7判断是否满足迭代结束条件，满足则结束，输出最优解，否则转步骤2。

4 记忆区间蚁群算法收敛性分析

定义1：

定理1：若满足：

证明：

证毕。

5 记忆区间蚁群算法仿真验证分析

为了充分验证算法的有效性，对算法利用TSP问题进行仿真分析，设定α=1，β=1.5，ε=0.95，λL=1.2，ρL=0.90，λE=1.1，ρE=0.80，参数Q随问题规模自适应调整为了验证算法的有效性，选用五个典型的TSP问题进行仿真分析，分别是Fri26、Bays29、Eil76、KroD100及Eil101进行仿真分析。算法独立运行十次，将本文提出的记忆区间蚁群算法（MIACO）与基本蚁群算法进行仿真对比，统计结果如表1所示。

表1 TSP问题仿真结果对比

从统计结果可以看出，本文所提出的MIACO在几个典型TSP问题中都能取得较好的寻优结果，并且在某些函数能够获得理论最优值，而这在很多情况下传统ACO算法所无法达到的。但同时也注意到，本文算法的运行时间较之以前有了较为明显的增加，特别是当TSP问题的规模在不断扩大的时候。这主要是因为随着问题规模的不断增大，采用区间数进行路径更新以及利用区间概率选择路径时，问题的规模急剧变大，在增加选择多样性的同时，也增加了系统的负担，加重了系统的开销。因此本文提出的MIACO，在优化规模较小的TSP问题时，可以在计算精度和计算效率之间得到较好的平衡，当问题规模较大时，可以适当将信息素的更新方式采用传统的点概率更新方式。

为了进一步进行对比分析，将Bays29和Eil101进行仿真对比分析，收敛迭代结果分别如图1和图2所示。

图1 Bays29问题仿真对比结果

从图1和图2可以看出，利用本文所提出的MIACO，无论是取得的最优解，还是最终解的稳定性都较基本ACO有了明显的进步，显示出本文利用区间概率选择路径和信息素记忆更新方式体现出的优越性。

为进一步进行分析，以Oliver30及Eil51问题为例，将本文算法与相关文献比较，MIACO运行的结果优于大部分文献的方法，只有文献［15]的方法所寻找到的最优值略优于本文提出的方法，但算法稳定性并不如本文算法。

图2 Eil101问题仿真对比结果

表2 Oliver30问题对比表

表3 Eil51问题对比表

由表2和表3的对比结果可以看到，利用本文提出的MIACO算法，在求解Oliver30以及Eil51上都已经具备了良好的性能，其性能较文献［3]也更为稳定，充分显示出MIACO的优越性。

6 结语

本文提出一种具有记忆特征的区间蚁群优化算法MIACO。算法的最主要的特征在于将信息素浓度推广到区间数，打破了过去信息素浓度都为固定数值的局限性。在路径的挥发和增强过程中，充分考虑人类记忆特征，引入长时记忆和短时记忆更新方式，采用不同的挥发系数，从而使得在路径更新和选择过程中呈现更具层次的多样性。在本文对提出的MIACO进行了理论分析和仿真验证分析，充分证明了算法所具有的优越性。