Defining Termination Criteria

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

👈 Applying a Penalty to the Shipping Problem | TOC | Applying Termination Criteria to Shipping 👉

Next to a good fitness function, termination criteria is the most important aspect of your genetic algorithms. If you don’t know when to stop and return a solution, you’ll never get a solution in the first place. The goal of termination criteria is to stop the algorithm when it has reached maximum fitness. You could write a perfect algorithm, but if it never knows when to stop, it wouldn’t matter. Imagine if you successfully managed to get out of the woods and reached civilization, but you kept wandering back into the woods because you didn’t know you were back to safety.

Most of the problems you worked with so far have explicit goals. You know what the solution should look like, so you know exactly when to stop. Unfortunately, as you saw with the cargo problem, you’ll almost never have all of the information you need. One of the challenges is trying to determine when to stop your evolution and return a solution. The goal is to produce the best solution possible, even when you don’t know that it’s the absolute best.

In this section, you’ll learn three basic techniques for defining termination criteria. Of course, you may find it beneficial to define termination criteria specific to your problem; however, these techniques will work for a majority of the problems you encounter.

Stopping Evolution at a Fitness Threshold

Stopping when your population has reached a certain fitness threshold is the most straightforward approach to terminating your algorithms. This approach is common when you either know what the solution is supposed to be or you’ve been given specific success criteria.

In the first few chapters, you worked with a maximum fitness threshold — you terminated when the best solution reached a target fitness. You can also terminate your algorithms at a minimum fitness, or even an average fitness. For example, in portfolio optimization, you might want to create a number of possible portfolios that meet an average threshold of success — in this case, you would check the population’s average fitness and return when it meets some threshold.

You can apply these techniques to the One-Max problem. Open lib/one_max.exs and experiment with the following termination criteria:

​ ​defmodule​ OneMax ​do​
​   ​# ...Genotype/Fitness Function defined...​
​ 
​   ​# Maximum Fitness Threshold​
​   ​def​ terminate?(population), ​do​:
​     Enum.max_by(population, &OneMax.fitness_function/1) == 42
​ 
​   ​# Minimum Fitness Threshold​
​   ​def​ terminate?(population), ​do​:
​     Enum.min_by(population, &OneMax.fitness_function/1) == 0
​ 
​   ​# Average Fitness Threshold​
​   ​def​ terminate?(population) ​do​
​     avg =
​       population
​       |> Enum.map(&(Enum.sum(&1) / length(&1)))
​     avg == 21
​   ​end​
​ ​end​

Each of these termination criteria will return different solutions. The first will stop when the best chromosome possible is found, the second will stop when the worst chromosome possible is found, and the last will stop when the average chromosome is found.

Fitness-based termination criteria is the most straightforward to implement; however, it’s difficult to come across a problem where you’re certain about when to stop.

Stopping Evolution after n Generations

Another method for designating termination criteria is to stop after your algorithm has run for a sufficiently long time. With this approach, you need to determine what “sufficiently long” means. The beauty of this approach is the ability to experiment with different numbers of generations. You may initially believe your algorithm will converge after 10,000 generations, only to find it continues to improve after 20,000 generations.

Another benefit of this method is its relative simplicity. To implement it, all you have to do is keep track of the current generation. Open lib/genetic.ex and alter the evolve function to track a generation parameter, like this:

​ ​def​ run(problem, opts \\ []) ​do​
​   population = initialize(&problem.genotype/0, opts)
​   first_generation = 0
​ 
​   population
​   |> evolve(problem, first_generation, opts)
​ ​end​
»​def​ evolve(population, problem, generation, opts \\ []) ​do​
​   ​# ...​
»  ​if​ problem.terminate?(population, generation) ​do​
​     ​# ...​
​   ​else​
»    generation = generation + 1
​     ...
​     |> evolve(problem, generation opts)
​   ​end​
​ ​end​

Next, you’ll need to slightly modify the Problem behaviour, so the terminate? function expects two parameters rather than one. Open the lib/problem.ex file and change the terminate? callback to this:

​ @callback terminate?(Enum.t(), integer()) :: boolean()

