Computational Intelligence by unknow

Author:unknow
Language: eng
Format: epub, pdf
Publisher: Springer London, London

13.1.3 The Principle of Minimal Alphabets

The principle of minimal alphabets is sometimes invoked to claim that binary encodings, as used by genetic algorithms, are “optimal” in a certain sense. The core idea is that the number of possible schemata should be maximized relative to the size of the search space (or the population size), so that the parallelism inherent in the search for schemata is maximally effective. That is, with the chromosomes of the population a number of schemata should be covered that is as large as possible.

If chromosomes are defined as strings of length L over an alphabet , then the ratio of the number of schemata to the size of the search space is . Clearly, this ratio is maximized if the size of the alphabet is minimized. Since the smallest usable alphabet has , binary codings optimize this ratio.

A more intuitive form of this argument was put forward by Goldberg (1989): the larger the size of the alphabet, the more difficult it is to find meaningful schemata, because a schema is matched by a larger number of chromosomes. Since a schema averages over the fitness of the matching chromosomes, the quality of a schema may be tainted by some bad chromosomes (low fitness) that happen to match the same schema. Therefore one should strive to minimize the number of chromosomes that are matched by a schema. Since a schema h matches chromosomes, we should use an alphabet of minimal size. Again, since the smallest usable alphabet has , binary codings can be expected to be optimal.

Whether these arguments are convincing is debatable. At least one has to admit that there is a tradeoff between maximizing the number of schemata relative to the search space and expressing the problem in a more natural manner with the help of larger alphabets (Goldberg 1991). Furthermore, a strong argument in favor of larger alphabets has been put forward by Antonisse (1989).

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.