Looking Deeper into Genetic Algorithms

The genetic algorithm structure

Based on what we’ve learned so far, we can understand that every genetic algorithm follows the same basic steps. While algorithms for different problems may use different techniques, probabilities, or strategies, they all share the same structure. As programmers, we 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. We can exploit the shared structure of genetic algorithms to avoid rewriting code that remains the same from algorithm to algorithm. Unfortunately, we have to start from scratch.

So how do we 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. We can use this to our advantage and begin designing from the ground up.

Chromosomes and populations

Chromosomes represent solutions to problems. In the One-Max problem, our solutions consisted of a series of ones and zeroes. 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 us to 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. We can use the Enumerable protocol to ensure the framework is as general as possible and works for all of the encoding schemes.

In Elixir, protocols allow us to implement polymorphism within our libraries. Data structures that implement the Enumerable protocol can be passed into any function within the Enum library. That means we can encode our chromosomes using any data structure that implements Enumerable — even ones that are self-built.

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