OPTIMIZED CROSSOVER-BASED GENETIC ALGORITHMS FOR THE MAXIMUM CARDINALITY AND MAXIMUM WEIGHT CLIQUE PROBLEMS

In Balas and Niehaus (1996), we have developed a heuristic for generat ing large cliques in an arbitrary graph, by repeatedly taking two cliq ues and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time throu gh bipartite matching in the complement of the subgraph. Aggarwal, Orl in and Tai (1997) recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover o peration. Inspired by their approach, we examine variations of each el ement of the genetic algorithm-selection, population replacement and m utation-and develop a steady-state genetic algorithm that performs bet ter than its competitors on most problems.