Representation and hidden bias II: eliminating defining length bias in genetic search via shuffle crossover

Published 20 August 1989

Richard A. Caruana, Larry J. Eshelman, J. David Schaffer

Citations31

TL;DR

A new crossover operator is introduced that eliminates the position dependent bias of the traditional crossover operator by shuffling the representation prior to applying crossover, and experimental results show that shuffle crossover outperforms traditional crossover on a suite of five function optimization problems.

Abstract

The traditional crossover operator used in genetic search exhibits a position-dependent bias called the dcfining-length bias. We show how this bias results in hidden biases that are difficult to anticipate and compensate for. We introduce a new crossover operator, shuffle crossover, that eliminates the position dependent bias of the traditional crossover operator by shuffling the representation prior to applying crossover. We also present experimental results that show that shuffle crossover outperforms traditional crossover on a suite of five function optimization problems.

Keywords

Computer Science

The MIT Press eBooksAdaptation in Natural and Artificial Systems

35,568 Citations1992John H. Holland

Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.

IEEE Transactions on Systems Man and CyberneticsOptimization of Control Parameters for Genetic Algorithms

2,831 Citations1986John J. Grefenstette

GA's are shown to be effective for both levels of the systems optimization problem and are applied to the second level task of identifying efficient GA's for a set of numerical optimization problems.

international conference on Genetic algorithmsReducing bias and inefficiency in the selection algorithm

1,408 Citations1987James E. Baker

A sheet which is a blend of water-insoluble fibers and pieces of film of a dry material which converts to a gel quickly on contact with a large amount of water.

Kluwer international series in engineering and computer scienceA Connectionist Machine for Genetic Hillclimbing

717 Citations1987David H. Ackley

This dissertation focuses on the development of a heuristic search algorithm that automates the very labor-intensive and therefore time-heavy and expensive process of manually cataloging discrete-time components of a genealogy tree.

international conference on Genetic algorithmsAn adaptive crossover distribution mechanism for genetic algorithms

210 Citations1987J. David Schaffer, Amy Morishima

Using an electronic template triggered at the point of consultation increased recruitment to prospective research approximately nine-fold compared with searching for symptom codes and study mailouts.

Elsevier eBooksRepresentation and Hidden Bias: Gray vs. Binary Coding for Genetic Algorithms

204 Citations1988Richard A. Caruana, J. David Schaffer

Experimental results are presented that indicate Gray coding is generally superior to binary coding for function optimization using the genetic algorithm and suggests that Gray coding eliminates the “Hamming cliff” problem that makes some transitions difficult when using a binary representation.

Elsevier eBooksUSING MULTIPLE REPRESENTATIONS TO IMPROVE INDUCTIVE BIAS: GRAY AND BINARY CODING FOR GENETIC ALGORITHMS

13 Citations1989Richard A. Caruana, J. David Schaffer +1 more

Experimental results show that genetic search using a multiple representation – Gray-coded mutation and binary-coded crossover – outperforms search using just one representation.