Adaptive knowledge representation: A content sensitive recombination mechanism for genetic algorithms
✍ Scribed by J. David Schaffer; Amy Morishima
- Publisher
- John Wiley and Sons
- Year
- 1988
- Tongue
- English
- Weight
- 899 KB
- Volume
- 3
- Category
- Article
- ISSN
- 0884-8173
No coin nor oath required. For personal study only.
✦ Synopsis
This article describes ongoing research on content sensitive recornbination operators for genetic algorithms. A motivation behind this line of inquiry stems fkom the observation that biological chromosomes appear to contain special nucleotide sequences whose job is to influence the recombination of the expressible genes. We think of these as punctuation marks t e r n the recombination operators how to do their job. Furthermore, we assume that the distribution of these marks (part of the representation) in a gene pool is determined by the same survivahf-the-fittest and genetic recombination mechanisms that account for the distribution of the expressible genes (the knowledge). A goal of this project is to devise such mechanisms for genetic algorithms and thereby to link the adaptation of a representation to the adaptation of its contents. We hope to do so in a way that capitalizes on the intrinsically parallel behavior of the traditional genetic algorithm. We anticipate benefits of this for machine learning. We describe one mechanism we have devised and present some empirical evidence that suggests it may be as good as or better than a traditional genetic algorithm across a range of search problems. We attempt to show that its action does successfully adapt the search mechanics to the problem space and provide the beginnings of a theory to explain its good performance.
I. MOTIVATION
A genetic algorithm is a powerful general purpose search method devised by Holland' over a decade ago. Since then research has focused on attempts to better understand the sources of its power, to overcome its weaknesses, and to apply it to problems calling for flexible forms of adaptation such as function optimization and machine
The genetic algoirithm (GA) is based on mechanisms abstracted from population genetics and differs from search algorithms that maintain a single "best solution so far." The GA maintains a set of trial solutions, called a population. and operates in cycles called generations. During each generation the following three steps are executed: each member of the population is evaluated (a performance metric is computed on the problem at hand), some members are selected