Crossover in evolutionary algorithms with dynamic linear genome representations

Evolutionary algorithms typically use fixed data structures to represent problem solutions. Dynamic structures allow a more natural growth in complexity during the optimization, and make it possible for the complexity itself to adapt to the problem requirements, as shown by the success of some tree-based implementations. We are interested in exploring evolutionary computation with linear genomes that are allowed to change in length and ordering; such a representation may be more natural for some optimization problems and is more similar to nature, allowing for some interesting evolutionary phenomena such as copy number variations to be studied with evolutionary computation as a model. A major hurdle for implementing such evolutionary algorithms is the choice of crossover. The aim of this project is to critically analyze what crossover should mean in such a setting, and compare the different approaches in terms of optimization performance and, more broadly, evolutionary dynamics.

Natural selection is the name given by Charles Darwin to his observation that the same principle of "selection" we have applied for milennia in artificial breeding of livestock and crops is also inevitable in nature, simply because some kinds of organisms are more likely to survive than others. Interestingly, natural selection is not limited to biological organisms. Computer scientists use programs called evolutionary algorithms to evolve solutions to difficult problems by artificially simulating an environment where populations of candidate solutions struggle for "life", instead of organisms. These algorithms are powerful problem solvers, but can also be used as a computer model for studying how natural selection works. However, evolutionary algorithms often represent their evolving solutions by fixed data structures -- typically a string of ones and zeroes of a fixed length --, which makes them easier to work but sacrificing some essential similarity to nature's DNA: many mutations induce structural changes such as copying a gene, deleting it, or moving it to a different location, none of which are allowed in traditional genetic algorithms. In this project we study how evolutionary algorithms that allow such structural mutations would work. In particular, we are interested in how sexual reproduction can be implemented.