Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/164088
Title: Memetic framework with adaptive meme pool for the travelling salesman problem
Authors: Zeng, Yuntao
Keywords: Engineering::Electrical and electronic engineering
Issue Date: 2022
Publisher: Nanyang Technological University
Source: Zeng, Y. (2022). Memetic framework with adaptive meme pool for the travelling salesman problem. Master's thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/164088
Abstract: 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.
URI: https://hdl.handle.net/10356/164088
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:EEE Theses

Files in This Item:
File Description SizeFormat 
Dissertation-ZengYuntao-Final.pdf
  Restricted Access
3.43 MBAdobe PDFView/Open

Page view(s)

23
Updated on Feb 4, 2023

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.