Next: Basic Operators
Up: Appendix A: Review of
Previous: Appendix A: Review of
The choice of representation of the problem in terms of how many model parameters,
their encoding, range of values and required resolution is perhaps the
most important decision we face when using genetic algorithms. In particular,
we must decide whether to use ``direct'' representation of the problem (in
terms of floating point numbers,for example) or to ``encode'' the solution in
terms of a
suitable ``alphabet'', usually binary. In his pioneering work in genetic
algorithms Holland employed the binary representation to prove his schemata
theorem which provides the theoretical foundation for the workings of the
genetic algorithm Goldberg (1989a); Holland (1975). This theorem proves
that short, low order schemata are more likely to be preserved by the evolution
process in contrast to long high order schemata which are more likely to be
disrupted by crossover and mutation .
Short, low order schemata, therefore, are likely to end
up associated with highly fit individuals, that is, with the best solutions to
the problem. Therefore, if we can encode our model parameters in such a way
that the promising short low-order schemata are produced, we may achieve a faster
convergence and obtain a better solution. If we use binary encoding, in order
to have short, low-order schemata, the model parameters must be
suitably encoded with related model parameters being put close together in the
binary string representing an individual Goldberg (1989a). The problem is
that in general we may not know before hand which parameters are related to
others or to what extent they are related. Therefore, in general it is
difficult to establish the order of the predominant schemata in a given
encoding of the model parameters.
Next: Basic Operators
Up: Appendix A: Review of
Previous: Appendix A: Review of
Stanford Exploration Project
11/11/2002