改进混合蚁群算法求解关联旅行商问题

朱 君，蔡延光，汤雅连

（广东工业大学 自动化学院，广东 广州 510006）

旅行商问题 TSP[1-2]（Traveling Salesman Problem）是运筹学领域中的经典优化组合问题，并且属于NP-Hard（NPH）问题，其计算复杂性随输入规模呈指数函数增长，其实际模型在连锁店的货物配送、电子地图、印刷电路板的钻孔路线方案、超大规模集成电路单元布局、网格布线、管道铺设等优化问题中有着广泛的应用。游客在访问城市时，会有各种约束，关联约束就是其中一种，由于两个或多个城市依次举行展会、博览会、艺术节、广交会及马拉松比赛等，这些演艺类、体育类、文化类及商业类的大型活动往往吸引着广大游客，游客会尽可能地参观或者参加节事旅游，比如3个旅游城市A、B和C依次举办大型活动，那么游客访问的次序应该是A→B→C，这就是关联旅行商问题ITSP（Incident Traveling Salesman Problem），由于该问题模型在现实生活中普遍存在，因而具有研究意义。

目前已经有很多求解TSP的算法。SILBERHOLZ J等人[3]研究了多彩TSP（Colourful Travelling Salesman Problem，CTSP），提出了两种新的启发式算法对其求解，并证明了所提出方法的有效性。ROY S[4]应用带单点交叉算子的遗传算法求解TSP，实验证明能搜索到最优解。MAVROVOUNIOTIS M[5]等人针对带交通因素的动态TSP，应用移民策略的蚁群优化算法ACO（Aat Colony Optimization）求解，实验证明提出的算法优于传统的ACO。SINGH H等人[6]应用遗传算法求解多旅行商问题 MTSP（Multiple Traveling Salesman Problem）。柳寅等人[7]基于模糊化处理和蜂群寻优的特点，提出一种模糊人工蜂群算法，通过对旅行商问题的仿真证明了该算法有良好的鲁棒性和有效性。王刚等人[8]应用多项式时间近似方案PTAS（PolynomialTimeApproxination Scheme）研究曲面上的TSP，一般性的深刻结论还有待研究。刘勇等人[9]研究了以总路程和总收益之比为目标函数的最小比率旅行商问题MRTSP（Minimum Ratio Traveling Salesman Problem），应 用基于万有引力定律和牛顿第二定律的引力搜索算法GSA（Gravitational Search Algorithm）寻优，实验结果证明该算法能有效解决最小比率旅行商问题。饶卫振等人[10]应用添加边所在位置信息的改进贪婪算法IMGRA（Improved Greedy Algorithm）求解欧几里得旅行商问题ETSP（Euclidean Travelling Salesman Problem），结果表明IMGRA优于贪婪算法 GRA（Greedy Algorithm）。蔡荣英等人[11]针对传统ACO的不足，提出了迭代改进蚁群优化算法，并用此算法求解TSP，仿真结果表明该算法能在更少迭代次数内获得更好解。柯良军等人[12]应用精确算法和蚁群算法求解不确定旅行商问题的鲁棒模型，结果证明提出的蚁群算法能在短时间内求得最优或近优解，且鲁棒解是有效的。王颖等人[13]提出一种克服局部最小点的自适应蚁群算法，在保证收敛速度的条件下提高解的全局性，仿真证明在收敛速度和解的性能方面优于传统蚁群算法。吴斌等人[14]在蚁群算法的基础上提出了相遇算法并将相遇算法与分段算法相结合，求解TSP，实验证明了算法的有效性。叶志伟等人[15]研究了蚁群算法中的参数α、β、ρ，并对最优的参数配置问题作了分析，同时求解TSP，证明有较好的实用价值。孙力娟等人[16]应用遗传算法 GA（Genetic Algorithm）对 ACO的参数α、β、ρ进行优化，对 TSP的求解表明算法的优化质量和效率优于传统蚁群算法和遗传算法。段海滨等人[17]应用改进的ACO求解对Bayes 29TSP问题，实验结果表明该算法具有很好的全局收敛性能。本文重点是引入混沌搜索和平滑机制，结合GA和ACO的优点，应用改进的混合蚁群算法对ITRP求解。

1 ITSP问题模型

假设一个游客要去 i（i=1，2，…，l）个城市，这些城市两两之间均可到达，且可以用距离来量化，其中有h个城市具有关联性，游客必须规划所要走的路径，h个城市必须按时间先后依次访问，每个城市只能拜访一次，最后要回到原来出发的城市，目的是路径总里程最小。

建立数学模型：式（1）为目标函数，即总路程最短；式（2）为约束条件，对于每个地方，都必须经过1次，对于任何n-2个节点，不能有回路，存在关联约束，根据时间的先后依次访问有关联约束的城市，关联城市个数小于总城市个数。

2 改进混合蚁群算法

2.1 混沌搜索

混沌搜索具有随机性、遍历性和确定性，由混沌搜索产生初始种群，克服了生成大量非可行解的缺陷，加速染色体向最优解收敛。文中选用Logistic映射[18]，如式（3）所示。i表示混沌变量的序号，i=1，2，…，r；u 表示种群序号，u=0，1， …，n；βi表示混沌变量，0≤βi≤1； μi表 示 吸 引 子 。 当 μi=4时 ，Logistic映射完全处于混沌的状态，此时的混沌变量βi具有很好的遍历性。

2.2 平滑机制

平滑机制可用于提高蚁群算法的性能的思想是通过增加选择有低强度信息素解元素的概率以提高探索新解的能力。如式（4）所示，0＜δ＜1，τij（t）和 τij*（t）分别为平滑化之前和之后的信息素轨迹量。其优点是对于δ＜1，在算法运行过程中所积累的信息不会完全被丢失，而仅仅是被削弱；δ=1时，相当于信息素轨迹的重新初始化；δ=0，则该机制被关闭。

2.3 基本蚁群算法系统模型

设 m 为蚂 蚁数量，dij（i，j=1，2，…，n）表示 i与 j之间的距离，τij（t）表示 t时刻在 ij连线上残留的信息素强度。 初始时刻，各路径上信息量相等，设 τij（0）=C（C 为常数）。 蚂蚁 k（k=1，2，…，m）在运动过程中，根据各条路径上信息量决定转移方向，Pijk表示t时刻蚂蚁k由位置i转移到 j的概率，如式（5）所示。

其中，allowedk为蚂蚁 k下一步可选择的城市；ηijβ为能见度因数，常取 ηij（t）=1/dij；α 和 β 分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性，α为信息启发式因子，β为期望启发式因子。

过多残留信息素会引起残留信息素覆盖启发信息，所以在每只蚂蚁走完一步或者完成对所有城市的遍历之后，要对残留信息进行更新处理。t+n时刻在路径（i，j）上的信息量可先按式（6）和（7）作调整。

其中，ρ为信息素挥发因子，ρ∈（0，1）；△τij（t）表示本次循环中信息素增量；△τijk（t）表示第 k只蚂蚁在本次循环中留下的信息素，计算方法可以根据计算模型而定。

本文采用蚁周模型，如式（8）所示。

其中，Q表示信息素强度，会影响算法的收敛速度，过大会导致局部收敛，过小会影响收敛速度；dij表示在本次循环中所走路径的长度。

2.4 构造状态转移规则

采用将确定性选择组合和随机性选择相结合的策略，适当加大随机选择概率，对解空间进行更完全的搜索，从而克服传统蚁群算法缺陷。按照式（9）确定蚂蚁由转移到的状态转移概率。

其中，q 是[0，1]内的随机数，是一个参数；q0∈[0，1]，一般取 0.85～0.90。

蚂蚁在选择下一客户时，根据先验知识，如式（9）所示来选择最好的边，否则按式（5）来选择一条边，将求得的各个节点的转移概率进行累加，再与产生的随机数相比较，直到满足要求，蚂蚁可转移到下一节点。

2.5 信息素更新

（1）保留最优解。在每次循环结束后，保留最优解。

（2）自适应改变ρ。通过减小ρ虽然可以提高算法的全局搜索能力，但也会使收敛速度降低，因此需要自适应改变 ρ。ρ的初始值 ρ（t0）=1；当算法求得最优值在此循环中无明显改进时，ρ如式（10）所示。

其中，ρmin可以防止ρ因过小而降低算法收敛速度。

2.6 改进混合蚁群算法求解流程

（1）混沌搜索，产生初始种群，设计遗传算法参数。

（2）进行选择、交叉和变异操作。

（3）满足条件则生成优化解，不满足则返回步骤（1）。

（4）根据优化解生成信息素初始分布，设计蚁群算法参数。

（5）蚂蚁根据转移概率选择下一节点。

（6）遍历所有点，最优蚂蚁圈进行信息素增加。

（7）更新信息素，引入平滑机制，根据式（11）进行平滑化。

（8）若满足终止条件，达到最大迭代次数，则结束；否则，返回步骤（5）。

3 仿真实验

改进混合蚁群算法中参数设计，蚁群规模m=20，最大迭代次数 Nc=200，α=1，β=1，ρ（t0）=0.15，q0=0.88，Q=100；遗传算法部分参数设计，初始化种群N=20，最大迭代次数 gen=50，交叉概率 pc=0.9，变异概率 pm=0.04，采用轮盘赌选择，路径编码，均匀杂交，单点变异。关联约束：t32＜t23＜t2＜t1＜t18，t38＜t11＜t39＜t40。 本 文中 的实 验及算例是在Intel（R）CoreTMi3 CPU 2.53 GHz、内存为 2.0 GB、安装系统为Win7的PC上采用MATLAB R2010b编程实现。城市信息如表1所示。应用 PSAGA、ACO、GA、禁忌搜索 TS（Tabu Serch）和改进的混合蚁群优化算法IHACO（Improving Hybird Ant Colony Optimization）对 TSP 和ITSP问题模型分别求解20次，然后应用IHACO和ACO求解TSPlib中的 3个算例，eil76（76个城市）、eil101（101个城市）和 pr136（136个城市），运行程序20次。首先将具有关联约束的城市连接起来，如图1所示，然后应用算法求解。

