Wanna have some Sunday afternoon fun? Just refresh your Erlang skills. Since this is me having fun, what better way to do so than to write yet another implementation of the compact Genetic Algorithm originally (cGA) proposed by Georges Harik?

I am going to skip describing the original algorithm and focus a bit on how to implement it in Erlang instead. You can find some nice books elsewhere and more information on the Erlang site. Erlang is an interesting mix of functional and logic programming languages. If you ever wrote code in ProLog, Erlang is going to look familiar. It will also look familiar if you are coming from Haskell, although, being Erlang a dynamically typed language, you will miss the type system and inference. Nevertheless, give it a chance. It concurrent model is worthwhile reading about. I will it for further posts thought.

Anyway, without further preamble, let’s dive into a naïve implementation of cGA in Erlang. Lists are an integral part of Erlang, hence it seems obvious that individuals could be represented by a list of integers. Under this representation, OneMax is trivial to implement by summing all the elements of the list defining an individual. Following this train of thought, the probabilistic model could also be represented by a simple list of floats (each entry representing the probability of 1 for a given locus).

Given the above description, a cGA implementation would just require: (1) an individual constructor based on sampling the current probabilistic model, (2) a function that given two evaluated individuals compute the model update, and (3) a function to check if the probabilistic model has converged. Once these basic functions are available, writing a cGA boils down to sampling two individuals, compute the updates required based on the evaluated individuals, and update the probabilistic model. This process should be repeated until the model has converged. The Erlang code below shows a possible implementation of such an approach.

% Naive implementation of the compact Genetic Algorithm in Erlang.
-module(cga).
-export([one_max/1, cga/4]).
 
% OneMax function.
one_max(String) -> lists:sum(String).
 
% Generates random strings of length N given a Model.
random_string(Model) ->
  lists:map(fun (P) -> case random:uniform() < P of true -> 1; _ -> 0 end end,
            Model).
 
% Generates a random population of size Size and strings of length N.
initial_model(N) -> repeat(N, 0.5, []).
 
% Given a pair of evaluated strings, returns the update values.
update({_, Fit}, {_, Fit}, N, _) ->
  repeat(N, 0, []);
update({Str1, Fit1}, {Str2, Fit2}, _, Size) ->
  lists:map(fun ({Gene, Gene}) -> 0;
                ({Gene1, _}) when Fit1 > Fit2 -> ((Gene1 * 2) - 1) / Size;
                ({_, Gene2}) when Fit1 < Fit2 -> ((Gene2 * 2) - 1) / Size
            end,
            lists:zip(Str1, Str2)).
 
% Check if the model has converged.
converged(Model, Tolerance) ->
  lists:all(fun (P) -> (P < Tolerance) or (P > 1 - Tolerance) end, Model).
 
% The main cGA loop.
cga(N, Size, Fun, Tolerance) when N > 0, Size > 0, Tolerance > 0, Tolerance < 0.5 ->
  cga_loop(N, Size, Fun, initial_model(N), Tolerance).
 
cga_loop(N, Size, Fitness, Model, Tolerance) ->
  case converged(Model, Tolerance) of
    true ->
      Model;
    false ->
      [P1, P2 | _] = lists:map(
        fun (_) -> Str = random_string(Model), {Str, Fitness(Str)} end,
        [1,2]),
      cga_loop(N, Size, Fitness,
               lists:map(fun ({M, U}) -> M + U end,
                         lists:zip(Model, update(P1, P2, N, Size))),
               Tolerance)
  end.
 
% Creates a list of Size repeating Value.
repeat(0, _, Update) -> Update;
repeat(N, Value, Update) -> repeat(N - 1, Value, [Value | Update]).

You can run this code by pasting it into a file named cga.erl. Use the Erlang shell to compile and run cGA as shown below (once you start the Erlang shell via erl).

1> c(cga).
{ok, cga.}
2> cga:cga(3, 30, fun cga:one_max/1, 0.01).
[0.999, 0.989, 0.098]

A couple of interesting considerations. Compiling and loading code in Erlang support hot code replacement without stopping a running production system. Obviously this property it is not critical for the cGA exercise, but it is an interesting property nonetheless. Another one is that functions, due to its functional programming ancestry, are first class citizens you can pass around. That means that the current implementation done supports you passing arbitrary fitness functions without having to change anything on the cGA implementation.

Finally, I mentioned that this is a naïve implementation to refresh my rusty Erlang syntax. You may want to spent some time profiling this implementation to see how to improve it. Also, you may want to start thinking on how we could take advantage of the concurrency model in Erlang to build a not-so-naive implementation of cGA.