基于非均匀变异算子的改进蚁群优化算法

第３９卷　Ｖ０１．３９　第１０期　ＮＯ．１０　计算机工程　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１３年１０月　

Ｏｃｔｏｂｅｒ　２０１３　

・人工智能及识别技术・　文章编号．１００ｏ—＿３４２８（２０１３）１０—＿０１９６＿－ｏ４　文献标识码：Ａ　中圈分类号ｚ　ＴＰ３０１．６　基于非均匀变异算子的改进蚁群优化算法　龚跃，吴航，赵飞　（长春理工大学计算机科学技术学院，长春１　３００２２）　

摘要：为解决对称旅行商问题，在改进蚁群优化算法的基础上，提出一种引入非均匀变异算子的改进算法。在路径寻优时采用　改进的蚁群优化算法，且在完成一次循环迭代后，运用非均匀变异算子对已完成该次任务的蚁群进行变异处理，从而加快算法收　敛速度，经过Ｊｖ次进化直至达到满意结果。仿真结果表明，在寻最优解的能力和算法稳定性方面，该算法比基本蚁群算法和蚁群　优化算法更强。　关健词：旅行商问题；蚁群优化算法；变异算子；遗传算法；非均匀变异　

Ｉｍｐｒｏｖｅｄ　Ａｎｔ　Ｃｏｌｏｎｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　０ｎ　Ｎ０ｎ．ｕｎｉｆ０ｒｍ　Ｍｕｔａｔｉｏｎ　Ｏｐｅｒａｔｏｒ　ＧＯＮＧ　Ｙｌｕｅ．ＷＵ　Ｈａｎｇ，ＺＨＡＯ　Ｆｅｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｃｈｕｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｃｈｕｎ　１　３００２２，Ｃｈｉｎａ）　［Ａｂｓｔｒａｃｔ］Ｔｈｉｓ　ｅｓｓａｙ　ｐｕｔｓ　ｆｏｒｗａｒｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｏｆｔｈｅ　ｖａｒｉａｂｉｌｉｔｙ　ｏｆｎｏｎ—ｕｎｉｆｏｒｍ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ．Ｉｔ　ｍａｋｅｓ　ｔｈｅ　ｐａｔｈ　ｏｐｔｉｍｉｚａｔｉｏｎ，ｗｈｉｃｈ　ｕｓｅｓ　ｏｐｔｉｍｉｚｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｃｏｍｐｌｅｔｅ　ｔｈｅ　ｔａｓｋ　ｏｆ　ａｎｔ　ｃｏｌｏｎｙ　ａｆｔｅｒ　ｔｈｅ　ｃｏｍｐｌｅｔｉｏｎ　ｏｆ　ｏｎｅ　ｉｔｅｒａｔｉｏｎ　ａｎｄ　ｎｏｎ—ｕｎｉｆｏｒｍ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ　ｍｕｔａｔｉｏｎ．Ｉｔ　ｃａｎ　ｓｐｅｅｄ　ｕｐ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｓａｔｉｓｆａｃｔｏｒｙ　ｒｅｓｕｌｔｓ　ａｒｅ　ｒｅａｃｈｅｄ　ａｆｔｅｒ　Ｎ　ｅｖｏｌｕｔｉｏｎｓ．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ｔｈｅ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ａｎｄ　ｓｔａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ａｒｅ　ｂｅｔｔｅｒ　ｔｈａｎ　ｔｈｅ　ｂａｓｉｃ　ａｎｔ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ａｎｔ　Ｃｏｌｏｎｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍ．　［Ｋｅｙ　ｗｏｒｄｓ　ｌ　Ｔｒａｖｅｌｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ（ＴＳＰ）；Ａｎｔ　Ｃｏｌｏｎｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍ；ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ；Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ（ＧＡ）；　ｎｏｎ．ｕｎｉｆｏｒｍ　ｍｕｔａｔｉｏｎ　Ｄ０Ｉ：１０．３９６９４．ｉｓｓｎ．１０００—３４２８．２０１３．１０．０４ｔ　

