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

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.