Angel "Java" Lopez : C Sharp, Programación

Algoritmos Genéticos usando GoRoutines y Channels en C#

lopez — Mon, 08 Feb 2010 07:56:36 GMT

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

Refactoreando AjLisp: un intérprete Lisp escrito en C#

lopez — Sun, 10 Jan 2010 11:50:51 GMT

En estos días estuve reimplementando el núcleo de mi intérprete Lisp de código abierto AjLisp. Había escrito sobre la anterior versión en el 2008:

AjLisp: a Lisp interpreter in .NET
AjLisp: un intérprete Lisp en .NET

Es trabajo en progreso. Pueden bajar el código de:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjLisp

(hay otras dos implementaciones en ese repositorio, en desarrollo: AjScheme, un Lisp tipo Scheme, y AjSharpure, que intenta seguir las ideas de Clojure). Debería escribir sobre esas implementaciones. Este post es el inicial en una serie sobre AjLisp. Es una corta introducción al estado actual del proyecto.

El principal cambio en esta nueva versión: el intérprete puede manejar objetos y valores nativos. La alternativa hubiera sido apuntar a esos objetos a través de “wrappers”, alguna clase que implemente SymbolicExpression o similar. Pero elegí manejar directamente objetos nativos. Para eso, cambié las primitivas y clases relacionadas para que recibieran como argumentos objetos en vez de IExpression. Sigue habiendo una interfaz IExpression, defined como:

    public interface IExpression
    {
        object Evaluate(ValueEnvironment environment);
    }

El ValueEnvironment (planeo cambiarle el nombre a BindingEnvironment, y derivarlo de alguna interfaz tipo IBindingEnvironment) mantiene una asociación anidada de nombres y valores:

Hay un interfaz IFunction:

    public interface IFunction
    {
        object Apply(List arguments, ValueEnvironment environment);
    }

que debería ser implementada por cualquier form expression (la cabeza de una lista a evaluar).

Las dos clases principales que representan los tipos núcleo del AjLisp son identificadores y listas:

Todo el proyecto fue armado siguiendo Test-Driven Development, así que no tuve problemas en cambiar la versión anterior: tenía toda una batería de tests que me ayudó en el proceso de refactoring. Este es el estado actual de los test:

Debería escribir sobre:

- La implementación de ValueEnvironment
- Manejo de objetos nativos
- El tipo List y su evaluación
- Evaluación de Identifier
- Las primitivas implementadas
- El Lexer y el Parser
- Operaciones numéricas
- Números racionales (AjLisp puede manejar pares enteros numerador/denominador)

Ahora, luego de lo que aprendí desarrollando estos proyectos (AjLisp, AjScheme, AjSharpure), estoy escribiendo un núcleo mínimo AjCoreLisp, para mostrar cuáles son las primitivas mínimas para crear un intérprete Lisp. Armado con esa implementación, me gustaría explorar alternativas de compilación, en vez de ser sólo intérprete. Mi primer candidato es Dynamic Language Runtime. Otro podría ser la producción de código C# directo. Sería demasiado encarar esa exploración sobre un intérprete “más grande”. Primero, entonces, estudiaré sobre compilar un intérprete con menos primitivas, más condensado.

Nos leemos!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

GoRoutines y Canales en C#

lopez — Sun, 03 Jan 2010 10:44:17 GMT

En post anteriores:

Canales y GoRoutines en AjSharp (Part 1)
Canales y GoRoutines en AjSharp (Part 2)

describí la implementación de gorutinas (goroutines, como en el lenguaje Go de Google), y canales en mi intérprete AjSharp. Al final del año que pasó, escribí una prueba rápida, implementando los mismos conceptos, pero para ser consumidos esta vez desde C# directamente. Pueden ver el código en

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

Primero, porté la clase Channel:

public class Channel
{
    private AutoResetEvent sethandle = new AutoResetEvent(false);
    private AutoResetEvent gethandle = new AutoResetEvent(false);
    private object value;

    public void Send(object value)
    {
        this.gethandle.WaitOne();
        this.value = value;
        this.sethandle.Set();
    }

    public object Receive()
    {
        this.gethandle.Set();
        this.sethandle.WaitOne();
        object result = this.value;
        return result;
    }
}

El código tiene una clase estática GoRoutines, con métodos como:

public static void Go(Action action)
{
    Thread thread = new Thread(new ParameterizedThreadStart(GoRoutines.RunAction));
    thread.IsBackground = true;
    thread.Start(action);
    //ThreadPool.QueueUserWorkItem(new WaitCallback(RunAction), action);
}

public static void Go(ITask task)
{
    Thread thread = new Thread(new ParameterizedThreadStart(GoRoutines.RunTask));
    thread.IsBackground = true;
    thread.Start(task);
    //ThreadPool.QueueUserWorkItem(new WaitCallback(RunTask), task);
}

Pueden lanzar una Action (lo que es en el framework delegate System.Action<>), en un nuevo thread (traté de hacerlo poniendo la tarea en la cola de ThreadPool, pero, no sé por qué, el rendimiento pasó a ser muy bajo; mi intento quedó en comentarios del código de arriba).

