一种利用混合优化算子求解旅行商问题的方法

贾玉福 陶懿 丰霄

摘 要：利用遺传算法、社会群体优化算法和模拟退火算法等仿生类整体探索算法求解旅行商问题（TSP），往往需要局部优化算子促进算法收敛。目前大多采用单一的n-opt算子而没有考虑利用其它算子或算子组合对旅行商路线进行优化。为此定义了P_Swap、FP_Swap和L_Swap等3个算子，在TSPLIB 数据集中选取18个实例，分别利用各个算子及组合对旅行商路线问题进行优化。对比分析结果显示，P_Swap算子的优化能力与2-opt算子相当，3个算子组合的优化能力明显强于2-opt算子，组合优化算法求得的最优解优于目前已知的大部分算法。

关键词：旅行商问题;n-opt 算子;组合优化;全局探索能力;随机扰动

DOI：10. 11907/rjdk. 182712

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）003-0062-03

0 引言

旅行商问题（TSP）是一个典型的NP-Hard 难题，精确求解大规模城市节点算法效率低下，取而代之的是一些启发式和仿生类探索性算法，比如社会群体优化算法（SGO） [1-2]、细菌觅食优化算法[3-4]、遗传算法[5-6]、蚁群算法[7]和模拟退火算法[8]等。这些算法虽然具有较好的全局探索能力，但往往需要局部优化算子促进算法收敛[9-11]。相关研究有：张子成[12]、韩伟等[13]在利用改进的模拟退火自适应离散型布谷鸟算法和离散型贝壳漫步优化算法求解TSP时采用2-opt 算子作局部优化;姚丽莎等[14]将局部搜索算法与遗传算法相结合求解异构多核系统的任务调度问题，利用3-opt对部分个体优化变异;宁桂英等[15]利用离散型差分进化算法求解TSP，王勇臻[16]、宋尧[17]等利用细菌觅食算法求解TSP，陈立云等[18]利用遗传算法求解运输车调度问题，都采用2-opt 算子作局部优化。上述方法均采用单一的n-opt交叉算子而没有考虑其它算子及组合对TSP求解的有效性。为此，本文定义3个优化算子，提出利用混合优化算子策略进行TSP求解，从而比较 2-opt与各个算子的有效性，以及算法整体得到的TSP最优解与其它算法的差距。

1 优化算子与算法描述

本文算法的基本思想是先依据所有节点坐标进行Delauney三角划分，随机选择一个三角形的3个顶点A、B、C形成环路，再以该三角形为种子向外扩张，形成一个包含所有节点的闭合环路。最后对该环路利用各种优化算子和算子组合进行环路调整得到最优解。

1.1 定义优化算子

在对比不同算子的有效性时，算法可以对步骤③、步骤④、步骤⑤和步骤⑥进行取舍。

2 实验结果

本文用国际标准的 TSPLIB 数据集[19]中18个实例进行仿真实验，采用以所有三角形作为种子得到的最优解进行比较。从表1可知，P_Swap有8个实例的优化效果好于2-opt，1个实例优化效果相同，9个实例的优化效果比2-opt差。3算子组合的效果有13个实例优于2-opt算子。从单个算子来看，FP_Swap比L_Swap好，比P_Swap差，这主要是因为FP_Swap算子只考虑局部连续4点的合理性，没有考虑全局优化的可能。

为将本文提出的混合算子策略算法与仿生类算法最优解进行比较，选取最近文献发表的部分实例结果作为评价标准。表2列出了文献[20]中提到的几个经典算法的最优解，表3列出了文献[21]中提到的几个经典算法的最优解。通过比较可知，本文算法的最优解优于大部分仿生算法，部分实例接近于文献[21]提出的DWPA算法结果。

3 结语

本文提出利用自定义的3个优化算子求解TSP的混合策略，通过对TSPLIB 数据集中的实例测试发现：P_Swap算子的优化能力与2-opt算子相当，3个算子组合的优化能力明显强于2-opt算子。算子组合优化算法求得的最优解优于目前已知的大部分算法。下一步研究工作是考虑将算子组合与仿生算法结合求解TSP。

