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

El año pasado había implementado un ejemplo con AjAgents usando CCR:

Agentes usando Concurrency and Coordination Runtime (CCR)
Agents using Concurrency and Coordination Runtime (CCR)

Escribí en mi blog en “anglish” (Angel’s English) algunas ideas para explorar:

Agents in a Grid

Recordemos que Concurrency and Coordination Runtime es parte de Microsoft Robotics Studio, puede leer más sobre esta librería en

Concurrent Affairs: Concurrency and Coordination Runtime

y consultar mis enlaces de Delicious

http://del.icio.us/ajlopez/ccr
http://del.icio.us/ajlopez/msrs

En estos días, extendí mi ejemplo AjAgentsCCR-0.1.zip con dos nuevos proyectos. Uno de consola AjAgents.Genetic01, y otro de ventanas AjAgents.WinGenetic01:

La idea básica es ejecutar un algoritmo genético usando agentes, los elementos de AjAgents, que se envían mensajes usando ports de CCR. Cada agente procesa sus mensajes entrantes, y envía mensajes salientes a otros agentes, en paralelo. El problema que encaro es el clásico Travelling Salesman Problem. Leo en la Wikipedia:

If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A?

La ventana de ejemplo es sencilla:

La clase Genoma representa el viaje (una lista de Points y un valor de distancia total):

class Genoma { public List<Point> travel = new List<Point>(); public int value; } class Point { public int x; public int y; }

Al comenzar la ejecución, los agentes son creados y conectados:

best = new BestSoFar(); evaluator = new Evaluator(); mutator = new Mutator(); collector = new Collector(); evaluator.Collector = collector; collector.Mutator = mutator; collector.Evaluator = evaluator; collector.BestSoFar = best; mutator.Evaluator = evaluator;

Un genoma inicial es creado:

Genoma genoma = new Genoma(); Random rnd = new Random(); for (int k = 0; k<40; k++) { Point pt = new Point(); pt.x = rnd.Next(12); pt.y = rnd.Next(12); genoma.travel.Add(pt); } genoma.value = evaluator.CalculateValue(genoma);

El agente BestSoFar dispara un evento. El formulario se registra como observador de ese evento, para refrescar el mejor viaje calculado y dibujarlo. El programa envía el genoma inicial generado al agente Mutator, varias veces, para generar la primeras poblaciones:

best.NewBest += BestGenoma; for (int k = 0; k < 60; k++) { mutator.Post("Mutate", genoma); }

Noten el uso del método Post, básico en AjAgents. Cada agente implementa ese método, que invoca un método en el agente, usando una puerta de CCR para invocar el método final. El método es ejecutado entonces no en el momento, sino en forma “paralela”, en un thread que maneja el pool de threads de CCR.

Un diagrama simple para explicar la interacción entre agentes:

El Mutator envía cada genoma al Evaluator. Este agente calcula el valor asignado a ese genoma. Lo envía a el Collector. Este implementa una nueva idea para este ejemplo: en vez de tener una clase Population o similar, el Collector recive genomas, y cuando tiene n o más genomas, determina los mejores del conjunto, envía el mejor a BestSoFar, y reenvía los mejores a Mutator, para generar una nueva lista de genomas a evaluar. Como método típico de ejemplo, tomemos uno de la clase Collector:

void ProcessList(List<Genoma> list) { list.Sort(comparer); bestsofar.Post("Process",list[0]); evaluator.Post("Evaluate",list[0]); evaluator.Post("Evaluate",list[1]); for (int k = 0; k < 4; k++) { mutator.Post("Mutate",list[k]); mutator.Post("Mutate",list[k]); } }

Tengo que mejorar el algoritmo genético. Ahora, sólo usa mutación, sin hacer “crossover” (cruzamiento) entre los mejores genomas. El resultado que consigue ahora, no es óptimo: puede dar como resultado un máximo local, pero no la mejor solución. La idea del ejemplo es ver ejecutando AjAgents con CCR, en una prueba de concepto.


Conclusiones


Uno puede ver cada agente como una pequeña célula u organismo, que reacciona a mensajes externos y envía mensajes a otros agentes. Cada agente está levemente acoplado a los demás. En estos ejemplos, los agentes son creados y relaciones por código, pero bien podrían ser creados y relacionados usando algún framework de inyección de dependencias, como Spring.NET o el nuevo Unity Application Block de Microsoft.


En lugar de usar solamente ports de CCR, podría escribir los agentes como  DSS Service components (ver Microsoft Robotics Studio para más información sobre DSS); el algoritmo podría ser distribuido en una grilla (“gridified”) y cada agente interactuar con otros, independientemente de su ubicación..


Pero eso es otra historia….;-)


En esta semana, ha sido anunciada la nueva versión de Microsoft Robotics Developer Studio 2008:


http://blogs.msdn.com/msroboticsstudio/archive/2008/04/09/microsoft-robotics-developer-studio-2008-ctp-april-available.aspx


La tercera nueva característica ahí anunciada, sería muy interesante para implementar “miniagentes” distribuidos:


Support for creating applications that run on multiple DSS nodes using Visual Programming Language and DSS Manifest Editor. This makes it much simpler to create applications that run across nodes, either on the same machine or across the network. When an application containing multiple nodes is to be started, VPL creates individual deploy packages for each node and fires them up across the network.


(este artículo es la versión en español de mi versión “anglish”:
Genetic Algorithms with AjAgents and Concurrency and Coordination Runtime (CCR)


)


Nos leemos!


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

This entry was posted in 1389, 7337, 7338. Bookmark the permalink.

Leave a Reply

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


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>