A Niching Regression Adaptive Memetic Algorithm for Multimodal Optimization of the Euclidean Traveling Salesman Problem
Shi-Jie Jian, Sun‐Yuan Hsieh
Abstract
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.