Document Type

Report

Date

4-15-1994

Embargo Period

5-7-2012

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.

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.

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.