Optimized Crossover for the Independent Set Problem

We propose a knowledge-based crossover mechanism for genetic algorithms that exploits the structure of the solution rather than its coding. More generally, we suggest broad guidelines for constructing the knowledge-based crossover mechanisms. This technique uses an optimized crossover mechanism, in which the one of the two children is constructed in such a way as to have the best objective function value from the feasible set of children, while the other is constructed so as to maintain the diversity of the search space. We implement our approach on a classical combinatorial problem, called the independent set problem. The resulting genetic algorithm dominates all other genetic algorithms for the problem and yields one of the best heuristics for the independent set problem in terms of robustness and time performance. The primary purpose of this paper is to demonstrate the power of knowledge based mechanisms in genetic algorithms.