A novel memetic algorithm with random multi-local-search: A case study of TSP

Peng ZOU, Zhi ZHOU, Guoliang CHEN, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

9 Citations (Scopus)

Abstract

Memetic algorithms (MAs) have been shown to be very effective in finding near optimal solutions to hard combinatorial optimization problems. In this paper, we propose a novel memetic algorithm (MsMA), in which a new local search scheme is introduced. We called this local search scheme as random Multi-Local-Search (MLS). The MLS is composed of several local search schemes, each of which executes with a predefined probability to increase the diversity of the population. The combination of MsMA with the crossover operator edge assembly crossover (EAX) on the classic combinatorial optimization problem Traveling Salesman Problem(TSP) is studied, and comparisons are also made with some best known MAs. We have found that it is significantly outperforming the known MAs on almost all of the selected instances. Furthermore, we have proposed a new crossover named M-EAX, which has more powerful local search ability than the EAX. The experimental results show that the MsMA with M-EAX has given a further improvement to the existing EAX.
Original languageEnglish
Title of host publicationProceedings of the 2004 Congress on Evolutionary Computation, CEC2004
Pages2335-2340
Number of pages6
Volume2
Publication statusPublished - 2004
Externally publishedYes

Fingerprint

Dive into the research topics of 'A novel memetic algorithm with random multi-local-search: A case study of TSP'. Together they form a unique fingerprint.

Cite this