Knowledge-Based Nonuniform Crossover

We present a new knowledge-based non-uniform crossover (KNUX) operator for genetic algorithms (GA\u27s) that generalizes uniform crossover. We extend this to Dynamic KNUX (DKNUX), which constantly updates the knowledge extracted so far from the environment\u27s 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\u27s, 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\u27s 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