Defining Termination Criteria

Importance of termination criteria

Next to a good fitness function, the termination criteria is the most important aspect of your genetic algorithms. If we don’t know when to stop and return a solution, we’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. We could write a perfect algorithm, but if it never knows when to stop, it wouldn’t matter. Most of the problems we have worked with so far have explicit goals. We know what the solution should look like, so we know exactly when to stop. Unfortunately, as we saw with the cargo problem, we’ll almost never have all of the information you need. One of the challenges is trying to determine when to stop our evolution and return a solution. The goal is to produce the best solution possible, even when we don’t know that it’s the absolute best.

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

Stopping evolution at a fitness threshold

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

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

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