Genetic algorithms in Elixir - Chapter 1

The One Max problem

A basic introduction to genetic algorithms can be had by working through the solution of the one max problem. The problem to be solved is to find the largest binary number that can be represented with a binary string, e.g for a string of length 4, the solution is 1111.

Overview

The general set of steps to solve a problem using genetic algorithms is as follows:

1. Generate an initial population of solutions
2. Evaluate the solutions (chromosomes) and sort the population accordingly
3. Pair up the adjacent solutions as parents
4. Create a new set of solutions by combining each set of parent solutions
5. Randomly alter a small subset of your population to avoid premature convergence (mutation)

Example implementation

Step 1: Generating the initial population

init_population = for _ <- 1..100, do: for(_ <- 1..1000, do: Enum.random(0..1))

Step 2: Evaluate the population and sort accordingly

evaluate = fn population ->
  Enum.sort_by(population, &Enum.sum/1, &>=/2)
end

Step 3: Select parents

selection = fn population ->
  population
  |> Enum.chunk_every(2)
  |> Enum.map(&List.to_tuple(&1))
end

Step 4: Combine parents’ solutions to form new child solutions

crossover = fn population ->
  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

Step 5: Mutate a small portion of the population

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

Put it all together:

algorithm = fn population, algorithm ->
  # IO.inspect(population)
  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.()
    |> mutation.()
    # Repeat the Process with new Population
    |> algorithm.(algorithm)
  end
end

solution = algorithm.(init_population, algorithm)
# IO.write("\n Answer is \n")
# IO.inspect(solution)