Building a Framework for Genetic Algorithms

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

👈 Using Mix to Write Genetic Algorithms | TOC | Understanding Hyperparameters 👉

You now have an empty project and an idea of what your genetic algorithm framework should look like. It’s time to start implementing each step.

Start by opening the genetic.ex file. The file is populated with some default code and will look something like this:

​ ​defmodule​ Genetic ​do​
​   ...documentation...
​   ​def​ hello ​do​
​     ​:world​
​   ​end​
​ 
​ ​end​

You can delete the default documentation and Hello World function. This module will contain the most basic parts of your genetic algorithm. This is where you’ll define each step of the algorithm based on the rules you determined earlier.

Creating an Initial Outline

In genetic.ex, start by creating a function named run, like this:

​ ​def​ run(...) ​do​
​   population = initialize()
​   population
​   |> evolve()
​ ​end​

This function calls the initialize function, which is responsible for creating the initial population. You might be wondering why the parameters of run are left blank. You’ll worry about them later. For now, concentrate on the overall structure of the code.

After you initialize the population, you pass the population into a function named evolve. evolve is designed to model a single evolution in your genetic algorithm. Below the run function, define evolve, like this:

​ ​def​ evolve(population, max_fitness) ​do​
​   population = evaluate(population, ..., opts)
​   best = hd(population)
​   IO.write(​"​​\rCurrent Best: ..."​)
​   ​if​ ... == max_fitness ​do​
​     best
​   ​else​
​     population
​     |> select()
​     |> crossover()
​     |> mutation()
​     |> evolve()
​   ​end​
​ ​end​

For now, disregard the blank parts of the code. You’ll fill these in at the end. This function evaluates the population and then extracts the “best” solution from the population. You can do this using the hd/1 function because one of the rules for evaluate was that it returns a sorted population. This means the fittest chromosome will always be the first one in the population.

This function also implements the recursion you need. It defines the base or termination case. Part of the termination criteria is left blank for now. It checks some blank value versus the maximum desired fitness. The recursive case is essentially identical to the recursive case from Chapter 1, ​Writing Your First Genetic Algorithm​.

With the basic outline defined, you can start implementing each step.

Initialization

Remember the rules you defined in the previous section? You’ll use them now to implement each step correctly. Start with the initialize function. Based on the design rules discussed previously, you know the function must return a population represented as a list of chromosomes. You also know that it must accept some function which produces an encoding of a single solution.

Above the run function, define the initialize function as follows:

​ ​def​ initialize(genotype) ​do​
​   for _ <- 1..100, ​do​: genotype.()
​ ​end​

This function is a list comprehension that generates chromosomes using the provided genotype/0 function. You might be wondering why this function is called genotype. You’ll learn more about this in Chapter 3, ​Encoding Problems and Solutions​. 1..100 is a range that creates a total of 100 chromosomes. Remember, your population can be any size. You can change this depending on your problem. The function returns a list of 100 chromosomes.

Evaluation

The next step is evaluation. Your rules for evaluation require you to create a function that sorts the provided population based on a provided fitness function. Based on how you define the transformations in the outline of your algorithm, the first parameter of the function should be a population.

Below initialize/1, create a new function named evaluate:

​ ​def​ evaluate(population, fitness_function) ​do​
​   population
​   |> Enum.sort_by(fitness_function, &>=/2)
​ ​end​

This function is identical to the evaluate function that you defined in Chapter 1, ​Writing Your First Genetic Algorithm​. However, rather than sorting chromosomes by sum, you sort chromosomes based on the provided fitness_function.

Selection

Now that you have a sorted population, you can define the selection step. Remember that your selection function needs to return an enumerable of tuples. For now, it doesn’t take any inputs besides population.

Below evaluate/2, define the select/1 function, like this:

​ ​def​ select(population) ​do​
​   population
​   |> Enum.chunk_every(2)
​   |> Enum.map(&List.to_tuple(&1))
​ ​end​

This function is identical to the select function you defined in Chapter 1, ​Writing Your First Genetic Algorithm​. The resulting population is an enumerable of tuples. This makes it easier to implement crossover.

Crossover

At this point, you performed initialization, evaluation, and selection. The population is transformed and ready for recombination.

Below select/1, add the following:

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

This function should look similar to the crossover method in the previous chapter. The only difference is that :rand.uniform/1 accepts the length of one of the parents as input. This is done so the algorithm can work on chromosomes of any length. Other than that, the algorithm is identical. It splits the parents at the crossover point, creates two new children, and prepends them to the population.

Mutation

The final step in the algorithm is mutation. Mutation has no special rules. It should look identical to the mutation function you defined in Chapter 1, ​Writing Your First Genetic Algorithm​.

Below crossover/1, add the following:

​ ​def​ mutation(population) ​do​
​   population
​   |> Enum.map(
​       ​fn​ chromosome ->
​         ​if​ ​:rand​.uniform() < 0.05 ​do​
​           Enum.shuffle(chromosome)
​         ​else​
​           chromosome
​         ​end​
​       ​end​
​     )
​ ​end​

You iterate over every chromosome in the population, checking to see if some condition is met. The condition is meant to model picking chromosomes at random with a probability of 5%. If a chromosome is picked, its genes are shuffled. If it isn’t, it remains the same.

With that, the basic steps of your algorithm are complete.

Filling in the Blanks

Remember the blanks you left in the evolve and run functions? Also, did you notice that none of the functions you called in evolve took parameters? It’s time to fill in these blanks.

The functions initialize/2 and evaluate/2 take extra parameters aside from a population. Because you won’t be calling these functions individually outside the module, you can take these parameters inside the run and evolve functions and pass them to initialize and evaluate from there. You need to take the following parameters into both run and evaluate: fitness_function, genotype, and max_fitness.

Additionally, with the required parameters in place, you can fill in the blanks left in the outline of the run and evolve functions.

Edit the functions so they look like this:

​ ​def​ run(fitness_function, genotype, max_fitness) ​do​
​   population = initialize(genotype)
​   population
​   |> evolve(fitness_function, genotype, max_fitness)
​ ​end​
​ ​def​ evolve(population, fitness_function, genotype, max_fitness) ​do​
​   population = evaluate(population, fitness_function)
​   best = hd(population)
​   IO.write(​"​​\rCurrent Best: ​​#{​fitness_function.(best)​}​​"​)
​   ​if​ fitness_function.(best) == max_fitness ​do​
​     best
​   ​else​
​     population
​     |> select()
​     |> crossover()
​     |> mutation()
​     |> evolve(fitness_function, genotype, max_fitness)
​   ​end​
​ ​end​

At this point, all of the blanks are filled. Additionally, the evolve and run functions accept the required problem-specific parameters and pass them to the functions that need them.

You now have a complete, working framework.

👈 Using Mix to Write Genetic Algorithms | TOC | Understanding Hyperparameters 👉

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.