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

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