Introducing a New Advantage of Crossover: Commonality-Based Selection - Robotics Institute Carnegie Mellon University

Introducing a New Advantage of Crossover: Commonality-Based Selection

Conference Paper, Proceedings of 1st Annual Genetic and Evolutionary Computation Conference (GECCO '99), pp. 122 - 128, July, 1999

Abstract

The Commonality-Based Crossover Framework defines crossover as a two-step process: 1) preserve the maximal common schema of two parents, and 2) complete the solution with a construction heuristic. In these "heuristic" oper ators, the first step is a form of selection. This commonality-based form of selection has been isolated in GENIE. Using random parent selection and a non-elitist generational replacement scheme, GENIE does not include fitness-based selection. However, a theoretical analysis shows that "ideal" construction heuristics in GENIE can potentially converge to optimal solutions. Experimentally, results show that the effectiveness of practical construction heuristics can be amplified by commonality- based restarts. Overall, it is shown that the commonality hypothesis is valid--schemata common to above-average solutions are indeed above average. Since common schemata can only be identified by multi-parent operators, commonality-based selection is a unique advantage that crossover can enjoy over mutation.

BibTeX

@conference{Chen-1999-16639,
author = {Stephen Chen and Stephen Smith},
title = {Introducing a New Advantage of Crossover: Commonality-Based Selection},
booktitle = {Proceedings of 1st Annual Genetic and Evolutionary Computation Conference (GECCO '99)},
year = {1999},
month = {July},
pages = {122 - 128},
publisher = {Morgan Kaufmann},
keywords = {genetic algorithms, Traveling Salesman Problem, commonality hypothesis, heuristic amplification},
}