This is an ongoing project that uses a genetic algorithm to optimize the layout of LLVM IR passes used to compile Julia code.
git clone https://github.com/WestleyArgentum/pass-optimizer.gitcd pass-optimizer./init.shjulia pass-ga.jl
Many traditional methods of crossover (single and double point, uniform) assume a genome of a fixed length, or some knowledge about what the optimal length might be. Others support variable length genomes (messy ga, SAGA), but pick largely random points when splicing parent sequences together.
The algorithm employed by this GA is called "Synapsing Variable Length Crossover". It uses the longest common subsequence to identify and split parents genomes in a way that preserves the order and content of the lcs shared by both parents. The paper that formally describes SVLC is behind a paywall, but you can read some here and the code in this repository represents my attempt at an accurate reproduction.
Because this GA relies on variable length genomes, it's important for the mutation function to sometimes insert and remove genes, in addition to simply changing them in place. Right now this is done very agressively at first (with a large number of passes being added / removed / changed), and less agressively over time until the GA has reached a predefined MAX_GENERATIONS and stops.
Please see the open issues for information about planned improvments / known problems.