One-Max Problem

Mix.install([
  {:axon, "~> 0.6.1"},
  {:explorer, "~> 0.8.2"},
  {:kino_explorer, "~> 0.1.19"}
])

Introduction

The One-Max Problem is often used to introduce the concept of genetic algorithms. 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?

Genetic algorithms work via transformations on populations of chromosomes over some number of generations

The basic structure of a genetic algorithm can be visualized:

graph LR;
  A[Initialize Population]-->B;
  B[Evaluate Population]-->C;
  C[Select Parents]-->D;
  D[Create Children]-->E;
  E[Mutate Children]-->B;

where each step performs a transformation on the population that brings you closer to finding a solution

defmodule OneMax do
  def evolve(population) do
    best = Enum.max_by(population, &Enum.sum/1)
    IO.write("\rCurrent Best: " <> Integer.to_string(Enum.sum(best)))

    if Enum.sum(best) == 1000 do
      best
    else
      # Initial population
      population
      # Evaluate population
      |> evaluate()
      # Select parents
      |> selection()
      # Create children
      |> crossover()
      # Mutate population
      |> mutate()
      # Repeat process with new population
      |> evolve()
    end
  end

  def initialize_population(n, m) do
    for _ <- 1..n do
      for _ <- 1..m do
        Enum.random(0..1)
      end
    end
  end

  def evaluate(population) do
    Enum.sort_by(population, &amp;Enum.sum/1, &amp;>=/2)
  end

  def selection(population) do
    population
    |> Enum.chunk_every(2)
    |> Enum.map(&amp;List.to_tuple(&amp;1))
  end

  def crossover(population) do
    Enum.reduce(population, [], fn {p1, p2}, acc ->
      cx_point = :rand.uniform(1000)

      {{h1, t1}, {h2, t2}} =
        {Enum.split(p1, cx_point), Enum.split(p2, cx_point)}

      [h1 ++ t2, h2 ++ t1 | acc]
    end)
  end

  def mutate(population) do
    population
    |> Enum.map(fn chromosome ->
      if :rand.uniform() < 0.05 do
        Enum.shuffle(chromosome)
      else
        chromosome
      end
    end)
  end
end

{:module, OneMax, <<70, 79, 82, 49, 0, 0, 17, ...>>, {:mutate, 1}}

defmodule OneMaxNx do
  def evolve(population) do
    best = Enum.max_by(population, &Enum.sum/1)
    IO.write("\rCurrent Best: " <> Integer.to_string(Enum.sum(best)))

    if Enum.sum(best) == 1000 do
      best
    else
      # Initial population
      population
      # Evaluate population
      |> evaluate()
      # Select parents
      |> selection()
      # Create children
      |> crossover()
      # Mutate population
      |> mutate()
      # Repeat process with new population
      |> evolve()
    end
  end

  def initialize_population(n, m) do
    key = Nx.Random.key(42)
    {population, _new_key} = Nx.Random.randint(key, 0, 1, shape: {n, m}, type: :u32)
    population
  end

  def evaluate(population) do
    Enum.sort_by(population, &amp;Enum.sum/1, &amp;>=/2)
  end

  def selection(population) do
    population
    |> Enum.chunk_every(2)
    |> Enum.map(&amp;List.to_tuple(&amp;1))
  end

  def crossover(population) do
    Enum.reduce(population, [], fn {p1, p2}, acc ->
      cx_point = :rand.uniform(1000)

      {{h1, t1}, {h2, t2}} =
        {Enum.split(p1, cx_point), Enum.split(p2, cx_point)}

      [h1 ++ t2, h2 ++ t1 | acc]
    end)
  end

  def mutate(population) do
    population
    |> Enum.map(fn chromosome ->
      if :rand.uniform() < 0.05 do
        Enum.shuffle(chromosome)
      else
        chromosome
      end
    end)
  end
end

{:module, OneMaxNx, <<70, 79, 82, 49, 0, 0, 16, ...>>, {:mutate, 1}}

Understanding the Flow of Genetic Algorithms

# solution =
#   OneMax.initialize_population(100, 1000)
#   |> OneMax.evolve()

# IO.write("\n Answer is \n")
# IO.inspect(solution)

nil

OneMaxNx.initialize_population(100, 1000)

#Nx.Tensor<
  u32[100][1000]
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...],
    ...
  ]
>