Linking the dynamics of genetic algorithms to the encoding of information

Sammanfattning: Genetic algorithms are complex constructs often used as heuristic search methods in contexts ranging from combinatorial optimisation to in silico evolution. They draw inspiration from the principles of biological evolution by utilizing the concepts of mutation, reproduction and selection in order to improve a population of solutions. The solutions are often represented as abstract data sequences, e.g. as binary strings, though it has been shown that the choice of encoding alters the performance of the search. In this thesis, the dynamics of four types of encodings used to evolve a set of integers are investigated: the previously researched bijective Binary and Gray code maps, as well as an introduced encoding scheme which includes non-coding data, denominated the consensus map. Coding parts of the consensus sequences are signified by pre-determined start sequences, after which subsequent code is interpreted via either the Binary or the Gray code scheme. The performance of the genetic algorithm is measured by the ability to solve four problems with different search spaces. The dynamics are also investigated by identifying the effects the encodings have on the distribution of cost effects due to point mutations, as well as by the ability to produce good solutions under a range of different mutation rates. It is found that the bijective maps give rise to similar distributions of cost effects, but significantly different performances. The consensus encodings instead allow for higher robustness with respect to different mutation rates, as well as a robustness towards highly negative effects due to point mutations. It is also shown that having an encoding–decoding map which allows for both smaller and larger steps in phenotype-space is an important part of being able to produce good solutions in a range of cases.