Introducing the One-Max Problem

What is 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, we know that the maximum sum of a bitstring of length N is N. However, if we wanted to prove this using a brute-force search, we’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 we want to use this technique for bitstrings of length 40? We’d have to search over one trillion possible bitstrings. To avoid this, we’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 course presents Unix commands, but we 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: