Creating Children

Summary

The text explains the implementation of the crossover function in genetic algorithms using Elixir programming language.

Abstract

The text is a part of a series on genetic algorithms in Elixir, focusing on the implementation of the crossover function. The author, Sean Moriarity, explains that the crossover function is analogous to reproduction and takes two or more parent chromosomes to produce two or more child chromosomes. The function uses pattern-matching features in Elixir to extract individual chromosomes and perform operations on them. The text also explains the use of Enum.reduce/3, Enum.split/2, and :rand.uniform/1 functions in the implementation of the crossover function. The author notes that this is a simple crossover method known as single-point crossover and that other crossover techniques will be discussed in Chapter 6.

Opinions

The author believes that Elixir's rich set of pattern-matching features makes it a suitable language for implementing genetic algorithms.
The author suggests that single-point crossover is one of the simplest crossover methods used in genetic algorithms.
The author encourages readers to learn more about other crossover techniques in Chapter 6 of the book.

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

With a population of parents prepared for crossover, it’s time to implement the crossover function.

Crossover is analogous to reproduction. It’s a genetic operator that takes two or more parent chromosomes and produces two or more child chromosomes. Thus far, the transformations have produced a list of tuples consisting of two 1000-length bitstrings. You want to produce a population you can pass back into the algorithm function. Implement the crossover function like this:

 crossover =
   fn population ->
     Enum.reduce(population, [],
       fn {p1, p2}, acc ->
         cx_point = :rand.uniform(1000)
         {{h1, t1}, {h2, t2}} =
           {Enum.split(p1, cx_point),
           Enum.split(p2, cx_point)}
         [h1 ++ t2, h2 ++ t1 | acc]
       end
     )
   end

First, take note of the first argument passed to the anonymous function in Enum.reduce/3. Elixir has a rich set of pattern-matching features. In the selection step, the list of chromosomes was turned into a list of tuples of adjacent pairs. Because of this, you can use pattern-matching to extract the individual chromosomes — denoted p1 and p2 for Parent 1 and Parent 2 — and perform some operation on them.

Enum.reduce/3 requires the anonymous function to also accept an accumulator — denoted acc — which takes an initial value and builds from the return value of the function. The initial value here is the empty list shown in the second parameter. The function returns two new chromosomes prepended to the accumulator.

So, how are the new chromosomes created? A random crossover point is selected using Erlang’s rand module. The :rand.uniform/1 function produces a uniform integer between 0 and N-1 where N is the integer parameter it receives. Passing 1000 to this function means you’ll receive a random integer between 0 and 1000.

Enum.split/2 returns a tuple of two enumerables. The enumerables are split at the random point selected earlier. The chromosomes are then recombined with the tails swapped. This is known as single-point crossover and is one of the simplest crossover methods used. You’ll learn more about single-point crossover and other crossover techniques in Chapter 6, Generating New Solutions.

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.