１概述　旅行商问题（Ｔｒａｖｅｌｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ，ＴＳＰ）是著名　的ＮＰ问题，在各个领域都有着广泛运用。把此问题描述为：　存在，２个城市　｛ｖｌ，Ｖ２，…，１；ｉ｝且ｉ∈｛１，２，…，ｎ），已知其任意　两两城市之间的距离为　，求从某座城市Ｖｘ出发，遍历所　有已知的　ｖ　城市，且任意一座城市有且只能经过一　次，最后再回到出发城市　，使得总路程三最小。　从描述中可知，若求解ＴＳＰ问题的规模与城市数目ｍ　是以指数增长的。所以，城市数量越多，就很难精确地求　出其最优解（求出其最优解所花费的时间将很长）。如当　ｍ＝７６时，城市之间存在的可能的路径７６　７／２＝９．４２７ｅ＋１　１０。　这是一个巨大的数字，而在实际应用中，并非需要最优解，　在权衡了代价问题，应用中可以接受一个有效的无限接近　最优解的优解，此时，需要寻找一种近似求解算法。　针对ＴＳＰ问题，提出解决算法主要有模拟退火算法、　遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＧＡ）、蚁群优化（Ａｎｔ　Ｃｏｌｏｎｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）算法：如随机扰动蚁群算法…；改进蚁　群算法运用于系统设计Ｉ２】、中间件设计【３　及任务调度【４　；蚁　群算法收敛速度的分析　等。此外，也有很多研究者提出融　合ＧＡ算法和蚁群优化算法的思路，如文献【６】提出带杂交　算子的蚁群优化算法，文献［７］提出运用变异算子具有变异　特征的蚁群优化算法，文献［８］提出同时具有杂交算子、变　异算子的融合遗传算法，即改进的蚁群优化算法。　将遗传算法与蚁群优化算法融合的目的就是利用蚁群　优化算法的信息素克服遗传算法不能利用系统中的反馈信　息造成无为冗余迭代的缺点，同时，也是借用遗传算法的　快速全局搜索能力解决蚁群优化算法速度慢的缺陷。在前　文提出的融合算法中，无论是杂交算子还是变异算子，都　没有随着系统迭代的不同时期对杂交算子的杂交点或者变　异算子的变异做出相应的变化。为此，本文提出一种基于　非均匀变异算子二次搜索的改进蚁群优化算法。在不同的　

基金项目：国家“８６３’’计划基金资助项Ｎ（２００６ＡＡ７０１３０６）；国家科技型中小企业技术创新基金资助项目（０５Ｃ２６２１２２００３７８）　作者简介：龚￣（１９６０一），男，教授，主研方向：网络通信；吴航、赵飞，硕士研究生　收藕日期：２０１２．０８．１３　修回日期：２０１２—１　１－１２　Ｅ－ｍａｉｌ：ｇｏｎｇｙｕｅ８８８８７８＠ｓｉｎａ・ｔｏｍ　第３９卷第ｌ０期　龚跃，吴航，赵飞：基于非均匀变异算子的改进蚁群优化算法　１９７　演化时期，蚂蚁种群将会有不同的突变率，发生突变的蚂　蚁变异点只限制在全程路径的前段部分，后段部分由变异　后产生的新个体，其路径长度基本不优于其父代。　２　蚁群优化算法基本原理　人工蚁群优化算法由文献［９－１０］提出，文献［１１］对其进　行了优化，该算法的设计是受到人们对自然界中真实的蚁　群集体找穴和觅食行为的启发。具体蚂蚁找穴和觅食的行　为表现为：蚂蚁在找穴或觅食过程中会受到自身在行进途　中在所经过路径上所释放激素的影响。当蚂蚁在行进选择　路径时会被激素较浓的路径所吸引，往激素浓的方向行进。　如此一来，就会有越来越多的蚂蚁选择激素浓度强的路径，　而这条路径上激素的强度自然就会越来越大。这样久而久　之蚂蚁的群体就会表现出一种信息正反馈的现象。随着时　间的迁移，较短路径上的激素将会越来越浓。　３基本蚁群优化算法的ＡＳ模型　为解决ＴＳＰ问题，最先运用的是基本蚁群优化算法的　ＡＳ（Ａｎｔ　Ｓｙｓｔｅｍ）模型。在模型中有如下定义：蚂蚁的数量为　ｍ，城市的数量为　，城市之间的距离为ｄｏ．（ｉｄ＝ｌ，２，…，　），城　市ｉ、城市，之间路径上所残留的信息素量为ｚ（ｉｊ），城市ｖ　到城市ｖ／的启发函数为ｔｌ（ｉｊ）（蚂蚁从城市ｖ　转移到城市ｖｊ　的期望度），ｎ为信息启发因子，　为期望启发因子，这２个　参数是调整信息与期望度的权重，　为第ｋ只蚂蚁还未经　过的城市。则蚂蚁ｋ从城市ｖ　到城市　的转移概率函数为：　＝　［　（ｆ，　）］　×［　（ｆ，　）］　［　（ｆ，　）］　×［７７（ｆ，明　ＳＥＣｋ　０　Ｊ∈　（１）　ｏｔｈｅｒ　在蚂蚁每走完一步或者完成一次所有城市的遍历后，　要对残留信息素进行更新，这样可以避免残留信息素量过　多而掩没了启发信息。更新公式如下：　ｍ　（ｆ，　）÷一（１－ｐ）ｘ　ｚ＇（ｉ，　）＋∑△　（ｆ，　）　ｋ＝ｌ　（２）　其中，Ｐ是信息素挥发因子；而△　（　，／）是第ｋ只蚂蚁经　过路径　的信息素增量；∑△　（ｆ，Ｊ）是所有蚂蚁在路径／ｊ　ｋ＝ｌ　上的总信息素增量。　在ＡＳ模型中，根据信息素更新策略的不同，提出　３种不同的模型：Ａｎｔ—Ｃｙｃｌｅ模型，Ａｎｔ－Ｑｕａｎｔｉｔｙ模型及　Ａｎｔ．Ｄｅｎｓｉｔｙ模型【Ｊ　。这３种模型的不同之处就是对　△　（ｆ，Ｊ）的定义方式的不同。具体如下：　（１）在Ａｎｔ—Ｃｙｃｌｅ模型中：　ｒ　ｎ　△　（ｆ√）：』　√　是第七只蚂蚁本次循环路径　ｆ　０否则　（２）在Ａｎｔ－Ｑｕａｎｔｉｔｙ模型中：　“）：　腿　只蚂蚁经过路径　ｌ０否则　（３）在Ａｎｔ－Ｄｅｎｓｉｔｙ模型中：　△　（　√）＝｛　是第　只蚂蚁经过路径　

