Introducing the One-Max Problem

Summary

The web content introduces the One-Max problem as a simple example to demonstrate the concept of genetic algorithms, particularly within the context of Elixir programming, and provides initial steps for setting up a genetic algorithm project.

Abstract

The One-Max problem, a classic introductory example for genetic algorithms, is presented as a straightforward optimization problem where the goal is to maximize the sum of a bitstring of length N. While the solution is intuitive (a bitstring of all 1s), the challenge lies in finding this optimal string without exhaustively searching through all 2^N possible combinations, which becomes infeasible for large N. To address this, the article guides readers through creating a genetic algorithm in Elixir, starting with setting up directories and files in a Unix environment. The genetic algorithm is described as a process that iteratively transforms a population of chromosomes (potential solutions) over generations, aiming to evolve towards an optimal solution. The article emphasizes the practical application of genetic algorithms by following a structured approach that mirrors the algorithmic steps, and it concludes by inviting readers to report any code errors or formatting mistakes.

Opinions

The One-Max problem is considered an excellent tool for introducing the fundamental concepts of genetic algorithms due to its simplicity.
Brute-force search methods are deemed impractical for large bitstrings, necessitating more efficient optimization techniques like genetic algorithms.
The article positions genetic algorithms as a method to significantly reduce the search space and computational effort in optimization problems.
The use of Elixir as the programming language for implementing the genetic algorithm is endorsed, suggesting its suitability for such tasks.
Readers are encouraged to engage with the content interactively by following along with the Unix commands and coding examples provided.
The article promotes the book "Genetic Algorithms in Elixir" by Sean Moriarity, implying its value as a resource for learning about genetic algorithms in the context of Elixir programming.
A cost-effective AI service, ZAI.chat, is recommended as an alternative to ChatGPT Plus (GPT-4), indicating a preference for more affordable AI solutions.

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

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

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.

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.