Evolutionary Solver: Coalescence
March 5, 2011
This is the fifth post in a series on Evolutionary Solvers.
Once a mate has been selected from a population, offspring needs to be generated. On the genetic level this is anything but fun and games. The biological process of gene recombination is horrendously complicated and itself subject to evolution (meiotic drive for example, where genes evolve to affect the random process of meiosis and thus improve their chances of ending up in offspring). The digital variant is much simpler. This is partially because genes in evolutionary algorithms are not very similar to biological genes. Ironically, biological genes are far more digital than programmatic genes. As Mendel discovered in the 1860′s, genes are not continuously variable qualities. Instead they behave like on-off switches. Genes in evolutionary solvers like Galapagos behave like floating point numbers, that can assume all the values between two numerical extremes. When Mendel crossed wrinkly and smooth peas, he ended up with specific frequencies of each in the subsequent generations, but never with a pea that was somewhat wrinkly and somewhat smooth. With Evolutionary Algorithms there’s no reason why we couldn’t interpolate genes this way.
When we mate two genomes, we need to decide what values to assign to the genes of the offspring. Again, Galapagos provides several mechanisms for achieving this.
Imagine we have two genomes of four genes each. There are no gender or sex-based characteristics in the solver so the combination of M and D is potentially a completely symmetrical process. A possible coalescence mechanism that is somewhat synonymous with biological recombination is Crossover Coalescence. In Crossover mating, junior inherits a random number of genes from mom and the remainder from dad. In this mechanism gene value is maintained. Crossover is best suited for then M and D are already quite similar. If we operate under the assumption that the genes in each genome have to cooperate in order to yield a high fitness, it makes no sense to combine them willy nilly. It would be like taking the best players from each team at a sporting event and mashing them into a ‘super’ team. It is unlikely that this new combination of talent would be able to cooperate as well as the original teams (who have spend years practising together) and therefore it is unlikely that they will form a true dream team.
Blend Coalescence will compute new values for genes, basically averaging the values, instead of duplicating existing genes. This is not entirely without precedent in biology, it depends a bit on what level of scale you define ‘gene’. There is no single gene for eye-colour, it’s a combination of several genes acting together. When we talk about gene-complexes it is possible to imagine interpolation of parental genes. We could also add a blending preference based on relative parental fitness. If mum is fitter than dad for example, her gene values can be made more prominent in the offspring.
The image below shows Crossover, Blend and Preferenced-Blend algorithms respectively: