摘 要：分析了蚁群算法，利用蚂蚁寻求可行解的优劣来选择性的调整信息素更新策略，提出了新的信息素局部和全局更新策略，完成对蚂蚁行为的奖惩性引导，对蚁群算法进行优化。通过Matlab仿真试验分析，验证了此改进确实为优化改进，提高了蚁群算法的效率和性能。
关键词：蚁群算法； 优化； 仿真
1信息素更新策略的改进
信息素的更新方式直接影响着算法的搜索能力，并对算法有很强的导向作用。上一章讨论了信息素的多种更新方式和具体策略，无论是蚂蚁系统（AS）中的全局更新策略还是蚁群系统（ACS）中的局部更新策略都有着不一样的弊病。根据前续章节讨论的几种更新具体策略的优缺点，对信息素的更新策略进行优化。
1.1信息素全局更新策略的改进
精华蚂蚁系统（EAS）和基于排序的蚂蚁系统（ASrank）中的信息素更新策略都是有所偏向的更新方式。虽然这样可以提高算法收敛的速度，但必然会导致算法的探索性能下降，在算法之初就迅速向着最优解方向靠拢，并有可能收敛于局部最优解。
为了兼顾精华蚂蚁系统和基于排列的蚂蚁系统的收敛速率，同时可以降低收敛于局部最优解的尴尬。在这两种算法思想的启发之下，本文提出了基于排序奖惩机制的蚁群系统（Rewards and Punishments of rand-based on Ant Colony System，RP-rand-ACS）。为了可以达到扩大各边上信息素浓度的差异，指导蚁群的路径搜索过程。具体规则如下：在每一轮的路径搜索构建之后，记录所有蚂蚁构建的可行解的路径长度，然后与当前最优解的路径长度进行比较。若长度小于当前最优解的长度，则该路径上的蚂蚁在其经过的路径上释放相应的信息素，若长度大于当前最优的蚂蚁不释放信息素。
在该算法（RP-rand-ACS）中，城市 到城市 之间路径上的信息素量更新的公式如下：
其中， 表示当前最优路径的长度。而此全局信息素更新策略，使得无论是信息素的挥发还是增加性释放都只能在比至今为止的最优解长度更短或者相等的蚂蚁 所在的路径 上进行。这样既能保持了算法的朝向是持续优化，而又不像精华蚂蚁系统的更新策略容易导致算法过快的朝着当前最优解附近收敛，而产生局部最优解。蚂蚁系统的全局信息素更新策略的算法时间复杂度为 ，而该算法系统（RP-rand-ACS）中的信息素全局更新策略的算法的时间复杂度可以降低，算法之初可能接近 ，随着路径的持续搜索最终将接近或者等于 。这种搜索的导向性范围持续缩小的形式，既使得最后求解的可行解的准确度提高更具普遍性，又可以在在算法的后续中加速收敛，节省了算法的运行时间，使得系统的可行解求解速度变快。参数 同样是表示信息素的挥发速率，根据公式（1.1）新增加的信息素 乘上挥发速率 ，同样会使得信息素的量控制在旧的信息素量与最新释放的信息素的量之间。同样可以实现与最大最小蚂蚁系统（MMAS）一样的效果，把信息素的浓度限制在一定的范围之内，却只是通过很简单的公式赋值的方法。至今最优和本轮迭代最优两种更新的规则对算法产生的影响同最大最小蚂蚁系统（MMAS）也是相似的，在大规模的TSP问题中，至今最优可行解的搜索引导的优越性就显现出来了。
1.2信息素局部更新策略的改进
同时在该算法中还应用信息素局部更新策略。该算法跟其他算法的循环之后进行全局更新信息素的策略不同，而是采用类似与蚁群系统的局部更新策略。基于排序奖惩机制的蚁群系统（RP-rand-ACS）中蚂蚁在构建路径的同时对经过的路径上的信息素进行局部更新，去除掉该路径上的一些信息素，以有利于后续蚂蚁探索其他路径，增大其探索的概率。
对于每一只蚂蚁，当其经过某一条边 时，立马对此条边或路径上的信息素进行更新，公式如下：
公式中， 为此算法的信息素的局部挥发速率， 为系统预设的边上的信息素的初始值。我们这里的信息素的局部挥发率与信息素的全局更新策略里的挥发率 和是同一个参数，一般我们设定为 。而信息素的初值我们也采用动态值： 。 仍然是当前最优可行解。很明显可以发现，这种更新方式会使得被经过路径上的信息素浓度被更新之后变小，路径上的信息素浓度也就越来越低。其可以使得后续蚂蚁倾向于探索的概率变大，可以有效地避免算法进入停滞状态或者局部最优解。这里的局部信息素更新策略，若采用顺序构建或并行构建将会产生不同的结果，而本文此处采用的是并行构建的方式。
2引入状态转移控制参数
类似蚁群系统（ACS）在该算法系统中引入一个随机变量 ，此变量用来控制状态转移的所要应用的策略。在该系统中同时采用伪随机比例规则和轮盘赌两个策略。状态转移规则为了让该系统中的蚂蚁可以更好更合理的利用新路径和利用好该问题的先验知识。基于排序奖惩的蚁群系统不像蚂蚁系统一样总是倾向于信息素高的路径的随机规则，而是采用了蚁群系统的伪随机比例规则平衡了开发当前路径与探索其他新路径之间的比例关系。
在基于排序奖惩的蚁群系统（RP-rand-ACS）中，任意蚂蚁 的禁忌列表 中依照蚂蚁访问的先后顺序存储记忆各个城市结点的序号。假设蚂蚁 当前所处的城市为 ，则其下一个访问城市的序号为：
在公式中，同样的 表示从城市 可以直接到达且又不在蚂蚁 的禁忌列表 中。 和 分别表示边 上的启发式信息量和信息素量。 则是描述信息素浓度和路径长度产生的启发式信息的相对重要性的平衡性的控制参数。 就是我们引入的一个设定在区间 内的参数，用于判定算法采用何种方式的路径选择。在算法进行中系统会产生一系列的随机数 ，当随机数 时，蚂蚁 就利用公式（2.1）选择启发式信息 和信息素量的 次幂 的乘积最大的下一个城市结点运行；反之，若 ，该系统（RP-rand-ACS）将和蚁群系统采用同样的轮盘赌的策略，利用公式（2.2）来运算位于城市 的蚂蚁 选择下一个城市 作为访问节点的概率，公式如下：
是引入的重要的控制型参数。可以通过调整参数 的值来控制系统中蚂蚁搜索的偏向――探索还是开发。随机数 的取值范围也同样为 ，参数 设置一个合适的值有助于调节探索和开发之间的关系，达到有利的平衡。同样容易发现，算法中概率为 的是开发，另有 的概率为探索。
3改进算法的实现
在信息素的全局更新和局部更新规则之下，加上引入状态转移因子，本文提出的基于排列奖惩的蚁群系统，其实现步骤如下：
Step1：将各个基本参数变量初始化或者赋初值，将各边上的信息素量赋初值令 ；并且 ；给当前最优可行解赋以初值；将m个蚂蚁随机的放置到一些初始结点上；清空禁忌列表；
Step2：设置或者判断循环结束条件，即可行解的进化速率趋缓的范围值，即当前最优解和本轮迭代最优可行解的差小于一个设定值，例如10-6；设置蚂蚁的禁忌表内序列号： ；将开始时各蚂蚁所置于的初始结点定义为当前禁忌表中的首位序列号为1；
Step3：根据公式（2.2）计算可转移到的下一城市结点的各个概率；
Step4：系统随机产生一个 值，然后根据该随机数和Step3中计算出的转移概率，按公式（2.1）为每一只蚂蚁选择下一个移动的城市的序号；
Step5：蚂蚁 从城市 移动到城市 后，立即根据信息素的局部更新策略公式（1.2）进行更新，并将蚂蚁所处的城市序号放入禁忌列表中；
Step6：循环执行Step3到Step5，直到每个蚂蚁都回到构建形成一个哈密顿回路，即可行解；
Step7：计算全部蚂蚁产生的哈密顿回路的长度，找到长度比当前最优解的长度更小或者相等的所有可行解和产生这些可行解的路径的蚂蚁，利用信息素的全局更新策略更新，根据公式（1.1）把这些路径上的全部信息素值进行更新；
Step8：把当前最优路径赋值给 ，清空全部蚂蚁的禁忌列表；
Step9：跳转到Step2，即再次从Step2开始根据既定约定条件判断是否满足结束条件，若满足，则本算法循环结束并输出运算结果；否则，跳转到Step3，再次进行循环，直到达到算法指定的最大迭代次数或连续若干轮循环内没有更好的可行解出现为止。
4改进算法的排序奖惩机制
基于排序奖惩的蚁群系统（RP-rand-ACS）算法，实际上就是系统中的蚂蚁如果构建出的可行解长度比当前最优解更短，即优于当前最优解或前一轮的最优解。该蚂蚁在构建路径方面取得了“进步”，那么就对其进行奖励。信息素的全局更新策略公式（1.1）实际上隐含了对路径长短的排序和奖惩激励机制，构建的路径越短信息素更新的加权系数越大。公式中的 相当于信息素更新的权重系数。在每一轮的构建中， 是相对不变的，若蚂蚁构建的路径长度越短，即 越小，就会导致整个系数值更大并且暗含了排序之意。而没有取得“进步”的蚂蚁，即构建的可行解不如当前最优路径的时候，就对此蚂蚁进行惩罚，惩罚措施就是不进行信息素的释放。并且信息素的局部更新策略又使得不“进步”蚂蚁的路径上的信息素被进一步削弱。
5仿真实验
为了验证改进的算法的可行性，现在用基于排序奖惩的蚁群系统（RP-rand-ACS）进行了算法的实验仿真。实验环境为：内存为512M，硬盘为20G 的Pentium® Dual T2330上运行，运行的操作系统为Windows XP Professional，使用V C++ 6. 0编程，并用matlab7.0实现结果和线路呈现。实验数据结果如表3-1所示：
（1）基本蚂蚁系统算法
基本蚂蚁系统算法在第38代中找到了最优解，最优路径为：
9 → 10 → 22 → 3 → 8 → 30 → 19 → 20 → 23 → 25 → 7 → 28 → 27 → 31 → 15 → 21 → 1 → 5 → 6 → 12 → 11 → 18 → 26 → 29 → 14 → 13→ 24 → 17 → 16 → 4 → 2
最优路径演化图如图3-2所示：
图5-1最优路径演化图
（2）基于排序奖惩的蚁群系统算法，在第31代中找到了最优解，最优路径为：
9 → 10 → 22 → 3 → 8→ 19 → 20 → 23 → 25 → 7 → 28 → 27 → 30→ 31 → 15 → 21 → 1 → 5 → 6 → 12 → 11 → 18 → 26 → 29 → 14 → 13→ 24 → 17 → 16 → 4 → 2
最优路径演化图：
通过基于排序奖惩的蚁群系统算法的路径寻优，构建出来的最优路径。
通过上述仿真实验可以发现，改进的算法（RP-rand-ACS）与传统的基本蚂蚁系统（AS）算法相比具有相对更强的寻优能力，寻求到的可行解也比传统的基本蚂蚁系统算法具有更好的多样性。另一方面，该算法在保证了可行解的质量的前提下，提高了运行速度，对原有的算法确实进行了优化改进。该算法在仿真实验中，对较少的结点问题进行仿真时可以呈现出良好的性能。而当其应对较大规模的路径寻优时，则会出现运行时间较长的问题。
参考文献
[1] Colorni A,Dorigo M,M aniezzo V.Distributed optimization by ant colonies EAT.Ins Proe.Europe Conf.Artificial Life[C],Paris:Elsevier Publishing, 1991, 134-142
[2]Eric Bonabeau,Marco Dorigo,Guy Theraulaz.Swarm intelligence from natural to artificial systems[M].New York,Oxford University Press,1999.
[3]梅红, 王勇, 赵荣齐. 基于蚁群优化的前向神经网络.武汉理工大学学报(交通科学与工程版),2009,3:531-533
作者简介：，孟凡聪（1983- ），男，汉族，山东潍坊人，软件工程硕士，福建工程学院软件学院助教，研究方向：算法分析；
通讯地址：福建省福州市鼓楼区福州软件园C区 福建工程学院软件学院 孟凡聪 收
邮编：350003
手机：18606937310
作者简介：，孟凡聪（1983- ），男，汉族，山东潍坊人，软件工程硕士，福建工程学院软件学院助教，研究方向：算法分析； 通讯地址：福建省福州市鼓楼区福州软件园C区 福建工程学院软件学院 孟凡聪 收 邮编：350003 手机：18606937310
推荐访问:奖惩 算法 排序 一种基于排序奖惩的蚁群算法 基于排序加权的蚁群算法 基于蚁群算法的