在解决对称ＴＳＰ问题时，Ａｎｔ－Ｃｙｃｌｅ模型的性能较好。　４蚁群优化算法的ＡＣＳ改进模型　在ＡＳ的基础上，针对ＡＳ收敛速度慢，易早熟的缺陷，　后期又提出改进的模型ＡＣＳ（Ａｎｔ　Ｃｏｌｏｎｙ　Ｓｙｓｔｅｍ）　。在ＡＣＳ　中基于ＡＳ做了一些简单的修改：　（１）蚂蚁的转移规则：　

Ｐ　：ａｒｇ　Ｚ　ｍａｘ｛［　（　，　）］　×［７７（　）］　）ｇ≤　。　

Ｉ　。ｔｈｅ　（３）　引入参数ｑ０（０≤ｑｏ≤１），这里ｑｏ称之为蚂蚁犯错因　

子；而ｑ为一在区　０，１］的随机数。当ｑ≤ｑ　时，蚂蚁将　

沿着Ｉ彳（ｆ，　）ｌ“×Ｉ　７７（ｆ，　）Ｉ　最大的路径方向前进；而当　ｇ＞　时，蚂蚁就会概率性的犯错，不一定朝最大的方向前　进，这样就丰富了蚁群的解空间。　（２）局部更新规则：　在蚂蚁完成一次城市转移后，会对本次转移城市之问　路径上的信息素执行如下更新：　（ｆ，　）＋－－－（１一Ｐ）ｘｒ（ｉ，Ｊ）＋ｐｘＡｒ（ｉ，Ｊ）　（４）　（３）全局更新的修改：　在ＡＣＳ模型中，并非所有蚂蚁在完成一次循环后都进　行全局更新。在ＡＣＳ中只会对在本次循环中路径最优蚂蚁　的路径进行更新，具体更新规则如下：　（ｆ，　）一（１一　）×　（ｆ，ｊ）＋ａ￣Ａｒ（ｉ，　）　

／）＝譬　（５）　

其中，ａ是控制全局路径上残留信息素的量因素；Ｌ为本次　循环最优路径的长度。　蚁群优化算法的缺陷为：早熟，收敛速度慢。早熟是　由于蚂蚁选择转移的城市时，总是趋向于信息素最强的路　径，这就造成整个蚁群的解空间不够丰富，蚂蚁创造力低　下，从而导致蚁群陷入局部最优解的陷阱。改进的蚁群优　化算法在一定程度上缓解了蚂蚁创造力低下、解空问的不　够丰富，有效地避免了早熟现象，提高了收敛速度。但是　如果在蚁群完成一次迭代后，融入ＧＡ算法，利用ＧＡ算　法中的变异算子，对蚁群中的部分个体实施变异，然后再　让变异的个体进行二次的城市遍历，从而产生新个体，将