Genetic Algorithms using GoRoutines and Channels in C#

More than a year ago, I wrote:

Genetic Algorithms with AjAgents and Concurrency and Coordination Runtime (CCR)

exploring concurrency in the implementation of Travelling Salesman Problem using a genetic algorithm. At the end of past year, I wrote an example, using the ideas implemented in:

GoRoutines and Channels in C#

The code is in the AjConcurr.Tsp project at:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjConcurr

This is the result (not a great interface… ;-):

TSP is not a good problem to resolve using Genetic Algorithm: the result depends of the improvement of population after each iteration. My implementation uses a mutation algorithm that tries to generate better individuals (a fair algorithm should only mutate). The code is written in a big method, under the Run button click, only for demo purpose.

At the beginning, I define the channels:

            Channel genomas = new Channel();
            Channel evaluated = new Channel();
            Channel bestsofar = new Channel();
            Channel mutator = new Channel();

Remember: you can put a value (object) in a channel, and in another thread, you can get that value. If you put a value in a channel, and no thread is reading the channel, your thread is blocked. If you read a value from a channel, and no value is present, your thread is blocked. In this way, producers and consumers are synchronized.
Evaluated channel receives individuals (solutions to the problem) and collects it, forming a new population. The best individual is send to bestsofar channel, that keeps the best individual found in process. Genomas channel receives an individual, evaluate its fitness, and forward it to Evaluated channel. Mutator receives a genoma, mutates and evaluates it. The new genoma is forwarded to Evaluated channel.
Many populations are processed in parallel. More accurate: there is no population, there are N * M individuals that are processed, mutated, and collected. For each group of N collected individuals, the best are selected, and a new group of N individuals are injected again in the process.
This is the code. First, launch a goroutine to generate the initial populations:
// Generates the initial populations
GoRoutines.Go(() =>
{
    Genoma genoma = GenerateGenoma();
    for (int j = 0; j < PopulationSize * 10; j++)
    {
        genomas.Send(this.Mutate(genoma));
    }
});

 
Launch a goroutine to evaluate new genomas:
// Evaluate genomas
GoRoutines.Go(() =>
{
    while (true)
    {
        Genoma genoma = (Genoma)genomas.Receive();
        genoma.value = this.CalculateValue(genoma);
        evaluated.Send(genoma);
    }
});

A goroutine to collect genomas, select them, and generate a new group, population:
// Collect and select
GoRoutines.Go(() =>
{
  GenomaComparer comparer = new GenomaComparer();
    while (true)
    {
    List<Genoma> genomalist = new List<Genoma>();
    for (int k = 0; k < PopulationSize; k++)
    {
      Genoma genoma = (Genoma)evaluated.Receive();
      genomalist.Add(genoma);
    }
    genomalist.Sort(comparer);
    GoRoutines.Go(() => bestsofar.Send(genomalist[0]));
    for (int k = 0; k < PopulationSize / 5; k++)
      GoRoutines.Go(() => evaluated.Send(genomalist[k]));
    for (int k = 0; k < PopulationSize / 5; k++)
    {
      GoRoutines.Go(() => mutator.Send(genomalist[k]));
      GoRoutines.Go(() => mutator.Send(genomalist[k]));
      GoRoutines.Go(() => mutator.Send(genomalist[k]));
      GoRoutines.Go(() => mutator.Send(genomalist[k]));
    }
    }
});

A goroutine for receives genomas, improve them, and forwards them to evaluated channel:
// Mutates
GoRoutines.Go(() =>
{
    Random rnd = new Random();
    while (true)
    {
    Genoma genoma = (Genoma)mutator.Receive();
    Genoma newgenoma = this.Mutate(genoma);
        while (newgenoma.value >= genoma.value)
        {
            if (rnd.Next(3) == 0)
                break;
        newgenoma = this.Mutate(genoma);
        }
        evaluated.Send(newgenoma);
    }
});

A goroutine to receives and process the best-so-far indivuals:
// Receives and draws the results
GoRoutines.Go(() =>
{
    Genoma best = null;
    while (true)
    {
        Genoma genoma = (Genoma)bestsofar.Receive();
        if (best == null || best.value > genoma.value)
        {
            best = genoma;
            this.BestGenoma(genoma);
        }
    }
});

I didn’t write support for crossover, but it could be added. The problem and algorithm could be changed. The main idea of this spike is to show the parallel implementation of a genetic algorithm.
The main problem is in the evaluated channel reading and processing. In that step, the goroutine forwards values to many channels. I had to launch many goroutines to feed the channels, because if one of these is blocked, the full process were blocked.
Next step: implement and use Queue Channels as in:
Implements actor model, and put each step in an agent. And then, implement distributed agents.
Keep tuned!
Angel “Java” Lopez

  
http://www.ajlopez.com 
http://twitter.com/ajlopez