求解TSP的离散野马优化算法

doi:10.3778/j.issn.1002-8331.2303-0012

摘要/Abstract

摘要： 针对求解TSP问题，提出一种新的元启发式算法离散野马优化算法（DWHO），应用最小位置匹配值法（MPMV）对求解结果进行离散化解码；为提高算法搜索能力，结合野马放牧、交配、领导者交流与选拔行为，引入变邻域搜索策略，增强了算法的局部搜索能力、加快算法收敛速度。选取TSPLIB标准库33个算例进行实验，并与交换序列人工蜂群算法（ABCSS）、离散蜘蛛猴优化算法（DSMO）两种算法进行比较。实验结果表明，DWHO求得的最优解与ABCSS、DSMO两种算法的最优解相比，最优解改进率最大值分别达到4.52%和3.41%。同时，将离散野马优化算法求解TSP收敛速度与以上两种算法进行比较，其收敛速度具有一定的优势。结果表明离散野马优化算法求解能力和精度具有优势。

关键词: 离散野马优化算法, 旅行商问题, 最小位置匹配值法, 最优解改进率

Abstract: A new metaheuristic algorithm called discrete wild horse optimizer (DWHO) is proposed for solving the traveling salesman problem. The minimum position matching value method (MPMV) is applied to discretize and decode the obtained solutions. To improve the algorithm’s search capability, a variable neighborhood search strategy is introduced to enhance its local search capability and accelerate the convergence speed by combining wild horse grazing behavior, mating behavior, exchange and?selection of?leaders. 33 benchmark examples from the standard library TSPLIB are selected for experimentation, and it is compared with two other algorithms, artificial bee colony algorithm with sequence exchange (ABCSS) , discrete spider monkey optimization (DSMO) . The experimental results indicate that the maximum improvement rates of the optimal solutions of DWHO, compared with ABCSS, and DSMO algorithms, are 4.52% and 3.41%, respectively. Moreover, the convergence speed of the discrete horse optimizer in solving TSP is significantly better than the above two algorithms. The results also indicate that the discrete horse optimizer has advantages in terms of solving ability and accuracy.

Key words: discrete wild horse optimizer (DWHO), traveling salesman problem (TSP), min-position matched value (MPMV), best solution improvement rate

蔡延光, 方春城, 吴艳林, 陈华君. 求解TSP的离散野马优化算法[J]. 计算机工程与应用, 2024, 60(1): 145-153.

CAI Yanguang, FANG Chuncheng, WU Yanlin, CHEN Huajun. Discrete Wild Horse Optimizer for TSP[J]. Computer Engineering and Applications, 2024, 60(1): 145-153.

参考文献

[1] SHI X H, LIANG Y C, LEE H P, et al. Particle swarm optimization based algorithms for TSP and generalized TSP[J]. Information Processing Letters, 2007, 103(5): 169-176.
[2] 林敏, 钟一文, 刘必雄, 等. 基因-表现型的布谷鸟算法求解旅行商问题[J]. 计算机工程与应用, 2017, 53(24): 172-181.
LIN M, ZHONG Y W, LIU B X, et al. Genotype-phenotype cuckoo search algorithm for traveling salesman problem[J]. Computer Engineering and Applications, 2017, 53(24): 172-181.
[3] 孙鉴, 刘凇佐, 武晓晓. 基于大规模邻域搜索的模拟退火算法求解TSP[J]. 计算机仿真, 2023, 40(6): 415-420.
SUN J, LIU S Z, WU X X. Simulated annealing algorithm based on large neighborhood search to solve TSP[J]. Computer Simulation, 2023, 40(6): 415-420.
[4] YU M. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization[J]. Discrete & Continuous Dynamical Systems-S, 2019, 12: 979-987.
[5] PANWAR K, DEEP K. Discrete grey wolf optimizer for symmetric travelling salesman problem[J]. Applied Soft Computing, 2021, 105(11): 107298.
[6] WU C, FU X, PEI J, et al. A novel sparrow search algorithm for the traveling salesman problem[J]. IEEE Access, 2021, 9: 153456-153471.
[7] DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem[J]. Biosystems, 1997, 43(2): 73-81.
[8] CINAR A C, KORKMAZ S, KIRAN M S. A discrete tree-seed algorithm for solving symmetric traveling salesman problem[J]. Engineering Science and Technology, 2020, 23(4): 879-890.
[9] AKHAND M A H, AYON S I, SHAHRIYAR S A, et al. Discrete spider monkey optimization for travelling salesman problem[J]. Applied Soft Computing, 2020, 86: 105887.
[10] AKHAND M A H, AKTER S, RASHID M A, et al. Velocity tentative PSO: an optimal velocity implementation based particle swarm optimization to solve traveling salesman problem[J]. IAENG International Journal of Computer Science, 2015, 42(3): 221-232.
[11] DU P, LIU N, ZHANG H, et al. An improved ant colony optimization based on an adaptive heuristic factor for the traveling salesman problem[J]. Journal of Advanced Transportation, 2021: 1-16.
[12] KHAN I, MAITI M K. A swap sequence based artificial bee colony algorithm for traveling salesman problem[J]. Swarm and Evolutionary Computation, 2019, 44: 428-438.
[13] HUANG Y, SHEN X N, YOU X. A discrete shuffled frog-leaping algorithm based on heuristic information for traveling salesman problem[J]. Applied Soft Computing, 2021, 102(2): 107085.
[14] NARUEI I, KEYNIA F. Wild horse optimizer: a new meta-heuristic algorithm for solving engineering optimization problems[J]. Engineering with Computers, ?2021: 1-32.
[15] ENVELOPE M, ENVELOPE S, ENVELOPE M, et al. An improved wild horse optimization algorithm for reliability based optimal DG planning of radial distribution networks[J]. Energy Reports, 2022, 8: 582-604.
[16] ALI M, KOTB H, KAREEM ABORAS M, et al. Frequency regulation of hybrid multi-area power system using wild horse optimizer based new combined fuzzy fractional-order pi and tid controllers[J]. Alexandria Engineering Journal, 2022, 61(12): 12187-12210.
[17] VASANTHKUMAR P, SENTHILKUMAR N, RAO K S, et al. Improving energy consumption prediction for residential buildings using modified wild horse optimization with deep learning model[J]. Chemosphere, 2022, 308: 136277.
[18] 戚远航, 蔡延光, 蔡颢, 等. 旅行商问题的混沌混合离散蝙蝠算法[J]. 电子学报, 2016, 44(10): 2543-2547.
QI Y H, CAI Y G, CAI H, et al. Chaotic hybrid discrete bat algorithm for traveling salesman problem[J]. Acta Electronica Sinica, 2016, 44(10): 2543-2547.
[19] MILLER C E, TUCKER A W, ZEMLIN R A. Integer programming formulation of traveling salesman problems[J]. Journal of the ACM, 1960, 7(4): 326-329.
[20] ALI I M, ESSAM D, KASMARIK K. A novel differential evolution mapping technique for generic combinatorial optimization problems[J]. Applied Soft Computing, 2019, 80: 297-309.
[21] LI X, YIN M. A hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problem[J]. International Journal of Production Research, 2013, 51(16): 4732-4754.
[22] AI T J, KACHITVICHYANUKUL V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem[J]. Computers & Industrial Engineering, 2009, 56(1): 380-387.
[23] PRINS C. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research, 2004, 31(12): 1985-2002.