表1 50个城市坐标信息

图1 关联约束图示

图2 IHACO求解TSP的最佳旅游路线最优旅游路线（ITSP）

图3 IHACO求解TSP的一次收敛过程

图4 IHACO求解ITSP的最佳旅游路线

图5 IHACO求解ITSP的一次收敛过程

结果比较如表2所示，在求解TSP时，基于遗传算法的粒子群算法 PSOGA（Particle Swarm Algorithm based on Genetic Algorithm）和IACO能搜索到较好解，TSP最优路径长度为：516.687 4 km。IHACO求解TSP的最佳旅游路线及IHACO求解TSP的一次收敛过程如图2和图3所示。在求解ITSP时，ACO和IHACO能搜索到较好解，ITSP最优路径长度为：520.191 2 km。IHACO求解ITSP的最佳旅游路线及IHACO求解ITSP的一次收敛过程如图4和图5所示。进一步验证ACO和IHACO的性能，对TSPlib中的3个算例仿真的结果如表3所示，与ACO相比，IHACO的运行时间更短，偏差也较小，说明IHACO优化能力更强，求解更优。

本文引出了关联旅行商问题并对其分析，建立了数模型；采用混沌搜索产生初始种群克服了生成大量非可行解的缺陷，加速染色体向最优解收敛；引入平滑机制，该机制通过增加选择有低强度信息素解元素的概率以提高蚁群算法探索新解的能力。蚁群算法搜索初期信息素累积时间长，求解效率低，结合遗传算法具有快速全局搜索能力，构成改进混合蚁群算法，算例证明该算法能搜索到较好解，并且提高了计算效率。

表2 GA-PSO、ACO、GA、TS和 IACO求解TSP和 ITSP的结果比较

表3 ACO和IHACO求解TSPlib中3个算例的结果

[1]赵秋红，肖依永，MLADENOVIC N.基于单点搜索的元启发式算法[M].北京：科学出版社，2013.

[2]李明.详解MATLAB在最优化计算中的应用[M].北京：电子工业出版社，2011.

[3]SILBERHOLZ J， RAICONI A， CERULLI R， et al.Comparison of heuristics for the colourful travelling salesman problem[J].International Journal of Metaheuristics， 2013， 2（2）： 141-173.

[4]ROY S.Genetic algorithm based approach to solve travelling salesman problem with one pointcrossoveroperator[J].INTERNATIONAL JOURNAL OF COMPUTERS&TECHNOLOGY， 2013， 10（3）：1393-1400.

[5]MAVROVOUNIOTIS M，YANG S.Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors[J].Applied Soft Computing，2013，13（10）：4023-4037.

[6]SINGH H，KAUR R.Resolving multiple travelling salesman problem using genetic algorithms[J].International Journal of Computer Science Engineering and Information Technology Research， 2013，3（2）：209-212.

[7]柳寅，马良.模糊人工蜂群算法的旅行商问题求解[J].计算机应用研究，2013，30（9）：2694-2696.

[8]王刚，骆志刚.曲面上旅行商问题的多项式时间近似方案[J].计算机研究与发展，2013，50（3）：657-665.

[9]刘勇，马良.最小比率旅行商问题的引力搜索算法求解[J].小型微型计算机系统，2013，4（34）：847-849.

[10]饶卫振，金淳，陆林涛.考虑边位置信息的求解 ETSP问题改进贪婪算法[J].计算机学报，2013，36（4）：836-850.

[11]蔡荣英，王李进，吴超，等.一种求解旅行商问题的迭代改进蚁群优化算法[J].山东大学学报（工学版），2012，42（1）：6-11.

[12]柯良军，尚可，冯祖仁.不确定旅行商问题的鲁棒模型及 其 算 法 研 究 [J].计 算 机 科 学 ，2012，39（B06）：238-241.

[13]王颖，谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报，2002，14（1）：31-33.

[14]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报，2001，24（12）：1328-1333.

[15]叶志伟，郑肇葆.蚁群算法中参数 α，β，ρ设置的研究——以TSP问题为例[J].武汉大学学报（信息科学版），2004，29（7）：597-601.

[16]孙力娟，王良俊，王汝传.改进的蚁群算法及其在TSP中的应用研究[J].通信学报，2004，25（10）：111-116.

[17]段海滨，王道波.蚁群算法的全局收敛性研究及改进[J].系统工程与电子技术，2004，26（10）：1506-1509.

[18]汤雅连，蔡延光，郭帅，等.单车场关联物流运输调度问题的混沌遗传算法[J].广东工业大学学报，2013（30）：53-57.