ISSN:
1572-9397
Keywords:
maximum clique
;
genetic algorithms
;
optimized crossover
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract In Balas and Niehaus (1996), 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 (1997) 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009646528813
Permalink
