A Niching Memetic Algorithm for Multi-Solution Traveling Salesman Problem

Ting HUANG, Yue-Jiao GONG, Sam KWONG, Hua WANG, Jun ZHANG

Research output: Journal PublicationsJournal Article (refereed)peer-review

60 Citations (Scopus)

Abstract

Multi-solution problems extensively exist in practice. Particularly, the traveling salesman problem (TSP) may possess multiple shortest tours, from which travelers can choose one according to their specific requirements. However, very few efforts have been devoted to the multi-solution problems in the discrete domain. In order to fill this research gap and to effectively tackle the multi-solution TSP, we propose a niching memetic algorithm in this article. The proposed algorithm is characterized by a niche preservation technique to enable the parallel search of multiple optimal solutions; an adaptive neighborhood strategy to balance the exploration and exploitation; a critical edge-aware method to provide effective guidance to the reproduction; and a selective local search strategy to improve the search efficiency. To evaluate the performance of the proposed algorithm, we conduct comprehensive experiments on a recently published multi-solution optimization test suite. The experimental results show that our algorithm outperforms other compared algorithms. Furthermore, the proposed algorithm is adopted to tackle problems from the well-known TSPLIB library to obtain a set of distinct but good solutions.
Original languageEnglish
Pages (from-to)508-522
JournalIEEE Transactions on Evolutionary Computation
Volume24
Issue number3
Early online date20 Aug 2019
DOIs
Publication statusPublished - Jun 2020
Externally publishedYes

Bibliographical note

This work was supported in part by the National Natural Science Foundation of China under Grant 61873095, Grant 61873097, and Grant U1701267, in part by the Guangzhou Science and Technology Planning Project under Grant 201904010211, in part by the Guangdong Natural Science Foundation Research Team Project under Grant 2018B030312003, and in part by the Guangdong-Hong Kong Joint Innovation Platform Project under Grant 2018B050502006.

Keywords

  • Memetic algorithm
  • multi-solution traveling salesman problem (MSTSP)
  • multimodal optimization (MMOP)
  • neighborhood niching strategy

Fingerprint

Dive into the research topics of 'A Niching Memetic Algorithm for Multi-Solution Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this