Knowledge-Based Nonuniform Crossover
Harpal Maini
Kishan Mehrotra
Chilukuri Mohan
Sanjay Ranka
School of Computer and Information Science,
4-116 Center for Science and Technology,
Syracuse University, Syracuse, NY 13244-4100, USA
Abstract
We present a new "knowledge-based nonuniform crossover'' operator for genetic algorithms that generalizes uniform crossover. We extend this to "Dynamic knowledge-based nonuniform crossover,'' which constantly updates the knowledge extracted thus far from the environment's feedback on previously generated chromosomes. Knowledge-based nonuniform crossover can improve on good solutions previously obtained using other algorithms. The modifications made by knowledge-based nonuniform crossover are orthogonal to other changes in parameters of genetic algorithms, and can be pursued together with any other proposed improvements. Whereas most genetic search methods focus on improving move-selection procedures, after having chosen a fixed move-generation mechanism, knowledge-based nonuniform crossover and dynamic knowledge-based nonuniform crossover make the move-generation process itself time-dependent. The same parents may give rise to different offspring at different moments in the evolutionary process, based on the past experience of the species. Simulation results show orders of magnitude improvement of knowledge-based nonuniform crossover over two-point and uniform crossover relative to three NP optimization problems: graph partitioning, soft-decision decoding of linear block codes, and the traveling salesperson problem. In particular, knowledge-based nonuniform crossover has been applied to variants of the graph partitioning problem not easily solved with other methods, and found to improve the quality of the solutions. Dynamic knowledge-based nonuniform crossover opens up the possibility of applying genetic algorithms to Incremental Optimization problems, characterized by a slow change in problem structure over time. Dynamic knowledge-based nonuniform crossover also achieves some of the goals of diploid representations with adaptive dominance, with smaller computational requirements.
