Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems

In an earlier paper, we have developed a heuristic for generating large cliques in an arbitrary graph, by repeatedly taking two cliques and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time through bipartite matching in the complement of the subgraph. Aggarwal, Orlin and Tai recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover operation. Inspired by their approach, we examine variations of each element of the genetic algorithm – selection, population replacement and mutation – and develop a steady-state genetic algorithm that performs better than its competitors on most problems.