Abstract:
In recent years, the advantage affrded 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 provide a theoretical evidence for this observation. In this paper, we will formalize the (1+1) RestartMemetic Algorithms applying two diffrent local searches, the first-improvement and the best-improvement, respectively. We will then run them on a single fitness function to solve the Clique Problem. 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.
