基于最好最差蚂蚁路径差异的奖惩蚁群算法

(广东石油化工学院 计算机与电子信息学院,广东茂名,525000)

1 引言

蚁群算法(Ant Colony Optimal, ACO)是一种基于种群的启发式智能搜索算法，是由意大利学者Dorigo M.等人提出的[1]，具有全局优化、良好的可扩充性，支持并行分布式计算等特点。作为一种概率搜索算法，蚁群中的蚂蚁运动是随机的，容易陷入局部最优而无法找到全局最优解。近年来的研究对基本蚁群算法提出了一些改进，如ACS(Ant Colony System )系统，MAX-MIN蚁群系统(MAX-MIN Ant System, MMAS)，至今的实验研究表明，ACS和MMAS是目前蚁群算法中公认的效果较好的两种算法[2]，特别是MMAS算法，在采用最优蚂蚁的路径信息更新信息素的同时限制信息素的范围，以防止信息素的过度累积或过小，保证了收敛和探索的平衡,取得了较好的效果且运算速度较快。但信息素的更新没考虑不同路段的差异性，导致算法存在搜索效率低和解的稳定度差等缺点[3]。本文在MMAS算法的基础上，提出基于最好最差蚂蚁路径差异奖惩的信息素更新策略，通过比较最优最差蚂蚁的路径差异，进一步突出不同路段对路径的差异贡献，实施区分奖惩的信息素更新策略，增强信息素释放的针对性，加快算法的搜索效率和增加最优解的稳定性。

2 蚁群算法简介

其中，allowedk表示蚂蚁k下一步允许访问的城市的集合，访问过的城市，不允许重复访问。

蚂蚁完成一次循环后，M只蚂蚁构建了路径的集合T，按式(2)，对各条路径上的信息素进行更新。

(2)

其中Ck代表了第k只蚂蚁建立的路径Tk的长度或旅行代价，Q是计算信息素的度量系数，Q的大小对算法性能影响不大，通常取100[4]。

MMAS算法在AS算法的基础上做了一些改进：只有最优蚂蚁(迭代最优或至今最优)才可以释放信息素，信息素更新策略如式(4)[3]；将信息素大小的取值范围限制在区间[τmin,τmax]内，且将信息素的初值设定为取值范围的上界。

3 基于最好最差蚂蚁路径差异奖惩的改进蚁群算法

3.1 基本思想

蚁群算法是通过种群内蚂蚁个体之间的竞争、协作实现种群整体的协同进化达到对最优解的搜索。信息素的更新策略是影响算法性能的关键因素，MMAS算法每一次迭代后，只有最优蚂蚁才可以更新对应路径上的信息素，强化了对后面蚂蚁的引导，通过限制信息素的范围，扩大了最优解区域的搜索。信息素范围的限制也使较差解被选中的概率增大了，存在太多无效搜索，影响了进化效率。

一条路径由多个路段组成，路径优劣差异主要由组成路径的路段的差异所造成。通常情况下，好的路径中含有较多的较好路段，差的路径中含有较多的较差路段。MMAS对最优蚂蚁进行奖励的策略利用了好的路径中含有较多的较好路段这一信息，如果也利用差的路径中含有较多较差路段的信息，选取较差蚂蚁的典型代表迭代最差蚂蚁，对其进行惩罚，加速较差路段信息素的蒸发，减少其出现概率，将加速解的收敛，提高解的稳定性。基于此种认识，本文通过最优最差蚂蚁路径的比对，进一步突出其差异路段在构成路径代价中的不同贡献，采取区分性奖惩策略，增强信息素释放的针对性,提高搜索效率，增加解的稳定性。

3.2 最好最差蚂蚁路径差异奖惩规则

(1) 路径矩阵的生成

一只蚂蚁k在一次求解过程中，所形成路径为Tk，路径包含的节点按顺序排列Tk(α1α2,...,αn-1αn)，αi∈{1,2,...,n},1≤i≤n。

