Search⌘ K
AI Features
Home
Courses
Genetic Algorithms in Elixir

Treating Chromosomes as Processes

Explore how to transform chromosomes into concurrent processes using Elixir's Agent module to enable parallel evaluation and mutation in genetic algorithms. This lesson guides you through implementing agents for chromosomes, updating the genetic algorithm framework to work with mutable process states, and understanding the trade-offs of parallelism in algorithm optimization.

We'll cover the following...

Creating the Agent module

The strongest aspect of the BEAM is its ability to create and work with processes. We saw how easy it was to spin up new processes using the Task module in the last lesson. In this lesson, we’ll use the Agent module to accomplish parallelization in a different manner.

An Agent is an abstraction around the state. Agents allow us to keep track of state between entities. In the original genetic algorithm framework, you perform transformations on Chromosome structs. Using an Agent, we can replace these transformations with interactions between processes. These processes will naturally run in parallel, and our algorithms will achieve parallelism naturally.

Note: You probably won’t see significant performance increases using this approach on normal machines. Using this approach in practice requires a massively parallel system to be viable. It also requires some additional complexities to implement correctly.

In this lesson, we’ll implement a basic agent and see how to evaluate a population of agents.

Basic agent implementation

Start by opening chromosome.ex in types. At the top of the file, add the following line:

use Agent

This line tells Elixir that we’ll be implementing the Agent behaviour. Next, we need to implement some functions for interacting with the Agent. Add the following to chromosome.ex:

C++
def start_link(chromosome) do
  Agent.start_link(fn -> chromosome end)
end
def get_fitness(pid) do
  Agent.get(pid, & &1.fitness)
end
def eval(pid, fitness) do
  Agent.update(pid, fn c -> %Chromosome{c | fitness: fitness.(c)} end)
end

Here, implement three functions start_link/1, get_fitness/1, and eval/2. start_link/1 at lines 1-3 returns a chromosome. The get_fitness/1 function returns fitness for use in evaluate/1 at lines 5-7. eval/2 evaluates a Chromosome given a fitness function at lines 9-12. We’ll use this function to evaluate chromosomes in parallel.

The previous implementations in genetic.ex assumed our algorithm worked on immutable populations of Chromosomes. That meant that after each generation we returned an entirely new population object. In this example, our algorithm will work on mutable agents. After each generation we will return the same population object; however, we will update the process state which is associated with each chromosome in our population. We’ll need to tweak parts of your algorithm to work with the new Agent abstraction.

First, edit the initialize/2 and evaluate/3 functions in genetic.ex to match the following:

C++
def initialize(genotype, opts \\ []) do
  population_size = Keyword.get(opts, :population_size, 100)
  for _ <- 1..population_size do
    {:ok, chromosome} = Chromosome.start_link(genotype.())
    chromosome
  end
end
def evaluate(population, fitness_function, _opts \\ []) do
  population
  |> Enum.map(&Chromosome.eval(&1, fitness_function))
  population
  |> Enum.sort_by(fn c -> Chromosome.get_fitness(c) end, &>=/2)
end

Notice that instead of simply calling genotype to return a new Chromosome at line 4, we need to spin up a new process which contains a new Chromosome as a state. In evaluate/3, we can’t just directly call c.fitness. Instead, we need to use the Chromosome.get_fitness/1 wrapper at line 14 which accesses the fitness property of the Chromosome associated with the process c.

Note: For simplicity, in this example, evaluate doesn’t update the age of a chromosome.

Next, change crossover/2 and mutation/2 to look like this:

C++
def crossover(population, opts \\ []) do
  crossover_fn = Keyword.get(opts, :crossover_type, &Toolbox.Crossover.single_point/2)
  population
  |> Enum.each(fn {p1, p2} ->
      {c1, c2} = apply(crossover_fn, [Agent.get(p1, & &1), Agent.get(p2, & &1)])
      Agent.update(p1, fn _ -> c1 end)
      Agent.update(p2, fn _ -> c2 end)
    end)
end
def mutation(population, opts \\ []) do
  mutate_fn = Keyword.get(opts, :mutation_type, &Toolbox.Mutation.scramble/1)
  rate = Keyword.get(opts, :mutation_rate, 0.05)
  population
  |> Enum.each(
      fn c ->
        if :rand.uniform() <= rate do
          mutant = apply(mutate_fn, [Agent.get(c, & &1)])
          Agent.update(c, fn _ -> mutant end)
        end
        c
      end
    )
end

Previously, crossover/2 and mutation/2 returned new lists of Chromosome objects and relied on reinsertion strategies to combine children, parents, and mutants. In this example, we use a sort of pure reinsertion where each child directly replaces its parent chromosome. Agent.update/2 at lines 6-7 and at line 19 updates the state associated with the given process by calling the given function. In this example, our function always returns a new Chromosome, so the process’s original state is overridden. Rather than use Enum.map and Enum.reduce which return an updated population, we can use Enum.each at line 4 and line 15 which assumes the given function is side-effecting and discards the original input object.

