Introducing the One-Max Problem

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

👈 Understanding Genetic Algorithms | TOC | Initializing the Population 👉

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:

​ ​$ ​​mkdir​​ ​​genetic​​ ​​&&​​ ​​mkdir​​ ​​genetic/scripts​
​ ​$ ​​cd​​ ​​genetic/scripts​
​ ​$ ​​touch​​ ​​one_max.exs​