Now, all you’ll need to do is specify a generation stopping point in one of your genetic algorithms. Try it with lib/one_max.exs, like this:

​ ​def​ terminate?(population, generation), ​do​: generation == 100

Generation Tracking

INFORMATION

For the remainder of this book, this is what your terminate? callback should look like. You’ll see another termination method next, but you’ll only ever use generation-based or fitness-based termination.

When you run this script on the cargo problem, notice how sometimes the algorithm converges on an optimal solution and sometimes it doesn’t:

​ ​$ ​​mix​​ ​​run​​ ​​scripts/cargo.exs​
​ Current Best: 30
​ %Types.Chromosome{
​   age: 1,
​   fitness: 30,
​   genes: [0, 1, 0, 1, 1, 1, 1, 0, 0, 0],
​   size: 10
​ }
​ 
​ Weight is: 39

​ ​$ ​​mix​​ ​​run​​ ​​scripts/cargo.exs​
​ Current Best: 35
​ %Types.Chromosome{
​   age: 1,
​   fitness: 35,
​   genes: [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
​   size: 10
​ }
​ 
​ Weight is: 38

This is the tradeoff with this approach — sometimes you get lucky and sometimes you don’t. You could experiment with different generation thresholds, but that can be time consuming. After awhile, you’ll find your algorithms will continue to converge to the same value after a certain number of generations.

Stopping Evolution with No Improvements

A more sophisticated technique for determining when to stop is by tracking how long it’s been since your algorithm has improved and stopping when progress has stalled. Implementing the tracking necessary for this can be a little tricky; however, it can pay off because it automatically determines when the algorithm has converged.

The simplest way to stop based on changes in fitness is by using a temperature. Temperature tells you how hot or cold an algorithm is. Algorithms that are hot are making significant improvements between generations. Algorithms that are cold haven’t made improvements in a long time.

Temperature

INFORMATION

You might recognize the term temperature from another optimization technique known as simulated annealing. Typically, temperature is a parameter that controls some of the movement in that algorithm; however, it’s also useful in genetic algorithms for measuring when to stop. You may not want to refer to the measure of progress in the algorithm as temperature — you can also call it momentum or something else that makes sense to you.

To measure the temperature of your algorithm, you’ll need to alter run/2 to track changes in fitness between generations. To accomplish this, open lib/genetic.ex and add the following changes:

​ ​def​ run(problem, opts \\ []) ​do​
​   population = initialize(&problem.genotype/0, opts)
​   population
»  |> evolve(problem, 0, 0, 0, opts)
​ ​end​
​ ​def​ evolve(problem, generation, last_max_fitness, temperature, opts) ​do​
​   ...
​   best = Enum.max_by(population, &problem.fitness_function/1)
​   best_fitness = best.fitness
»  temperature = 0.8 * (temperature + (best_fitness - last_max_fitness))
»  ​if​ terminate?(population, generation, temperature) ​do​
​     ...
​   ​else​
​     ...
»    |> evolve(problem, generation, best_fitness, temperature, opts)
​   ​end​
​ ​end​

As with tracking generations, you’ll need to change the terminate? callback in the Problem behaviour to reflect the additional parameter.

One thing you’ll see here is that the temperature is calculated by multiplying the sum of the old temperature and the change in maximum fitness by a factor of 0.8. You don’t have to use 0.8. In fact, you may want to take an additional parameter, known as a cooling rate, which determines how fast the temperature lowers. Your formula would then look like this: (1 — cooling_rate) * (temperature + (best — last_max_fitness)). A higher cooling rate means your algorithms will terminate faster.

To see the temperature strategy in action, open lib/one_max.exs and adjust the termination criteria like this:

​ ​def​ terminate?(population, generation, temperature), ​do​: temperature < 25

This example stops when the temperature is less than 25. This technique is useful because it allows you to determine when an algorithm has converged automatically. The temperature will automatically decrease when there’s no progress being made. You can play around with different cooling rates and temperature thresholds to see which works best for you.

👈 Applying a Penalty to the Shipping Problem | TOC | Applying Termination Criteria to Shipping 👉

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.