Tracking Genealogy in a Genealogy Tree

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

👈 Logging Statistics Using ETS | TOC | What You Learned 👉

Sometimes, especially in evolutionary simulations, it’s useful to track the genealogy of the evolution. Genealogy is the study of families and family histories. In the context of genetic algorithms, genealogy is the history of a chromosome’s lineage. It allows you to trace the ancestry of a specific chromosome — all the way back to the initial population.

To track genealogy, you’ll take advantage of the libgraph[5] package. libgraph is an Elixir package for creating graph structures. libgraph offers a ton of convenient features for creating, manipulating, and querying graphs. If you want to learn more about the beauty of graphs in Elixir, check out Elixir for Graphs [Ham20].

You’ll use libgraph to implement a genealogy tree. A genealogy tree is a directed graph that points from parent chromosome to child chromosome and shows the transition of the evolution from the first population to the last population. A directed graph is a graph whose edges have a direction — edges start on one node (the parent) and point to another (the child).

You can use the genealogy tree to trace the origins of your strongest chromosome or to see how traits evolved over time. You can even export your genealogy tree and visualize the genealogy of your evolution with third-party tools. First, you’ll need to implement it.

Before you begin, start by adding libgraph to your dependencies:

​ ​defp​ deps ​do​
​   {​:libgraph​, ​"​​~> 0.13"​}
​ ​end​

Then, run mix deps.get.

One important thing you need to do before you begin tracking genealogy is to ensure that each chromosome has a unique id associated with it. libgraph will overwrite existing entries in a genealogy tree if the attributes of a chromosome match one that’s already in the genealogy tree. To prevent this, alter your Types.Chromosome struct to look like this:

​ ​defmodule​ Types.Chromosome ​do​
​ 
​   @enforce_keys ​:genes​
​   defstruct [​:genes​,
​              ​id:​ Base.encode16(​:crypto​.strong_rand_bytes(64)),
​              ​size:​ 0,
​              ​fitness:​ 0,
​              ​age:​ 0]
​ ​end​

This code will generate a unique ID every time a chromosome is created. This will allow you to more easily query your graph for unique chromosomes.

Creating the Genealogy GenServer

Just like with statistics, you’ll use a GenServer to store your genealogy tree. Start by creating a new file genealogy.ex in utilities. In genealogy.ex, create a module, like this:

​ ​defmodule​ Utilities.Genealogy ​do​
​   ​use​ GenServer
​ ​end​

Now, go to application.ex and ensure Utilities.Genealogy is started with your application:

​ ​defmodule​ Genetic.Application ​do​
​   ​use​ Application
​ 
​   ​def​ start(_type, _args) ​do​
​     children = [
​       {Utilities.Statistics, []}
»      {Utilities.Genealogy, []}
​     ]
​ 
​     opts = [​strategy:​ ​:one_for_one​, ​name:​ Genetic.Supervisor]
​     Supervisor.start_link(children, opts)
​   ​end​
​ ​end​

Now, you need to implement the client-server behaviour of the GenServer. You’ll need to be able to do the following:

• Add chromosomes.
• Add child chromosome with parent(s).
• Access libgraph graph.

To keep things simple, you’ll only use the GenServer to add chromosomes to the genealogy tree and to obtain the current tree. If you need to explore the tree, you can obtain the graph from the GenServer and use any of libgraph’s functions.

You’ll start by implementing the server. First, you need to define what happens when the GenServer starts via the init function. This function should just initialize a new libgraph graph. libgraph’s API is exposed via the Graph module. Creating a new graph is as easy as calling Graph.new. Implement init, like so:

​ ​def​ init(_opts) ​do​
​   {​:ok​, Graph.new()}
​ ​end​

Graph.new automatically creates a new directed graph. Once your GenServer starts, it’ll be initialized with an empty directed graph.

Next, you’ll need a function that inserts multiple chromosomes at once. You’ll need this function to store the initial population of chromosomes in the graph. Because you’re updating the state of the genealogy tree, this functionality will be invoked via cast messages, so you’ll handle it using handle_cast/2. The message should come with a list of chromosomes to add and should be invoked using :add_chromosomes:

​ ​def​ handle_cast({​:add_chromosomes​, chromosomes}, genealogy) ​do​
​   {​:noreply​, Graph.add_vertices(genealogy, chromosomes)}
​ ​end​

libgraph has a convenient function, Graph.add_vertices/2, that handles adding multiple vertices to your graph.

Now you need to implement functionality for adding a chromosome with either one parent, in the event a chromosome is the result of mutation, or two parents, in the event a chromosome is the result of crossover. This functionality will be invoked via cast messages using the :add_chromosome message with either two or three chromosomes. Add the following to Utilities.Genealogy:

​ ​# Child is mutant of Parent​
​ ​def​ handle_cast({​:add_chromosome​, parent, child}, genealogy) ​do​
​   new_genealogy =
​     genealogy
​     |> Graph.add_edge(parent, child)
​   {​:noreply​, new_genealogy}
​ ​end​
​ 
​ ​# Child is crossover of Parents​
​ ​def​ handle_cast({​:add_chromosome​, parent_a, parent_b, child}, genealogy) ​do​
​   new_genealogy =

​     genealogy
​     |> Graph.add_edge(parent_a, child)
​     |> Graph.add_edge(parent_b, child)
​   {​:noreply​, new_genealogy}
​ ​end​

