A Tabu Search Algorithm Based on Symmetry Local Search for Multi-objective Combinatorial Optimization Problems
Tianyang Li, Ying Meng, Lixin Tang, Qingxin Guo · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
In this paper, we propose a Tabu search algorithm based on symmetry local search (TS-SLS) that can be regarded as a search component for multi-objective evolutionary algorithms (MOEAs) to solve multi-objective traveling salesman problems (MOTSPs). In TS-SLS, the symmetry local search is designed by the symmetry feature of solution space in MOTSPs. We discuss and analyze the relation between the solution space and several common search operators and in turn obtain an interesting conclusion. In addition, considering the importance of diversity preservation in MOEAs, TS-SLS adopts the Tabu search (TS) as the main search mechanism to preserve diversity in MOTSPs. For experiments, we take 15 MOTSP benchmark instances and three classical and representative MOEAs as reference algorithms to assess the performance of TS-SLS. Experimental results show that the MOEAs embedded with TS-SLS can achieve competitive performances in terms of convergence and diversity.