SECTION 3
THE GENETIC ALGORITHM
3.1 Overview
The genetic algorithm is an iterative improvement stochastic search method appro-
priate for application to combinatorial optimization problems and based on the evolution
of biological systems. It implements the fundamental idea of survival fitness on a
population of string structures which are coded representations of solution candidates
selected from the solution space of the optimization problem. The population of candi-
date solutions (which collectively represent the current estimate of the optimum solution)
is subjected to a set of stochastic genetic operators which transform a current population
into a new (descendent) population. A variety of distinct genetic operators (based on bio-
logical analogs) are available and are reported in the literature [Davi87, Gold89a, Gref85,
Gref87]. The most important of them are (1) proportional reproduction, (2) crossover and
(3) mutation. A one, two or three operator genetic algorithm employing combinations of
these operators with fixed population size is referred to herein as a simple genetic algo-
rithm.
The genetic operators are all implemented stochastically, but they do not result in a
simple random walk through the search space. They represent a highly structured search
which exploits the historical record of performance reflected at each stage of the search
by the current population. It is the novel use of this historical record which is central to
the appeal of the genetic algorithm.
Genetic algorithms usually operate on populations of bit-strings (i.e. the optimiza-
tion problem is usually coded such that its search space is defined over a binary string
alphabet), and they always attempt to maximize some strictly nonnegative objective