A Niching Regression Adaptive Memetic Algorithm for Multimodal Optimization of the Euclidean Traveling Salesman Problem
针对欧几里得旅行商问题的多模态优化，提出一种结合生态位策略和回归初始化、自适应参数控制的模因算法，在大规模案例上优于现有方法。
The traveling salesman problem (TSP) has been studied for many years. In particular, the multimodal optimization of the TSP is important for practical applications, because decision-makers can select the best candidate based on current conditions and requirements. In the Euclidean TSP, there are <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> points in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {R}^{d}$ </tex-math></inline-formula> space with Euclidean distance between any two points, that is, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d(x, y) =||x-y||_{2}$ </tex-math></inline-formula> . The goal is to find a tour of minimum length visiting each point. In this article, we only focus on the case that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d=2$ </tex-math></inline-formula> . Recently, in order to efficiently handle the multimodal optimization of the TSP, some methods have been developed to deal with it. Nevertheless, these methods usually perform poorly for large-scale cases. In this article, we propose a niching regression adaptive memetic algorithm (MA) to handle the multimodal optimization of the Euclidean TSP. We use the MA as the baseline algorithm and incorporate the neighborhood strategy to maintain the population diversity. In addition, we design a novel regression partition initialization and adaptive parameter control to enhance our algorithm, and propose the concept of the redundant individual to improve the search efficiency. To validate the performance of the proposed algorithm, we comprehensively conduct experiments on the multimodal optimization of TSP benchmark and the well-known TSPLIB library. The experimental results reveal that the proposed method outperforms other methods, especially for large-scale cases.