Document Type
Report
Date
4-15-1994
Keywords
algorithms
Language
English
Disciplines
Computer Sciences
Description/Abstract
We present a new "knowledge-based non-uniform crossover" (KNUX) operator for genetic algorithms (GA's) that generalizes uniform crossover. We extend this to "Dynamic KNUX" (DKNUX), which constantly updates the knowledge extracted so far from the environment's feedback on previously generated chromosomes. KNUX can improve on good solutions previously obtained by using other algorithms. The modifications made by KNUX are orthogonal to other changes in parameters of GA's, and can be pursued together with any other proposed improvements. Whereas most genetic search methods focus on improving the move-selection procedures, after having chosen a fixed move-generation mechanism, KNUX and DKNUX 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 KNUX over two-point and uniform crossover, on three NP optimization problems: graph partitioning, soft-decision decoding of linear block codes, and the traveling salesperson problem. KNUX has been applied to variants of the graph partitioning problem that cannot be solved easily using non-GA approaches, and to improve quality of solutions obtained using non-GA methods. DKNUX opens up the field of applying GA's to Incremental Optimization problems, characterized by a slow change in problem structure with time. DKNUX also achieves some of the goals of diploid representations with adaptive dominance, with smaller computational requirements.
Recommended Citation
Maini, Harpal; Mehrotra, Kishan; Mohan, Chilukuri K.; and Ranka, Sanjay, "Knowledge-Based Nonuniform Crossover" (1994). Electrical Engineering and Computer Science - Technical Reports. 157.
https://surface.syr.edu/eecs_techreports/157
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-93-31
Authors later published: Maini, H.; Mehrotra, K.; Mohan, C.; Ranka, S., "Knowledge-based nonuniform crossover," Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on , vol., no., pp.22,27 vol.1, 27-29 Jun 1994 doi: 10.1109/ICEC.1994.350048.