Chapter 4 Evaluating Solutions and Populations

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

👈 What You Learned | TOC | Optimizing Cargo Loads 👉

Every problem has an objective. The goal of optimization is to maximize or minimize a value. The goal of search is to find a path to an objective. The common thread between optimization and search is an objective.

Your objective is your final destination — the end goal of your genetic algorithm. Sometimes, you might not know exactly what your end goal looks like, but you still need a way to know if you’re moving in the right direction. If you’ve ever played the game “Hot or Cold,” you understand what this looks like. You search for an object and somebody gives you clues to its location by telling you whether you’re “hot” — close to the object — or “cold” — further from the object. “Hot” and “cold” are basic assessments of your current location — they help you continue moving in the right direction without actually knowing where you’re going.

In genetic algorithms, fitness functions tell you how “hot” or “cold” you are. You use them as a barometer to measure your progress toward the best solution.

That’s why each new generation in a genetic algorithm starts with an evaluation of the current population. The evaluation step is crucial in ensuring your algorithm is progressing toward the best solution. In Chapter 2, ​Breaking Down Genetic Algorithms​, you defined the evolve/3 function in lib/genetic.ex. If you recall, that function looks like this:

​ ​def​ evolve(population, problem, opts \\ []) ​do​
​   population = evaluate(population, &problem.fitness_function/1, opts)
​   best = hd(population)
​   IO.write(​"​​\rCurrent best: ​​#{​best.fitness​}​​"​)
​   ​if​ problem.terminate?(population) ​do​
​     best
​   ​else​
​     population
​     |> select(opts)
​     |> crossover(opts)
​     |> mutation(opts)
​     |> evolve(problem, opts)
​   ​end​
​ ​end​

At two points in this code, the population is being evaluated. The first instance occurs in the first line of the function body, and looks like this:

​ population = evaluate(population, &problem.fitness_function/1, opts)

This line of code immediately transforms the population variable passed to the run/2 function by calling the evaluate/2 function to assess the population based on your problem-specific fitness function.

The next point of evaluation is a little less obvious. Take note of the if-condition, which determines when to stop an evolution and return the best solution. The condition calls problem.terminate?/1, which assesses the population based on some problem-specific parameter and decides whether or not to continue.

Fitness functions and termination criteria are two means of assessing solutions in a genetic algorithm. Fitness functions tell you how good a solution is. Termination criteria tells you when to stop the genetic algorithm and return the solution. More often than not, your termination criteria is tied to the best fitness in your population. Both fitness functions and termination criteria are equally important in creating an effective genetic algorithm to solve your problems.

In this chapter, you’ll start by examining a new kind of problem to illustrate the importance of crafting a good fitness function and to learn how to craft fitness functions using common techniques for different problems. Additionally, you’ll learn how to define termination criteria that stops your algorithms from searching and returns the best possible solutions.

👈 What You Learned | TOC | Optimizing Cargo Loads 👉

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.