Understanding the Flow of Genetic Algorithms

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

👈 Initializing the Population | TOC | Selecting Parents 👉

You’re now ready to start writing your algorithm. But, before you begin, what do you notice about the structure of the genetic algorithm previously described? Specifically, what happens after children are mutated?

The answer: the process repeats itself. Genetic algorithms are recursive meaning the algorithm repeats itself over and over until it hits a termination point.

Below the initial population, add the following:

​ algorithm =
​   ​fn​ population, algorithm ->
​     ​# Algorithm here​
​   ​end​

The algorithm is an anonymous function that takes two parameters: population represents the current generation’s population, and algorithm is a reference to itself. This is a trick used to implement a recursive anonymous function. It’s not essential to understand why this works or why this is necessary. All you need to know is that algorithm is a reference to your algorithm function.

In other languages, you’ll likely see genetic algorithms implemented using loops instead of recursion. You need to use recursion because Elixir doesn’t support loops. But remember, a recursive function is just as powerful as a loop.

Recursive functions usually have two branches: a base-case and a recursive case. The base case produces the solution to your problem. You should think of this as the termination criteria. Your termination criteria are the measurements you use to determine when to stop your algorithm. Because you already know what your final solution should look like — a bitstring with a sum of 1000 — you can tell your algorithm to stop when this solution appears. You’ll learn more about other strategies for telling your algorithm when to stop in Chapter 4, ​Evaluating Solutions and Populations​. Replace the # Algorithm here with the following:

​ best = Enum.max_by(population, &Enum.sum/1)
​ IO.write(​"​​\rCurrent Best: "​ <> Integer.to_string(Enum.sum(best)))
​ ​if​ Enum.sum(best) == 1000 ​do​
​   best
​ ​else​
​   ​# Rest of algorithm here​
​ ​end​

The first line extracts the current best solution from the population. The best solution is the one with the largest sum. Next, the algorithm prints out the value of the largest sum. Finally, you define your termination criteria — telling the algorithm to stop and return the best solution when the maximum sum has reached 1000.

Now, once again, refer to the steps in a genetic algorithm. The first step is to initialize a population. You already have a population; now you need to do everything else. Replace # Rest of algorithm here with the following:

​ population                ​# Initial Population​
​ |> evaluate.()            ​# Evaluate Population​
​ |> selection.()           ​# Select Parents​
​ |> crossover.()           ​# Create Children​
​ |> algorithm.(algorithm)  ​# Repeat the Process with new Population​

Notice how the algorithm is defined as a series of transformations on the initial population. The population starts as a random list of 1000-length bitstrings. It’s then passed into a set of functions that do some work on the population to produce a new, hopefully better population.

This is a pattern you’ll see throughout this book. You start with a population, do some predefined work on the population, and then pass the population on to the next generation. A single step in the pattern is called an evolution. Genetic algorithms work via evolutions over multiple generations.

Now you need to go about implementing these transformations. Start by adding the following below your population definition:

​ evaluate = ​fn​ population -> ... ​end​
​ selection = ​fn​ population -> ... ​end​
​ crossover = ​fn​ population -> ... ​end​

Here, you create stubs for three anonymous functions: evaluate, selection, and crossover. Each of these functions represents a step in the genetic algorithm. Each function takes a population and returns a transformed version of the population.

Evaluating the Population

Start by writing the first function — evaluate. This function represents Step #2 in the genetic algorithm. This function takes a population, evaluates each chromosome based on a fitness function, and sorts the population based on each chromosome’s fitness. Fitness is simply a heuristic that tells you how good or bad a solution is — a fitness function calculates this fitness for you. In this problem, the fitness of a chromosome is represented by the sum of the bitstring.

Replace the stub of the the evaluate function with this:

​ evaluate =
​   ​fn​ population ->
​     Enum.sort_by(population, &Enum.sum/1, &>=/2)
​   ​end​

The evaluate function uses the Enum.sort_by/3 function to sort the population by the sum in descending order. This means that better solutions will exist at the top of the population. It also means that better solutions will be grouped together. Sorting your population is important for the next step.

👈 Initializing the Population | TOC | Selecting Parents 👉

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.