Using Behaviours to Model Problems

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

👈 Using Structs to Represent Chromosomes | TOC | Understanding and Choosing Genotypes 👉

Recall that one technique to solving problems is to transform them into a form you already understand. While every problem seems different, and on the surface may require different techniques to solve, they almost always have patterns and similarities between them. This is especially true with the problems you’ll solve with genetic algorithms.

The framework you built in Chapter 2, ​Breaking Down Genetic Algorithms​, separates a few problem-specific parameters from the common aspects of a genetic algorithm. These parameters are a fitness function, a genotype, and termination criteria. This means that every problem you attempt to solve using a genetic algorithm must implement all three of these functions — the nature of the framework creates a natural abstraction for problems.

An abstraction is a simplification of underlying complexities and implementations. The purpose of abstraction is to force you to think of things at different levels of specificity. It gives you an idea of what to look for before you approach a problem. This is especially useful when approaching new problems with genetic algorithms. When you want to approach a new problem, you already know that you need a fitness function, or a way to measure success; a genotype, or a way to represent solutions; and some termination criteria, or a way to tell the algorithm when to stop. While the specifics are the difficult part, you’re never starting from scratch with this abstraction in place.

Unfortunately, Elixir doesn’t feature abstract classes, interfaces, or traits like other object-oriented languages. Instead, you can implement abstraction using behaviours.

Mind the “u”

IMPORTANT

Elixir uses the British spelling of “behaviour.”

Behaviours Are a Contract

In much the same way that interfaces enforce a specification in object-oriented languages, behaviours enforce specifications in Elixir.

A behaviour is a contract — a means of defining what you want with specifications and ensuring that any module that implements a behaviour does the same. With a behaviour, you can define functions that a module must implement to be valid.

Behaviours consist of a number of callbacks. Callbacks are function signatures with an accompanying return type. Callbacks indicate what functions behaviours must implement, with guidelines on what they take and what they return.

A callback looks something like this:

​ @callback function_name(parameter_type, parameter_type, ...) :: return_type

To define a behaviour, you define a series of callbacks within a module. A behaviour looks like this:

​ ​defmodule​ Behaviour ​do​
​ 
​   @callback function1(String.t) :: {​:ok​, String.t}
​   @callback function2(List.t) :: {​:ok​, List.t} | {​:error​, String.t}
​ 
​ ​end​

You would then adopt a behaviour, like so:

​ ​defmodule​ Adopt ​do​
​   @behaviour Behaviour
​ 
​   @impl Behaviour
​   ​def​ function1(string), ​do​: {​:ok​, string}
​ 
​   @impl Behaviour
​   ​def​ function2(list) ​do​
​     ​case​ list ​do​
​       nil -> {​:error​, ​"​​Can't be nil!"​}
​       _   -> {​:ok​, list}
​     ​end​
​   ​end​
​ ​end​

Behaviours are relatively straightforward to implement. You define a module that contains a series of callbacks. Defining a behaviour is the same as defining an outline for a module which adopts that behaviour. When adopting a behaviour, you simply enumerate the name of the behaviour, followed by implementations of the required callbacks.

Note that the @impl keyword is not necessarily required; however, it does generate useful warnings when your functions don’t do what they’re specified to do.

You’ll use behaviours to define a contract for the problems you want to solve using genetic algorithms. The problem behaviour will ensure that the problem-specific parts of your genetic algorithm are implemented correctly and are seamlessly integrated with the framework you designed earlier in Chapter 2, ​Breaking Down Genetic Algorithms​.

Creating the Problem Behaviour

To get started writing your behaviour, create a new file within the lib directory named problem.ex.

Now, open the problem.ex file and add a new module named Problem, like this:

​ ​defmodule​ Problem ​do​
​   alias Types.Chromosome
​ ​end​

This is a barebones module that contains an alias for the Chromosome module you created in the previous section. The alias makes accessing the Chromosome module easier later on.

At this point, it’s time to start thinking about what a problem consists of. Remember, you need to define callbacks that modules adopting the Problem behaviour will need to implement. In the previous chapter, the problem-specific functions were a fitness function and a genotype function, which is a good place to start.

Think about what each of these functions took as input and what they needed to do. The genotype function didn’t require any input. All it needed to do was return an enumerable which represented a single chromosome. In this chapter, you created a chromosome type that works in place of the original representation of a chromosome. Therefore, all the function needs to do is return a chromosome.

Your genotype callback will look like this:

​ @callback genotype :: Chromosome.t

Chromosome.t is the custom type you built in the previous section. This means that genotype/0 must return a chromosome struct.

The next function a problem needs is a fitness function. Remember, a fitness function assesses the fitness of a single chromosome and returns some sort of fitness value. In practice, a fitness function can return any value, so long as the value can be sorted in some way. In this book, you’ll only create fitness functions that return positive or negative numbers, so you can simplify the callback to only return numbers. The callback will look like this:

