Runtime analysis to compare best-improvement and first-improvement in memetic algorithms

In recent years, the advantage afforded by using multiple local searches in a Memetic Algorithm (MA) to solve one problem (a single fitness function), has been verified in many successful experiments. These experiments also give the observation that the local search operator that gives the best results in an MA on the same fitness function for solving a NP-hard problem is instance specific. This paper will pro- vide a theoretical evidence for this observation. In this pa- per, we will formalize the (1+1) Restart Memetic Algorithms applying two different local searches, the first-improvement and the best-improvement, respectively. We will then run them on a single fitness function to solve the Clique Prob- lem. We then show that there are two families of graphs such that, for the first family of graphs, MAs with one local search drastically outperform MAs with the other local search, and vice versa for the second family of graphs. Our study explains why using multiple local searches can outperform using a single local search in Memetic Algorithms.