OPTIMIZED CROSSOVER FOR THE INDEPENDENT SET PROBLEM

We propose a knowledge-based crossover mechanism for genetic algorithm s that exploits the structure of the solution rather than its coding. More generally, we suggest broad guidelines for constructing the knowl edge-based crossover mechanisms. This technique uses an optimized cros sover mechanism, in which the one of the two children is constructed i n such a way as to have the best objective function value from the fea sible set of children, while the other is constructed so as to maintai n the diversity of the search space. We implement our approach on a cl assical combinatorial problem, called the independent set problem, The resulting genetic algorithm dominates all other genetic algorithms fo r the problem and yields one of the best heuristics for the independen t 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.