Algoritmos Genéticos usando GoRoutines y Channels en C#

Published on Author lopezLeave a comment

Hace más de un año, escribí:

Algoritmos Genéticos con AjAgents y Concurrency and Coordination Runtime (CCR)

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

explorando la concurrencia en la implementación de una solución al Travelling Salesman Problem usando un algoritmo genético. Al final del año pasado, escribí un ejemplo, usando lo que ya había implementado en C#:

GoRoutines y Canales en C#

GoRoutines and Channels in C#

El código de este experimento está en el proyecto AjConcurr.Tsp en el repositorio:

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

Este es el resultado (no es una gran interfaz… ;-):

TSP no es un buen problema para resolver usando algoritmos genéticos: el resultado depende de la mejora de la población de soluciones tentativas después de cada iteración. En esta implementación uso un algoritmo de mutación (no estoy usando crossover) que intenta generar mejores individuos (en general, un algoritmo de mutación debería solamente cambiar al individuo, dejando la emergencia de mejoras al algoritmo genético mismo). El código está escrito en un gran método, que se lanza desde el botón Run. Es código sólo para demostración de la idea.

Al comienzo de ese método, se definen los canales a usar:

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

Recordemos: podemos poner un valor (un objeto cualquiera) en un channel, y en otro thread, podemos obtener el valor. Si colocamos un valor en un channel sin que haya otro thread que está esperando ese valor, nuestro thread se bloquea. Si tratamos de leer el próximo valor de un channel, y no hay tal valor, nuestro thread se bloquea. De esta forma, productores y consumidores de valores se van sincronizando.

El canal Evaluated recibe individuos (soluciones del problema) y los collecciona, formando una nueva población. El mejor individuo es enviado al canal bestsofar, que mantiene cuál es el mejor individuo hallado hasta el momento en el proceso. El canal genomas recibe un individuo, evalúa la solución que representa, y lo reenvía al canal evaluated. El canal mutator recibe un genoma, lo muta y evalúa. El nuevo genoma es entonces reenvíado al canal evaluated.

De esta forma, varias poblaciones son procesadas en paralelo. Para ser más exacto, no hay el concepto de población, sino que hay  N * M individuos en proceso. Por cada N de esos individuos que llegan al final del proceso, los mejores son seleccionados, y un nuevo grupo de N individuos es inyectado de nuevo en el proceso.

Veamos el código, compuesto de varias GoRoutinas. Primero, lanzamos una goruotine para generar la poblaciones iniciales:

// Generates the initial populations
GoRoutines.Go(() =>
{
    Genoma genoma = GenerateGenoma();
    for (int j = 0; j < PopulationSize * 10; j++)
    {
        genomas.Send(this.Mutate(genoma));
    }
});

Se lanza una goroutine para evaluar nuevos genomas:

// Evaluate genomas
GoRoutines.Go(() =>
{
    while (true)
    {
        Genoma genoma = (Genoma)genomas.Receive();
        genoma.value = this.CalculateValue(genoma);
        evaluated.Send(genoma);
    }
});

Una goroutine para coleccionar genomas, seleccionarlos, y generar un nuevo grupo, población:

// 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);
    }
});

Una goroutine para recibir y procesar los mejores encontrados hasta el momento:

// 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);
        }
    }
});

No puse una operación de crossover. El caso es que el problema y el algoritmo podrían cambiar, pero la idea es explorar la implementación paralela de un algoritmo genético.

El principal problema que encontré es en el proceso de una población acumulada. En ese paso, la goroutine tiene que enviar varios valores a varios canales. Si alimenta un canal, y ésto la bloquea, los demás canales no recibirán sus valores. Tuve que lanzar varias goroutines para solucionar este problema, cada una alimenta a un canal.

Próximos pasos: implementar el algoritmo usando Queue Channels como en:

Queue Channels en AjSharp

e implementar un actor model, colocando cada paso en un agente, no en una goroutine. Llegados a ese punto, podría intentar poner los agentes en distintas máquinas.

Nos leemos!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Leave a Reply

Your email address will not be published. Required fields are marked *