Illinois Genetic Algorithms Laboratory

Rothlauf, F., Goldberg, D.E. (2000)
TR No.: 2000011 | Download PDF | Download PS

Abstract:

When handling tree networks, researchers have sometimes tried using the pruefernumber representation for encoding networks, but GAs often degraded or broke down when used on this encoding. This paper investigates the locality of the pruefernumber and its effect on the performance of a Genetic Algorithm (GA). The locality describes how the neighborhood of the genotype is preserved, when constructing the phenotype (the tree) from the genotype (the pruefernumber). It is shown that the locality of the pruefernumber is highly irregular on the entire solution space and that the performance of a GA depends on the structure of the optimal solution.
A GA is able to perform well only for networks that have a good locality (stars). For all other types of networks (lists, trees) the locality is low and a GA fails to find the best list or tree. Using a GA with the pruefernumber encoding can be useful, when the good solutions tend to be a star. The locality of an encoding could have a strong influence on the performance of a GA. When choosing encodings for optimization problems, researchers should be aware of this and be careful with low locality encodings. If the locality of the encoding is low, a failure of the GA is often inescapable.