A replicator equations-based evolutionary algorithm for the maximum clique problem

In this paper we propose a heuristic based evolutionary algorithm for the Maximum Clique Problem. The algorithm is based on a local search heuristic centered on a continuous formulation of the problem which is approached with a class of dynamical systems called Replicator Equations. We show how, embedding this local search heuristic within an evolutionary algorithm, help the replicator equations heuristic to find larger cliques, and lead to an effective algorithm for the Maximum Clique Problem. Experimental results performed on a class of benchmark instances from the literature assess the effectiveness of the proposed algorithm.