Comparing Two Local Searches in a (1+1) Restart Memetic Algorithm on the Clique Problem

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.