​ @callback fitness_function(Chromosome.t) :: number()

The last problem-specific parameter you must implement is a termination criteria. In the previous chapter, this criteria was represented as a max fitness. This was sufficient for the One-Max problem; however, you won’t always be able to reach a specific fitness threshold. Sometimes you won’t even know what a solid threshold is. You’ll need more problem-specific termination criteria.

Most of the time, termination is determined based on information about the population or after a maximum number of steps. In Chapter 4, ​Evaluating Solutions and Populations​, you’ll learn more about termination criteria. What you need to define at this point is a function that analyzes the population and tells your framework whether to continue evolving or to cease and return the best solution. This function should take an enumerable representing the population and return a Boolean indicating whether the evolution should stop or continue.

Something like this will work:

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

The function terminate?/1 takes in a population and returns a Boolean — false means continue evolving and true means stop and return. The question-mark at the end is common to Boolean functions in Elixir.

The problem behaviour will now look like this:

​ ​defmodule​ Problem ​do​
​   alias Types.Chromosome
​ 
​   @callback genotype :: Chromosome.t
​ 
​   @callback fitness_function(Chromosome.t) :: number()
​ 
​   @callback terminate?(Enum.t) :: boolean()
​ 
​ ​end​

This module represents a contract you can use for all of the problems you want to solve using a genetic algorithm. It provides a very simple abstraction from which to start — implementing specifics is difficult, but you know exactly what you need to implement with each problem.

Adjusting the Framework

To insert the Problem behaviour into your framework, you’ll need to make a few minor adjustments. Additionally, you’ll need to make some changes to account for your new chromosome struct.

First, open the genetic.ex file and add the following at the top:

​ alias Types.Chromosome

The alias is necessary to easily access the chromosome struct.

Next, locate the run and evolve functions you defined in the previous chapter, and change them to look like this:

​ ​def​ run(problem, opts \\ []) ​do​
​   ...
​ ​end​
​ ​def​ evolve(population, problem, opts \\ []) ​do​
​   ...
​ ​end​

Now you need to reference the functions specific to the problem behaviour rather than those passed in as parameters. Change the body of the run and evolve functions to look like this:

​ ​def​ run(problem, opts \\ []) ​do​
»  population = initialize(&problem.genotype/0)
​   population
»  |> evolve(problem, opts)
​ ​end​
​ ​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​

Notice that all the references to parameters have been changed to references to the corresponding function in the problem parameter. This is because the termination criteria depends on the population of chromosomes already having an associated fitness. All of the other code is the same.

The next change you need to make is to ensure you’re constantly updating your chromosome structs with new ages and fitnesses as you transition between generations. You can do this in the evaluate function. Change it to look like this:

​ ​def​ evaluate(population, fitness_function, opts \\ []) ​do​
​   population
»  |> Enum.map(
»      ​fn​ chromosome ->
»        fitness = fitness_function.(chromosome)
»        age = chromosome.age + 1
»        %Chromosome{chromosome | ​fitness:​ fitness, ​age:​ age}
»      ​end​
»    )
​   |> Enum.sort_by(& &1.fitness, &>=/2)
​ ​end​

Finally, you need to adjust the crossover and mutation functions so they work correctly with your chromosome type. Change your functions to look like this:

​ ​def​ crossover(population, opts \\ []) ​do​
​   population
​   |> Enum.reduce([],
​       ​fn​ {p1, p2}, acc ->
»        cx_point = ​:rand​.uniform(length(p1.genes))
​         {{h1, t1}, {h2, t2}} =
»          {Enum.split(p1.genes, cx_point),
»            Enum.split(p2.genes, cx_point)}
​         {c1, c2} =
»          {%Chromosome{p1 | ​genes:​ h1 ++ t2},
»            %Chromosome{p2 | ​genes:​ h2 ++ t1}}
​         [c1, c2 | acc]
​       ​end​
​     )
​ ​end​
​ 
​ ​def​ mutation(population, opts \\ []) ​do​
​   population
​   |> Enum.map(
​       ​fn​ chromosome ->
​         ​if​ ​:rand​.uniform() < 0.05 ​do​
»          %Chromosome{chromosome | ​genes:​ Enum.shuffle(chromosome.genes)}
​         ​else​
​           chromosome
​         ​end​
​       ​end​
​     )
​ ​end​

Notice how these functions now return new chromosomes as well as reference the genes of old chromosomes rather than working on the chromosomes directly with Enum. This will give you access to the fields you define for the Chromosome struct, such as age, fitness, and size.

With these minor adjustments, your framework is now completely compatible with the work you did in this chapter.

👈 Using Structs to Represent Chromosomes | TOC | Understanding and Choosing Genotypes 👉

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.