A genetic algorithm tutorial - Soft Computing and Intelligent

This tutorial covers the canonical genetic algorithm as well as more experimental forms of genetic algorithms, including parallel island models and parallel cellular genetic algorithms. The tutorial also illustrates genetic search by hyperplane sampling. The theoretical foun- dations of genetic algorithms are reviewed, include the schema theorem as well as recently developed exact models of the canonical genetic algorithm. Keywords: Genetic algorithms, search, parallel algorithms I. Introduction Genetic algorithms are a family of computational models inspired by evolution. These algorithms encode a potential solution to a specific problem on a simple chromosome-like data structure, and apply recombination

operators to these structures in such a way as to preserve critical information. Genetic algorithms are often viewed as function optimizers, although the range of problems to which genetic algorithms have been applied is quite broad. An implementation of a genetic algorithm begins with a population of (typically random) chromosomes. One then evaluates these structures and allocates reproductive opportunities in such a way that those chromosomes which represent a better solution to the target problem are given more chances to 'reproduce' than those chromosomes which are poorer solutions. The 'goodness' of a solution is typically defined with respect to the current population. This particular description of a genetic algorithm is intentionally abstract because in some sense, the term genetic algorithm has two meanings. In a strict interpre- tation, the genetic algorithm refers to a model introduced and investigated by John Holland (1975) and his students (for example DeJong, 1975). It is still the case that most of the existing theory for genetic algorithms applies either solely or primarily to the model introduced by Holland, as well as variations on what will be referred to in this paper as the canonical genetic algorithm. Recent theoretical advances in modelling genetic algorithms also apply primarily to the canonical genetic algorithm (Vose, 1993). In a broader usage of the term, a genetic algorithm is any population-based model that uses selection and recombination operators to generate new sample points in a search space. Many genetic algorithm models have been 0960-3174 9 1994 Chapman & Hall introduced by researchers largely working from an experi- mental perspective. Many of these researchers are appli- cation oriented and are typically interested in genetic algorithms as optimization tools. The goal of this tutorial is to present genetic algorithms in such a way that students new to this field can grasp the basic concepts behind genetic algorithms as they work through the tutorial. It should allow the more sophisti- cated reader to absorb this material with relative ease. The tutorial also covers topics, such as inversion, which have sometimes been misunderstood and misused by researchers new to the field. The tutorial begins with a very low-level discussion of optimization to introduce basic ideas in optimization as well as basic concepts that relate to genetic algorithms. In Section 2 a canonical genetic algorithm is reviewed. In Section 3 the principle of hyperplane sampling is explored and some basic crossover operators are introduced....

Website: sci2s.ugr.es | Filesize: -
No of Page(s): 21
Download A genetic algorithm tutorial - Soft Computing and Intelligent ....pdf