Abstract:
In recent years, the advantage afforded by using multiple local searches in a Memetic Algorithm to solve one problem (a single fitness function), has been verified in many successful experiments. However, theoretical studies cannot explain
why Memetic Algorithms with multiple local searches often outperform Memetic
Algorithms with a single local search in these experiments. In this paper, we will
formalize a (1+1) Restart Memetic Algorithm and two different local searches,
and 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,
Memetic Algorithms with one local search drastically outperform Memetic Algorithms with the other local search, and vice versa for the second family of graphs.
Furthermore, we propose a (1+1) Restart Memetic Algorithm with an Alternative
Local Search, and show that the proposed algorithm is expected to solve the Clique
Problem on both families of graphs efficiently. Lastly, we verify our theoretical results by experiments.