Looking Deeper into Genetic Algorithms

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

👈 Reviewing Genetic Algorithms | TOC | Using Mix to Write Genetic Algorithms 👉

Based on what you’ve learned so far, you should understand that every genetic algorithm follows the same basic steps. While different algorithms for different problems may use different techniques, probabilities, or strategies, they all share the same structure. As a programmer, you want to take advantage of this.

One of the golden rules of programming is Don’t Repeat Yourself (DRY), which essentially boils down to not rewriting unnecessary code. You can exploit the shared structure of genetic algorithms to avoid rewriting code that remains the same from algorithm to algorithm. Unfortunately, you have to start from scratch.

So how do you go about designing a versatile framework from the ground up? Start with the basics. All genetic algorithms follow the same structure. They all use chromosomes and populations, and they all require similar inputs. You can use this to your advantage and begin designing from the ground up.

Chromosomes and Populations

Chromosomes represent solutions to problems. In the One-Max problem, your solutions consisted of a series of 1s and 0s; however, that won’t be the case for every problem. Some problems are encoded using real values, some as permutations, and some using characters. Also, some problems require that you use a data structure other than a list to encode solutions.

All of this means that specific encoding schemes are unique and vary from problem to problem. To ensure your framework is as general as possible and works for all of your encoding schemes, you can use the Enumerable protocol.

In Elixir, protocols allow you to implement polymorphism within your libraries. Data structures that implement the Enumerable protocol can be passed into any function within the Enum library. That means you can encode your chromosomes using any data structure that implements Enumerable — even ones you build yourself.

A population, on the other hand, is simply a collection of chromosomes. The following image demonstrates the difference between a chromosome and a population:

For the most part, how you encode a population won’t change — as long as the population is a series of chromosomes, it doesn’t matter what data structure you use. For simplicity, this book uses lists to contain chromosomes.

Also, the size of your population doesn’t matter. Bigger populations take longer to transform, but they may converge on a solution faster, whereas smaller populations are easier to transform, but they may take longer to converge.

Based on what you know now, you can begin to define some rules your framework must enforce, such as:

• To use polymorphism, you must encode chromosomes using a data structure that implements the Enumerable protocol.
• Because populations are stored as lists, you can use any function in the Enum or List library to implement transformations.
• Your algorithm should work on any population size.

By enforcing each of these rules, you’ll be able to expand your framework for a variety of problems.

Initializing the Population

The first step in every genetic algorithm is initializing a population. Typically, the first population is random — it’s like a shotgun blast onto the search space. The idea is to start out examining many different solutions and slowly work toward the best ones.

You’ve already determined that a population is a list, which means the function you implement for this step must return a list of chromosomes. But you need to ensure that your function can apply to all types of problems and doesn’t include specifics about how chromosomes are encoded. To do this, you can take a function that generates chromosomes as input.

Elixir allows you to pass functions as arguments to other functions. You can ensure one of the parameters is a function that produces a chromosome. You don’t care about the specifics of how this function is implemented; you only care that this function returns a chromosome.

With this step, you have two main goals:

• The initialization step must produce an initial population — a list of possible solutions.
• The function which initializes the population should be agnostic to how the chromosome is encoded. You can achieve this by accepting a function that returns a chromosome.

Evaluating the Population

The evaluation step is responsible for evaluating each chromosome based on some fitness function and sorting the population based on this fitness. This makes it easy to extract the best chromosome from the population. It also makes it easier to work with the population in the selection step.

Just like encoding schemes vary from problem to problem, so does fitness. Different problems require different measures of how good a solution is. If you were trying to find the shortest path between two points, you’d evaluate your solutions based on the distance of the path they produce. If you were trying to optimize a portfolio full of stocks, you’d evaluate the portfolio based on potential return. Essentially, you don’t care how the fitness function is implemented or even what it returns — you just need a measure that allows you to compare the fitness of each chromosome against the rest of the chromosomes in the population.

This leaves you with the following goals or requirements of the evaluation step:

• The evaluation step must take a population as input.
• The evaluation step must produce a population sorted by fitness.
• The function which evaluates the population should take a parameter that is a function that returns the fitness of each chromosome.
• The fitness function can return anything, as long as the fitness can be sorted.

Selecting Parents

With a sorted population, you can begin to select parents for reproduction. Remember, selection is responsible for matching parents that will produce strong children. Later on, you’ll implement different selection methods to achieve this effect. For now, the selection method should only pair adjacent chromosomes in the population. Because the population is sorted, the strongest chromosomes will reproduce with other strong chromosomes. This is referred to as elitism selection.

One additional goal of the selection function is to make it easy for the crossover function to transform the population into a new population. You can do this by transforming the population of chromosomes into tuples — as you did in the previous chapter.

Therefore, the rules for selection are:

• The selection step must take a population as input.
• The selection step must produce a transformed population that’s easy to work with during crossover — say by returning a list of tuples which are pairs of parents.

Creating Children

Remember that crossover is analogous to reproduction. The goal of crossover is to exploit the strengths of current solutions to find new, better solutions. Crossover is one of the last steps before starting a new generation and should create a population that looks and feels identical to the one you started with — albeit with new solutions.

In Chapter 6, ​Generating New Solutions​, you’ll learn a variety of crossover methods to use in different circumstances. Remember from the last step that the transformed population is a list of tuples, which are pairs of adjacent parents. You need to take these parents and transform the population into a brand-new population.

This image might help you understand this step better:

Notice how you combine each pair of parents to create a new pair of children. After this step, you should be left with a population that is identical in size to your original one.

With that in mind, the crossover step should:

• Take a list of 2-tuples as input.
• Combine the 2-tuples, which represent pairs of parents. For now, use single-point crossover.
• Return a population identical in size to the initial population.

Creating Mutants

Mutation is the last step before the next generation. Remember, the goal of mutation is to prevent premature convergence by transforming some of the chromosomes in the population. There are a number of mutation strategies. For now, you can keep your mutation function the same as the one you used in Chapter 1, ​Writing Your First Genetic Algorithm​. In Chapter 7, ​Preventing Premature Convergence​, we’ll introduce other types of mutation functions. The mutation rate should be kept relatively low — typically somewhere around 5%.

So what can you gather from this?

• The mutation step should accept a population as input.
• The mutation step should mutate only some of the chromosomes in the population — the percentage should be relatively small.
• The mutation strategy should be identical to the mutation function from the previous chapter.

Termination Criteria

In Chapter 1, ​Writing Your First Genetic Algorithm​, you told your genetic algorithm to stop when the solution reached a maximum. Will you always know the maximum? Is there always a maximum? What if your algorithm can never achieve a maximum? Do you want it to run forever?

You can gather from this that termination criteria vary from problem to problem. Sometimes you know the answer; you just need to get there. Other times you want to see how good you can get your population, but you don’t want to waste time evolving over millions of generations. You’ll learn various termination criteria in Chapter 4, ​Evaluating Solutions and Populations​. What you need to know right now is that termination criteria are defined by the problem you’re working with.

What does this mean? It means you need to accept some kind of termination criteria. To keep things simple, assume that you’re only ever working with the One-Max problem with strictly positive, integer fitnesses. When does the One-Max problem terminate? When the maximum is found.

What rules can you generate from this?

• Termination criteria must be defined by the problem — the framework must accept some problem-defined criteria to stop the algorithm.
• Termination criteria, for now, must be just an integer — the maximum value needed to stop evolution.

👈 Reviewing Genetic Algorithms | TOC | Using Mix to Write Genetic Algorithms 👉

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.