Memetic framework with adaptive meme pool for the travelling salesman problem

• Main Author: Zeng, Yuntao
• Other Authors: Meng-Hiot Lim
• Format: Thesis-Master by Coursework
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/164088
• Institution: Nanyang Technological University

The Travelling Salesman Problem (TSP) is a well-known combinatorial optimization problem. As the number of cities increases, traditional algorithms become less effective in finding the optimal solution in the vast search space of TSP, and it is also difficult to achieve good sub-optimal solutions. The design of a performance-efficient approximate solution algorithm has been the focus of many researchers. Memetic Algorithms (MAs) is a class of evolutionary algorithms for such complex optimization problems, using a global search to locate a good region and a local search, otherwise known as meme to locate the optimal solution. The key to memetic algorithms is the incorporation of one or more memes in the search algorithm. This work focuses on COPs and investigates the use of a memetic framework for solving the classical combinatorial optimization problem TSP. With the solution landscape unknown, it is likely that the over reliance of a single meme may not deliver good performance, as with the case of classical memetic algorithm. We explore a Memetic Framework with Adaptive Meme Pool (MF-AMP), consisting of k-opt operators, the swap operator, and the Tabu Algorithm adaptive local search operators. The set of operators mentioned above is combined with GA in order to derive a time-efficient search algorithm. The performance measurement and algorithm validation are conducted by performing experiments on instances of varying complexity in the benchmark dataset TSPLIB. The corresponding experiment results are given for analysis and discussion. Our approach is compared with other algorithms proposed in recent years according to the results, which demonstrate the effectiveness and superiority of search algorithm enhanced with adaptive memes within in the meme pool.