Introducing the One-Max Problem

The One-Max problem is a trivial problem often used to introduce the concept of genetic algorithms. It’s incredibly simple, but it’s great for introducing many of the critical aspects of a genetic algorithm. The problem boils down to one question: what is the maximum sum of a bitstring (a string consisting of only 1s and 0s) of length N?

Of course, you know that the maximum sum of a bitstring of length N is N. However, if you wanted to prove this using a brute-force search, you’d end up needing to search through 2^N different solutions. As with any search problem, this isn’t too difficult with relatively small bitstrings. But what happens if you want to use this technique for bitstrings of length 40? You’d have to search over one trillion possible bitstrings. To avoid this, you’ll create a genetic algorithm that produces an optimal solution without iterating over every possible solution in the search space.

To get started, open a terminal or command prompt. This book presents Unix commands, but you won’t need to do anything more difficult than create files and directories or work with Elixir and Mix. With a terminal open, run the following commands:

This creates a new directory named genetic and a directory within that directory named scripts. It then creates a file within scripts titled one_max.exs. The one_max.exs is where you’ll write your genetic algorithm.

Genetic algorithms work via transformations on populations of chromosomes over some number of generations. Imagine you’re playing a card game where your goal is to get the highest possible card after some number of turns. You are initially given five cards and you can choose to keep any number of cards at the end of every turn.

In this example, a single card is a chromosome. It represents one solution to your problem. Your entire hand is the population; it’s a collection of possible solutions. The changes you make to your hand after every turn are transformations. Finally, every turn represents one generation—one transformation of the population.

The figure illustrates the basic structure of a genetic algorithm.

Each step depicted in the image performs a transformation on the population that brings you closer to finding a solution. The process is repeated until a solution is found.

Most genetic algorithms follow a structure similar to the one in the figure, which is easily translated into equally structured code. Your genetic algorithm will also follow these same steps—with code that mirrors each step in the process.