Graph.add_edge/3 adds an edge between two vertices. In this example, Graph.add_edge/3 will add an edge from parent to child. You don’t need to add child to the graph because Graph.add_edge/3 will automatically add it to the graph for you.

Finally, you need a way to obtain the current genealogy tree from the GenServer. This functionality will be invoked via call messages, so you’ll handle them with handle_call/3. Implement this functionality like this:

​ ​def​ handle_call(​:get_tree​, _, genealogy) ​do​
​   {​:reply​, genealogy, genealogy}
​ ​end​

This function is invoked with the message :get_tree and returns the current state of the genealogy tree.

With the server implemented, you need to implement accompanying client functions. The client functions should be friendly interfaces that invoke server methods. You’ll implement one client method for each server method you implemented: add_chromosomes/1, add_chromosome/2, add_chromosome/3, and get_tree/0. Additionally, you need to implement start_link, which initializes the GenServer. You can implement the client like this:

​ ​def​ start_link(_opts) ​do​
​   GenServer.start_link(__MODULE__, _opts, ​name:​ __MODULE__)
​ ​end​
​ 
​ ​def​ add_chromosomes(chromosomes) ​do​
​   GenServer.cast(__MODULE__, {​:add_chromosomes​, chromosomes})
​ ​end​
​ 
​ ​def​ add_chromosome(parent, child) ​do​
​   GenServer.cast(__MODULE__, {​:add_chromosome​, parent, child})
​ ​end​
​ 
​ ​def​ add_chromosome(parent_a, parent_b, child) ​do​
​   GenServer.cast(__MODULE__, {​:add_chromosome​, parent_a, parent_b, child})
​ ​end​
​ 
​ ​def​ get_tree ​do​
​   GenServer.call(__MODULE__, ​:get_tree​)
​ ​end​

Now that you’ve successfully implemented the functionality of a genealogy tree, you’ll need to update the genealogy tree using the GenServer in your framework.

Tracking Genealogy in Your Framework

The genealogy tree should be updated every time you add a new chromosome into the population. That means you should update the genealogy tree after population initialization, after any crossover takes place, and after any mutation takes place.

Start with population initialization. After you create your population in initialize/2, you’ll want to immediately add those chromosomes to your genealogy tree, like this:

​ ​def​ initialize(genotype, opts \\ []) ​do​
​   population_size = Keyword.get(opts, ​:population_size​, 100)
​   population = for _ <- 1..population_size, ​do​: genotype.()
​   Utilities.Genealogy.add_chromosomes(population)
​   population
​ ​end​

In this function, rather than immediately returning a new population, you initialize the population to a variable and add the list of chromosomes to the genealogy tree using the Utilities.Genealogy client. You then return the population.

Next, you’ll need to update your genealogy tree when children are created from crossover. Update your crossover/2 function to look like this:

​ ​def​ crossover(population, opts \\ []) ​do​
​   crossover_fn = Keyword.get(opts,
​                              ​:crossover_type​,
​                              &Toolbox.Crossover.single_point/2)
​   population
​   |> Enum.reduce([],
​       ​fn​ {p1, p2}, acc ->
​         {c1, c2} = apply(crossover_fn, [p1, p2])
»        Utilities.Genealogy.add_chromosome(p1, p2, c1)
»        Utilities.Genealogy.add_chromosome(p1, p2, c2)
​         [c1, c2 | acc]
​       ​end​
​     )
​ ​end​

This function is pretty much the same as it originally was; however, you add both c1 and c2 to your genealogy tree with p1 and p2 as parents.

Finally, you need to update the mutation/2 function. Change it so it looks like this:

​ ​def​ mutation(population, opts \\ []) ​do​
​   mutate_fn = Keyword.get(opts, ​:mutation_type​, &Toolbox.Mutation.scramble/1)
​   rate = Keyword.get(opts, ​:mutation_rate​, 0.05)
​   n = floor(length(population) * rate)
​   population
​   |> Enum.take(n)
​   |> Enum.map(
​       ​fn​ c ->
​         mutant = apply(mutate_fn, [c])
»        Utilities.Genealogy.add_chromosome(c, mutant)
​         mutant
​       ​end​
​     )
​ ​end​

Again, the only change here is adding the mutant to the genealogy tree with the original chromosome as its parent. At this point, you’re all set to track your genealogy during every genetic algorithm.

Exploring Genealogy of a Simulation

You can use any of the functions in the libgraph API to explore your genealogy tree. For example, if you wanted to see every chromosome that ever existed over the course of an evolution, you can access the vertices of the genealogy tree, like this:

​ tiger = Genetic.run(TigerSimulation,
​                     ​population_size:​ 20,
​                     ​selection_rate:​ 0.9,
​                     ​mutation_rate:​ 0.1,
​                     ​statistics:​
​                       %{​average_tiger:​ &TigerSimulation.average_tiger/1})
​ 
​ genealogy = Utilities.Genealogy.get_tree()
​ 
​ IO.inspect(Graph.vertices(genealogy))

If you run this, you’ll see a very long list of chromosomes. In the next chapter, you’ll learn how to export a visualization of the genealogy tree to better see how your evolution progresses over time.

👈 Logging Statistics Using ETS | TOC | What You Learned 👉

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.