Title :
A novel memetic algorithm with random multi-local-search: a case study of TSP
Author :
Zou, Peng ; Zhou, Zhi ; Chen, Guoliang ; Yao, Xin
Author_Institution :
Nat. High Performance Comput. Center, Hefei, China
Abstract :
Memetic algorithms (MAs) have been shown to be very effective in finding near optimal solutions to hard combinatorial optimization problems. 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.
Keywords :
genetic algorithms; probability; search problems; travelling salesman problems; M-EAX; MsMA; TSP; combinatorial optimization problem; combinatorial optimization problems; crossover operator edge assembly crossover; memetic algorithm; random multilocal-search; traveling salesman problem; Assembly; Cities and towns; Computer aided software engineering; Computer applications; Genetic algorithms; High performance computing; Laboratories; Multilevel systems; Tellurium; Traveling salesman problems;
Conference_Titel :
Evolutionary Computation, 2004. CEC2004. Congress on
Print_ISBN :
0-7803-8515-2
DOI :
10.1109/CEC.2004.1331189