R-evo: a Reactive Evolutionary Algorithm for the Maximum Clique Problem

An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem. In the framework of estimation-of-distribution algorithms (EDA), guided mutation uses a model distribution to generate the offspring by combining the local information of solutions found so far with global statistical information. Each individual is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure that it represents a legal clique. The novel reactive and evolutionary algorithm (R-evo) proposed in this paper starts from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by local search with memory, in the reactive search framework. In particular, the estimated distribution is used to periodically initialize the state of each individual based on the previous statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution concept with reactive search produces significantly better results than EA/G and is remarkably robust w.r.t. the setting of the algorithm parameters. R-evo adopts a drastically simplified low-knowledge version of reactive local search (RLS), with a simple internal diversification mechanism based on tabu-search, with a prohibition parameter proportional to the estimated best clique size. R-evo is competitive with the more complex full-knowledge RLS-evo which adopts the original RLS algorithm. For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G for comparable or smaller CPU times.