参考文献：

[1] SATAPATHY S，NAIK A. Social group optimization（SGO）： a new population evolutionary optimization technique[J]. Complex &Intelligent Systems， 2016（3）：1-31.

[2] NAIK A，SATAPATHY S C，ASHOUR A S，et al. Social group optimization for global optimization of multimodal functions and data clustering problems[J]. Neural Computing & Applications，2016（5）：1-17.

[3] PASSINO K M. Biomimicry of bacteria foraging for distributed optimization and control[J]. IEEE Control Systems Magazine， 2002，22（3）：52-67.

[4] LIU Y，PASSINO K NM. Biomimicry of social foraging bacteria for distributed optimization： models， principles， and emergent behaviors[J]. Journal Optimization Theory Application，2002，115（3）：603-628.

[5] NGUYEN，HUNG DINH. Implementation of an effective hybrid GA for large-scale traveling salesman problems[J]. IEEE transactions on systems， man， and cybernetics，2007，37（1）：92-99.

[6] MARIBEL GUERRERO，OSCAR CASTILLO，MARIO GARCíA VALDEZ. Cuckoo search via lévy flights and a comparison with genetic algorithms[J]. Fuzzy Logic Augmentation of Nature-Inspired Optimization Metaheuristics， 2015（3）：91-103.

[7] DORIGO M， GAMBARDELLA L M. A study of some properties of ant-q[C]. Lecture Notes in Computer Science，1996（1141）：656-665.

[8] KIRKPATRICK S，GELATT JR CD，VECCHI M P. Optimization by simulated annealing[J]. Science，1983，220（4598）：671-680.

[9] 陳彧，韩超. 一种求解旅行商问题的进化多目标优化方法[J]. 控制与决策，2017（12）：248-254.

[10] 刘亚军，陈得宝，邹锋，等. 离散社会群体优化算法求解旅行商问题[J]. 长春师范大学学报，2018，37（6）： 91 - 95.

[11] CHIANG C W，LEE W P，HEH J S. A 2-opt based differential evolution for global optimization[J]. Applied Soft Computing，2010，10（4）：1200 - 1207.

[12] 张子成，韩伟，毛波，等. 基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题[J]. 电子学报，2018，46（8）：1849-1857.

[13] 韩伟，张子成. 求解旅行商问题的离散型贝壳漫步优化算法[J]. 模式识别与人工智能， 2016，29（7）： 650-657.

[14] 姚丽莎，王占凤，程家兴. 分层混合局部搜索策略异构多核系统调度[J]. 运筹与管理， 2016，29（7）： 193-199.

[15] 宁桂英，曹敦虔，周永权. 求解TSP问题的离散型差分进化算法[J]. 计算机与数字工程，2017，45（11）：2136-2142.

[16] 王勇臻，陈燕，李桃迎. 离散型细菌觅食算法求解 TSP[J]. 计算机应用研究，2014，31（12）： 3642 - 3650.

[17] 宋尧，叶桦，仰燕兰. 改进细菌觅食算法在 TSP 问题中的应用[J]. 工业控制计算机，2018，31（8）：86-87.

[18] 陈立云，卢昱，晏杰，等. 基于改进遗传算法的弹药运输车辆调度问题研究[J]. 装备学院学报，2014，25（2）：106-111.

[19] DOC IN. Symmetric TSPs[EB/OL]. [2018-03-13]. http：//www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/STSP.html.

[20] 王艳，王秋萍，王晓峰. 基于改进萤火虫算法求解旅行商问题[J]. 计算机系统应用，2018，27（8）：219-225.

[21] 黄海松，任竹鹏，魏建安. 改进狼群算法求解旅行商问题[J].计算机应用研究，2018，36（12）：1245-1249.

（责任编辑：杜能钢）