Cuando una acción recibe parámetros, se encapsulan los dos en una Task<>, como esta que recibe dos parámetros:

public class Task<T1, T2> : ITask
{
    private Action<T1, T2> action;
    private T1 parameter1;
    private T2 parameter2;

    public Task(Action<T1, T2> action, T1 parameter1, T2 parameter2)
    {
        this.action = action;
        this.parameter1 = parameter1;
        this.parameter2 = parameter2;
    }

    public void Run()
    {
        this.action(this.parameter1, this.parameter2);
    }
}

(hay clases Task para uno, dos o tres parámetros).

Pueden invocar GoRoutines.Go directamente, especificando una acción y sus parámetros:

public static void Go<T1, T2>(Action<T1, T2> action, T1 parameter1, T2 parameter2)
{
    Go(new Task<T1, T2>(action, parameter1, parameter2));
}

Podemos escribir esta invocación usando expresiones lambda:

[TestMethod]
public void RunGoRoutineWithTwoParameters()
{
    int i = 0;
    AutoResetEvent handle = new AutoResetEvent(false);
    GoRoutines.Go((x, y) => { i = x + y; handle.Set(); }, 2, 3);
    handle.WaitOne();
    Assert.AreEqual(5, i);
}

Con todo esto implementado, escribí una aplicación de consola AjConcurr.Primes, reimplementando el ejemplo de números primos de mi anterior post:

Channel numbers = new Channel();
GoRoutines.Go(() => { for (int k = 2; ; k++) numbers.Send(k);  });
Channel channel = numbers;
int prime = 0;
while (prime < 1000)
{
    prime = (int)channel.Receive();
    Console.WriteLine(prime);
    Channel newchannel = new Channel();
    GoRoutines.Go((input, output, p) =>
    {
       while (true)
       {
           int number = (int)input.Receive();
           if ((number % p) != 0)
               output.Send(number);
       }
    }, channel, newchannel, prime);
    channel = newchannel;
}

Me gusta ver este código formateado en pastie:

http://pastie.org/761916

Próximos pasos:

- Mejorar Channel para soportar múltiples productores y consumidores de valores que operan de forma simultánea sobre el mismo canal.
- Agregar soporte de Futures
- Agregar características de reactive programming (sé que está el Reactive Framework, quería experimentar algo con código propio).

Nos leemos!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

Code Kata: Capturando páginas web

lopez — Mon, 26 Oct 2009 09:31:03 GMT

Para practicar, como Code Kata (y también, como prueba de concepto para un proyecto relacionado con Hacia una Historia Clínica Digital de Código Abierto), estuve codificando un programa de Web Scraping. Pueden bajarse el código completo desde: Web Scrapping Example (pensé que en inglés era “scrapping” con doble p, así que quedó por ahora con ese nombre :-)

La solución, escrita en C#, contiene un proyecto de librería de clases, uno de tests de Visual Studio, y un programa de demostración, del tipo consola. Fue interesante codificar un mini HTML parser (simple, que no contempla todos los casos, sólo los necesarios para el trabajo), que soporta el análisis de páginas mal formadas. El usar TDD (Test-Driven Development) me permitió ir codificándolo de forma de estar seguro de lo que necesitaba como resultado, y además, que ese resultado fuera el correcto. Ejemplo de test simple:

[TestMethod]

public void ParseSimpleTag()

    HtmlParser parser = new HtmlParser("<html>");

    HtmlToken token = parser.NextToken();

    Assert.IsNotNull(token);

    Assert.AreEqual(HtmlTokenType.Tag, token.TokenType);

    Assert.AreEqual("html", token.Name);

    Assert.IsNull(parser.NextToken());

Para capturar las páginas, usé System.Net.WebClient, con código tan simple como:

private string GetContent()

    WebClient webclient = new WebClient();

    return webclient.DownloadString(this.address);

Como demostración, en el programa de consola, parto de explorar la página:

Medline Plus Drugs

Lanzando el programa de consola, aparece la salida, capturando algunos cientos de páginas, sobre información de drogas medicinales (efectos, posología, contraindicaciones, etc):

Exploro las páginas que apuntan a la información de drogas por letra, obtengo los enlaces a cada droga, traigo el contenido de la página, extraigo la información que me interesa (descartando el principio y el fin de la página) por cada droga. Un ejemplo de página:

Al final, genero una página de índice:

Podría implementar un mejor parser de HTML, y algunas operaciones más de extracción de datos. Pero para lo que quería obtener, me bastó. Y fue una buena experiencia de TDD.

Si usan la información generada, recuerden de leer los términos del sitio original (entiendo que necesitan una autorización para usarlo de forma comercial, no parece que haya problema en capturar los datos en un utilitario no comercial).

¿Por qué no explorar directamente la web para obtener estos datos? Porque el contexto de la prueba de concepto que me impuse, es que los médicos y enfermeros no tienen acceso a Internet desde todas las máquinas donde van a estar trabajando.

Nos leemos!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez