新型改进量子蚁群算法及其TSP应用

赵莉+董玉民

摘要：量子蚁群算法将量子理论与传统的蚁群算法结合，是一种高效的生物进化算法，已经广泛应用到诸多领域，但算法在寻优过程中仍然普遍存在陷入局部最优解的问题。针对量子蚁群算法的不足，通过引入粒子群的学习模式来改进算法，使得种群在进化过程中有更多的可能性，避免算法早熟收敛。将提出的新型改进量子蚁群算法应用于传统TSP实验，实验结果表明改进算法对问题求解效果较好，对量子蚁群算法的性能有一定的提高。

关键词：量子技术；蚁群算法；粒子群；TSP；智能优化

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）35-0214-03

New Improved Quantum Ant Colony Algorithm and Its Application in TSP

ZHAO Li 1，2，DONG Yu-min2

（1. Qingdao Hiser Medical Group， Qingdao 266034， China； 2. Qingdao Technological University， Qingdao 266033， China）

Abstract： Quantum ant colony algorithm combines quantum theory with traditional ant colony algorithm， which is an efficient biological evolutionary algorithm. It has been widely used in many fields， but the algorithm still has the problem of falling into the local optimal solution in the process of optimization. In view of the deficiency of the quantum ant colony algorithm， the particle swarm learning model is introduced to improve the algorithm， so that the population has more possibilities in the evolutionary process， and avoid premature convergence. The new improved quantum ant colony algorithm is applied to the traditional TSP experiment. The experimental results show that the improved algorithm has better effect on the problem， and the performance of the quantum ant colony algorithm is improved.

Key words： Quantum technology； Ant Colony Algorithm； Particle swarm； TSP； Intelligent optimization

人工蚁群算法最早由M.Dorigo等人提出，是一种受自然界蚂蚁群体觅食行为启发而提出的模拟优化算法[1-2] 。该算法在被提出后即受到诸多关注，随即被广泛应用于求解旅行商问题、调度问题、指派问题等，并取得了较好的结果。但由于算法中存在着极易陷入局部最优值、收敛速度慢等不足，因此与量子计算相融合的量子蚁群算法被研究者们发现并提出。量子蚁群算法提出后，迅速引起了各界的关注与研究并很快地投入到相关领域当中，成功解答了0-1背包问题、多任务联盟问题等[3-4]。量子蚁群算法中使用量子计算所特有的二态量子比特来表示信息单元，利用量子比特的叠加性增加信息单位的可能性，从而提高算法的求解能力。传统的量子蚁群优化算法正是发挥了量子计算与蚁群算法各自的优势，使得算法能以较小的规模、较好的速度收敛于问题的解，但陷入局部最优的弊端并没有很好的避免。本文提出一種新型的改进量子蚁群算法，将量子蚁群与粒子群相配合，充分利用量子蚁群的群体性及粒子群的自学习能力，避免局部最优的发生，使得算法快速收敛于问题的全局最优。在文章最后，将提出的改进算法用于解决TSP问题，通过与传统算法求解的对比，发现改进的算法能够更好地满足求解需求。

1 改进的量子蚁群算法

1.1 蚁群算法

蚂蚁觅食的个体行为虽然简单，但由多个个体组成的全体觅食行为却给我们的研究带来了思路。以自然界蚁群为模型，研究者深入分析了蚂蚁个体及群体的行为方式，构造出了一种具有群体智能的人工蚁群系统。蚁群算法是一种随机搜索算法，通过群体的进化逐步搜索到求解的最优。算法中的蚂蚁个体在移动过程中，会释放一种名为外激素的物质以便与同伴传递信息，在此我们称之为信息素。同样，在个体行进时也会参考路径上残留的信息素浓度以概率方式确定移动的方向，以表示第k只蚂蚁从i→j的概率，则：

其中，allowedk表示第k只蚂蚁下一步允许去往的位置，分别表示信息素浓度和启发因子。

1.2 粒子群算法

粒子群优化算法起源于对自然界鸟群的捕食行为研究，是Kennedy和Eberhart共同提出的一种社会系统的模拟[5]。每一只飞鸟看作待优化问题的一个解，鸟群觅食的整体行为即为待优化问题逐步寻优的过程。若鸟群中的M只飞鸟表示为，第只飞鸟的位置和速度可以分别用向量表示为：

鸟群学习自己与群体的经验进行更新，采用交叉、变异的形式重新确立自身及全局最优，更新公式可以表示为：endprint

粒子群算法被应用于众多科学研究和工程应用，以及函数优化、图像处理等其他领域，正是由于PSO算法的简单易实现[6-7]。与其他进化算法类似，粒子群在优化进行过程中遵循优胜劣汰的规律，但鸟群寻优不采用交叉变异等行为，仅通过个体的记忆能力进行彼此之间相互合作与竞争，同时利用自身的学习能力使得优化任务得以完成。但过早的收敛会使优化结果不够精确，对于精确求解的复杂性问题不足以很好地完成优化。

1.3 量子编码

与传统的二进制编码不同，量子态不仅可以表示0状态和1状态，还可以表示二者的任意叠加状态：，其中，满足归一化条件：。若量子位表示为，则具有n个基因位的个体为：

在改进的量子蚁群算法中，用量子态表示蚂蚁所经过路径上的信息素。第k只蚂蚁的信息素矩阵可以描述为：

其中，表示该蚂蚁在路径i→j上产生的信息素浓度。

1.4 信息素更新

蚂蚁在经过某条路径时，会在该路径上留下信息素以帮助群体的其他同伴能顺利找到合适的路径，信息素会因蚂蚁的增加而增多，也会随时间而流失。在初始时刻，所有路径上残留的信息素浓度都相等，设为。用表示信息素浓度随时间的消逝，当蚂蚁完成一次路径探索后，所有路径上的信息素浓度随之改变，具体可以描述为：

其中，是第k只蚂蚁在经过路径i→j时留下的信息素，表示为：

是则表示路径i→j上增加的所有信息素的累计值，是k蚂蚁所走过路径的长度之和。种群中的蚂蚁会根据信息素浓度的多少，选择合适的路径走向终点，完成路径寻优任务。

2 算法流程

旅行商问题是经典的组合优化问题，将商人要访问的M个城市进行路径规划，使得每个城市都被访问且只访问一次 [8-9]。TSP问题中，商人可以选择的路径组合相当庞大，对于M个城市而言，可选择的路径为M！/2M，在这众多的路径当中求解出的距离最短路径，即为TSP问题的最优解，也是智能优化算法的目的所在。

本文以TSP的优化为例，描述改进的新型量子蚁群算法如下：

1） 初始化算法参数，确定待规划城市的位置信息、种群规模、最大迭代次数、信息素挥发因子、初始温度、冷却系数等。初始化信息素矩阵中每个量子位的概率幅为。

2） 统计个体已经走过的城市作为旅行禁忌，推算出个体允许旅行的城市列表。计算个体从一个城市转移到另一个城市的概率，采用轮盘赌法选择个体将要去到的下一个城市，并记录个体走过的路径与相应路径的长度。

3） 更新路径上信息素的浓度，使用量子旋转门与量子变异算子，增加群体的多样性，其中旋转角度与变异因子动态自调整，随迭代次数的增加而自适应变化。同时计算新的路径规划与路径距离，利用模拟退火的思路以一定的概率接受新路径。

4） 利用粒子群的自学习和社会学习行为，对种群寻优的结果进行深度优化，并判断新路径是否被采用，避免种群过早陷入局部最优。

5） 逐步迭代，得到TSP问题的最优解。

3 实验

考虑到对旅行商问题进行优化测试，本文采用国际通用的TSP实例库TSPLIB进行实验[10]。选取chn31作为实验数据，并将本文提出的新型改进的量子蚁群算法、传统的量子蚁群算法与蚁群算法进行对比，对每个算法分别进行30次独立实验。算法参数的设置尚无明确的理论依据，但由经验可得当时，算法的效率较好[11]。本文取信息素相对重要程度因子，启发信息相对重要程度因子，初始温度为100，冷却系数为0.99，种群规模为30，最大迭代次数为50，信息素矩阵初始化为，量子旋转角度及量子变异概率根据迭代次数自适应调整。

如上图所示，图1为实验采用的chn31问题的城市位置坐标图，共有31个城市分布图中。图2-4分别为使用蚁群算法、量子蚁群算法和本文改进的新型量子蚁群算法求得的TSP问题的规划路径。图4则为使用三种不同的智能优化算法，分别对chn31进行30次独立实验得到的平均最优路径图。可以看出，采用蚁群算法求得的路径规划图中路线直接存在明显的交叉重叠，显然不是理想路线；量子蚁群算法得到的路径规划虽无较大的路径交叉，但从得到的路径长度来看并不十分理想；而采用本文算法最终得到的路径规划中，彼此线路没有之间连接合理，最终路径距离也符合最短的要求。

传统的量子蚁群算法较蚁群算法能更加快速寻找到优化解，但很难搜索到问题的全局最优，只能停留在相对较为优秀的位置；本文提出的算法在一定程度上克服了传统量子蚁群算法的不足，能以较小的种群规模和迭代次数，快速的跳出局部收敛并寻找到较为优秀的路径规划结果。

4 结束语

智能优化算法的不断更新与发展，为复杂的组合优化等问题提供了可行的解决方案，并将逐步应用于实际生产生活的诸多领域中。本文在传统的量子蚁群算法、粒子群算法的基础上加以改进，提出了一种新型的改进算法，充分考虑到每个算法自身的优缺点以此来提高算法的总体优化求解水平，并将新的改进算法应用于TSP实验当中，实验结果表明改进算法具有一定的可用性，较传统算法而言能更加快速准确地找到规划路径。但chn31属于规模较小的旅行商问题，在今后希望能将提出的改进算法进一步应用到大规模问题的求解当中，并继续扩展到其他实际应用当中。

参考文献：

[1] Colomi A，Dorigo M and Maniezzo V.Distributed optimization by ant colonise[A].In：Proc.of 1st European Conf.Artificial Life[C].Pans，France：Elsevier，1991：134-142.

[2] Zhao H X，Huo B F，Liu R Y.Chromaticity of the complements of paths[J].J Math Study，2000，4：345-353.

[3] 张澎，王鲁达，胡丹.基于量子遗传算法的蚁群多目标优化研究[J].计算机仿真，2013，30（4）：322-325.

[4] 贾瑞玉，李亚龙.基于MapReduce的量子蚁群算法[J].计算机工程与应用，2013，49（19）：246-270.

[5] Kennedy J，Eberhart R C.Particle Swarm Optimization[C].Proceedings of IEEE International Conference on Neutral Networks，Perth，Australia，1995：1942-1948.

[6] 高鹰，谢胜利.混沌粒子群优化算法[J].计算机科学，2004，31（8）：13-15.

[7] 张广帅，张煜东，吉根林.蚁群算法求解TSP综述[J].南京师范大学学报：工程技术版，2014，14（4）：39-44.

[8] Escoffier B，Monnot J.A better differential approximation ratio for symmetric TSP[J].Theoretical Computer Science，2008，396，37（2）：83-84.

[9] 萬正宜，彭玉旭.求解旅行商问题的改进型量子蚁群算法[J].计算机工程与应用，2016，52（22）：59-63，122.

[10] Dong F M，Koh K M，Teo K L.Chromatic polynomials and chromaticity of graphs[M].[S.l.]：World Scientific Publishing Co Pte Ltd，2005.

[11] 张记会，高齐圣，徐心和.自适应蚁群算法[J].控制理论与应用，2000，17（1）：1-3.endprint