路径中相邻的两个节点之间的路径构成一个路段，最后一个节点与第一个节点构成一个路段lαnα1，一条路径Tk有N个路段，构成路径的路段集合。

Tkc={lα1α2,...,lαn-1αn,lαnα1},αi∈{1,...,n}, 1≤i≤n;

(5)

定义一个路径Tk的路径矩阵Rk，表示路径中含有的路段。如果路段 lij∈Tkc，则rij=1；否则rij=0,如式(6)。矩阵数据可直接用于相同、相异路段、局部信息素的生成计算，提高算法效率。

(2)信息素奖惩策略

对比一次迭代内的M条路径，选择迭代最优、最差蚂蚁路径Tnbest,Tnworst，生成路径矩阵Rnbest,Rnworst，比较两者的相同或相异路段，如式(7)生成相同路段Rsame，最优路径矩阵Rnbest减去相同路段Rsame余下部分称为奖励路段Rpremium，这部分路段在最优解与最差解的差异中贡献最大，通常该部分路径中含有较好的路段(解元素)，需要进行额外奖励；最差路径矩阵Rnworst减去相同路段Rsame余下部分称为惩罚路段Rpenalty，这部分路段是导致路径整体效果差的主要因素，其中必定含有较差的路段(解元素)，所以要降低这部分路段的信息素，减弱其被选中的概率，降低对无用区域的搜索概率。

Rsame=Rnbest&Rnworst;

Rpremuim=Rnbest-Rsame;

Rpenalty=Rnworst-Rsame;

(7)

3.3 算法框架

算法流程和MMAS算法基本相同，在step4中，除利用最优蚂蚁更新信息素外，增加了本文提出的最优最差蚂蚁相异路径计算、区分奖惩的策略。

Step1.初始化，取ρ=0.02，设定τmax,τmin；按τmax初始化信息素矩阵，初始化迭代次数NC=1，NC_max为设定的最大迭代次数。

Step2.当NC≤NC_max时，进入Step3，否则进入Step6。

Step3.一次迭代内构建路径，m蚂蚁随机放在n个城市，读取路径禁忌表，按公式(2)，按照轮赌盘规则选择下一步移动城市，构建m条路径。

Step4.对比生成的m条路径，按3.2.2描述的奖惩规则，选出最好(或选择至今最优)、最差蚂蚁路径。，生成相同路段，奖励路段Rpremium，惩罚路段Rpenalty， 按式(8)、(9)生成τij。按式(10)[2]更新全局信息素。

Step5.清零局部信息素，迭代次数 NC增加1。

Step6.循环结束，输出结果。

4 实验仿真

在Matlab7.0下，实现本文算法(Premium Penalty-MMAS，PP-MMAS)和MMAS算法，实验中取α=1.0，β=5.0，m=n，ρ=0.02，Pbest=0.05，Q=100。本文算法中，奖惩系数ε=0.1，每组数据实验20次，对TSP问题测试集中的Eil51，Eil101，D198三组测试数据进行了实验。

图1为本文算法求得的eil51问题最优路线, 路线距离为426等于该问题的已知最优解[5]，三组数据实验结果如表1所示，20次实验中本文算法找到的最优解的最小迭代次数小于MMAS算法，反映了本文算法的搜索效率较高；本文算法求得的最优解的平均值优于MMAS算法，方差小于MMAS算法，说明本文算法对最优解区域的搜索引导加强，求解的质量、解的稳定度都有提高。实验数据图表均说明了算法改进的有效性。

表1 MMAS和本文算法的仿真数据结果

5 结束语

本文在MMAS算法的基础上，提出一种基于最好最差蚂蚁路径差异奖惩的信息素更新策略，通过比较最优最差蚂蚁的路径差异，进一步突出不同路段对路径的差异贡献，实施信息素区分性奖惩，增强信息素释放的针对性，强化对蚁群的搜索引导，提高了算法求解的效率和稳定度，通过一些TSP问题数据集的测试，验证了算法策略的有效性。