Genetic representation
As a genetic representation (also problem representation ) the way is referred to as an optimization problem , is encoded so that it with an evolutionary algorithm can be released (EA). EA look for solutions to optimization problems using methods of natural evolution . The term genetic representation encompasses both the concrete data structures and data types with which the genetic material of the solution candidates is realized, as well as the relationships between the search space and the problem space. In the simplest case, the search space corresponds to the problem space ( direct representation ). The choice of the problem representation is tied to the choice of the genetic operators , both of which have a decisive effect on the efficiency of the optimization.
The genome of a candidate for a solution often takes the form of a bit string , a list of real numbers , a sequence (for combinatorial problems such as Traveling Salesman ) or a tree .
Differentiation between search and problem areas
In nature, information about all the basic properties ( phenotype ) of an organism (e.g. external appearance, metabolism or basic behavior) is stored within each organism, as Gregor Mendel discovered around 1860. Today it is known that this storage is realized with the genetic code . At the molecular level, the defining properties are encoded as DNA . The entire genetic makeup of an organism is called a genotype . The genotype determines the phenotype, albeit through a complicated process called gene expression .
Analogous to biology, evolutionary algorithms differentiate between problem space (corresponds to phenotype ) and search space (corresponds to genotype ). The problem space thus contains concrete solutions for the problem dealt with, while the search space contains the coded solutions. The illustration (Engl. Map ) by search space on problem space is called Genotype-Phenotype Mapping referred. The genetic operators are applied to elements of the search space; for evaluation , elements of the search space are mapped to elements of the problem space using genotype-phenotype mapping.
Relationships between search and problem space
redundancy
If there are more possible genotypes than phenotypes, the genetic representation of the EA is said to be redundant. In nature one speaks of the degenerated genetic code. In the case of a redundant representation, neutral mutations are possible; these are mutations that change the genotype but do not affect the phenotype. In biology, the neutral theory of molecular evolution says that this effect plays a dominant role in natural evolution. Research results in the field of evolutionary algorithms in turn suggest that neutral mutations can improve the functionality of EA insofar as populations that have converged to a local optimum have a genetic drift to escape this local optimum.
Locality
The locality of a genetic representation corresponds to the extent to which distances in the search space are retained in the problem space after the genotype-phenotype mapping. This means that a high locality has a representation if and only if neighbors in the search area are also neighbors in the problem area. So that successful schemas are not destroyed by the genotype-phenotype mapping after a minor mutation , the locality of a representation must be high.
Scaling
With genotype-phenotype mapping, the elements of the genotype can be scaled (weighted) differently. The simplest case is uniform scaling: All elements of the genotype are weighted equally in the phenotype. A common scaling is exponential. If whole numbers are coded in binary, the individual digits of the resulting binary number have exponentially different weightings in the representation of the phenotype.
- Example: The number 90 is written in binary ( base two) as 1011010. If you change one of the first digits in binary notation, this has a significantly greater impact on the coded number than any changes in the last digits (the selection pressure is exponentially stronger in the front digits).
For this reason, the effect occurs with exponential scaling that the “rear” places in the genotype are randomly fixed before the population has reached the optimum enough to adapt these subtleties.
Individual evidence
- ^ Edgar Galván-López, Stephen Dignum and Riccardo Poli: The Effects of Constant Neutrality on Performance and Problem Hardness in GP . In: Genetic Programming: 11th European Conference, EuroGP 2008, Naples, Italy, March 2008, Proceedings . Springer-Verlag, p. 313.
literature
- Franz Rothlauf: Representations for Genetic and Evolutionary Algorithms . Springer-Verlag, Berlin Heidelberg, ISBN 3-540-25059-X .