While this example uses a pure reinsertion strategy, an alternative approach could spin up new processes with Agent.start_link/2, and kill old ones with Agent.stop/4 during reinsertion. Agent.stop/4 is synchronous, so we’d want to use it as a cleanup routine before transitioning to the next generation.

Finally, we need to change evolve/4 to work with your new mutable implementations:

C++
def evolve(population, problem, generation, opts \\ []) do
  population = evaluate(population, &problem.fitness_function/1, opts)
  best = hd(population)
  IO.write("\rCurrent best: #{Chromosome.get_fitness(best)}\tGeneration: #{generation}")
  if problem.terminate?(population, generation) do
    Agent.get(best, & &1)
  else
    {parents, _} = select(population, opts)
    crossover(parents, opts)
    mutation(population, opts)
    evolve(population, problem, generation+1, opts)
  end
end

In this example, we can completely remove reinsertion steps. Additionally, rather than accepting an updated population at each step, our crossover, mutation, and evolve functions at lines 9-11 accept the same population objects and assume they are mutated in the previous steps. Finally, because each Chromosome in the population is actually a process, we need to change some calls to access the process state. Rather than accessing the fitness property of best, we need to use the Chromosome.get_fitness/1 property at line 4. Additionally, to ensure the algorithm actually returns a Chromosome, we need to use Agent.get/2 at the end at line 6.

Now, we need to make some slight alterations to the original problem solutions to ensure they work well with the new Agent based implementations. In order to run scripts/one_max.exs, we need to change the termination criteria to look like:

@impl true
def terminate?(population, _generation), do: Chromosome.get_fitness(hd(population)) == 42

Testing the results

Now, we can finally test this out using the following application:

defmodule Genetic do
  alias Types.Chromosome

  def initialize(genotype, opts \\ []) do
    population_size = Keyword.get(opts, :population_size, 100)
    for _ <- 1..population_size do
      {:ok, chromosome} = Chromosome.start_link(genotype.())
      chromosome
    end
  end

  def evaluate(population, fitness_function, _opts \\ []) do
    population
    |> Enum.map(&Chromosome.eval(&1, fitness_function))

    population
    |> Enum.sort_by(fn c -> Chromosome.get_fitness(c) end, &>=/2)
  end

  def select(population, opts \\ []) do
    select_fn = Keyword.get(opts, :selection_type, &Toolbox.Selection.elite/2)
    select_rate = Keyword.get(opts, :selection_rate, 0.8)
    n = floor(length(population) * select_rate)
    n = if rem(n, 2) == 0, do: n, else: n+1
    parents =
      select_fn
      |> apply([population, n])
    leftover = MapSet.difference(MapSet.new(population), MapSet.new(parents))
    parents =
      parents
      |> Enum.chunk_every(2)
      |> Enum.map(& List.to_tuple(&1))
    {parents, MapSet.to_list(leftover)}
  end

  def crossover(population, opts \\ []) do
    crossover_fn = Keyword.get(opts, :crossover_type, &Toolbox.Crossover.single_point/2)
    population
    |> Enum.each(fn {p1, p2} ->
        {c1, c2} = apply(crossover_fn, [Agent.get(p1, & &1), Agent.get(p2, & &1)])
        Agent.update(p1, fn _ -> c1 end)
        Agent.update(p2, fn _ -> c2 end)
      end)
  end

  def mutation(population, opts \\ []) do
    mutate_fn = Keyword.get(opts, :mutation_type, &Toolbox.Mutation.scramble/1)
    rate = Keyword.get(opts, :mutation_rate, 0.05)
    population
    |> Enum.each(
        fn c ->
          if :rand.uniform() <= rate do
            mutant = apply(mutate_fn, [Agent.get(c, & &1)])
            Agent.update(c, fn _ -> mutant end)
          end
          c
        end
      )
  end

  def run(problem, opts \\ []) do
    population = initialize(&problem.genotype/0)
    population
    |> evolve(problem, 0, opts)
  end

  def evolve(population, problem, generation, opts \\ []) do
    population = evaluate(population, &problem.fitness_function/1, opts)
    best = hd(population)
    IO.write("\rCurrent best: #{Chromosome.get_fitness(best)}\tGeneration: #{generation}")
    if problem.terminate?(population, generation) do
      Agent.get(best, & &1)
    else
      {parents, _} = select(population, opts)
      crossover(parents, opts)
      mutation(population, opts)
      evolve(population, problem, generation+1, opts)
    end
  end
end
Using Agent to run the genetic algorithm

This approach follows similar approaches taken in evolutionary-based algorithms written in Erlang, but it’s not necessary for the situations we will encounter.