Implementing Chromosome Repairment

Genetic Algorithms in Elixir — by Sean Moriarity (54 / 101)

👈 Crossing Over More Than Two Parents | TOC | What You Learned 👉

Sometimes, you’re limited in the crossover strategy you can use. In Chapter 4, ​Evaluating Solutions and Populations​, you explored a solution to the N-queens problem that wouldn’t work because you used single-point crossover. One approach that works around limitations in crossover strategies is the concept of chromosome repairment. Chromosome repairment is the process of ensuring solutions remain valid after crossover or mutation. In the case of N-queens, using single-point crossover ruins the integrity of the permutation. This means after crossover takes place, you have to go in and individually repair every chromosome.

Chromosome repairment isn’t necessary if you choose a crossover strategy that maintains the integrity of your permutation; however, if you’re restricted to using specific crossover strategies, then it will be necessary. To implement chromosome repairment into your genetic algorithm, add the following to crossover/1 in lib/genetic.ex:

​ ​def​ crossover(population, opts \\ []) ​do​
​   crossover_fn = Keyword.get(opts,
​                              ​:crossover_type​,
​                              Toolbox.Crossover.single_point/2)
​   population
​   |> Enum.reduce([],
​       ​fn​ {p1, p2}, acc ->
​         {c1, c2} = apply(crossover_fn, [p1, p2])
​         [c1, c2 | acc]
​     )
​   |> Enum.map(& repair_chromosome(&1))
​ ​end​

The addition of Enum.map/2 will go through each chromosome in the population and call repair_chromosome/1, which is a function that will repair chromosomes. Now, implement the repair_chromosome/1 function like this:

​ ​def​ repair_chromosome(chromosome) ​do​
​   genes = MapSet.new(chromosome.genes)
​   new_genes = repair_helper(chromosome, 8)
​   %Chromosome{chromosome | ​genes:​ new_genes}
​ ​end​
​ ​defp​ repair_helper(chromosome, k) ​do​
​   ​if​ MapSet.size(chromosome) >= k ​do​
​     MapSet.to_list(chromosome)
​   ​else​
​     num = ​:rand​.uniform(8)
​     repair_helper(MapSet.put(chromosome, num), k)
​   ​end​
​ ​end​

Here, you use a MapSet to get the unique elements of the provided chromosome. Next, you pass it into a recursive helper. The helper function will generate random numbers and attempt to put them into the MapSet until the chromosome is the appropriate length.

Now, if you change crossover/1 back to use single_point_crossover/2, you can run scripts/nqueens.exs and obtain a solution:

​ ​$ ​​mix​​ ​​run​​ ​​scripts/nqueens.exs​
​ Current Best: 8
​ [3, 6, 2, 7, 1, 4, 0, 5]

👈 Crossing Over More Than Two Parents | TOC | What You Learned 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.