MorAnts. Mi primera investigación ‘rentable’

Pues si. :D

Recientemente y compaginando, por una parte el I Hackatón del reto de inteligencia artificial de Google en la UGR, propuesto por la Oficina de Software Libre de dicha universidad, y por otra el Google AI Challenge 2011, me decidí a participar en ambos ‘concursos’, creando un bot capaz de jugar de forma autónoma (y combatir contra otros rivales) al juego ANTS, implementado para la ocasión por el Computer Science Club de la Universidad de Waterloo.

Grosso modo, se trata de un juego de estrategia en tiempo real en el que debemos dirigir a una serie de hormigas en mapas generalmente laberínticos, con el objetivo de eliminar a todas sus rivales, principalmente los nidos de los que salen. Para ello deberemos buscar comida (para generar nuevas hormigas), sortear obstáculos en el mapa y aplicar reglas algo complejas en los enfrentamientos, para los que es conveniente moverse en grupos.

En la siguiente presentación, que yo mismo hice durante la introducción a dicho Hackaton, se pueden ver los pormenores de la competición:

En definitiva, a pocos días de la finalización del plazo de ambos concursos, diseñé un bot con una sencilla máquina de estados finitos, en la cual se tenían 4 estados básicos. A modo de resumen:

•  Explorando -> estado en el que las hormigas se mueven de forma pseudoaleatoria, ya que según su ID (módulo 4) se mueven en una dirección, consiguiendo que éstas se agrupen al tiempo que exploran zonas diferentes del mapa.
•  Ir hacia comida -> las hormigas se mueven hacia la unidad de comida más cercana.
•  Ataque a enemigo -> todas las hormigas que lo vean se dirigen hacia un enemigo.
•  Ataque a colinas -> todas las hormigas que la vean se dirigen hacia una colina enemiga.

En dichos estados se hacían varias consideraciones, como evitar obstáculos (con movimientos simples) o evitar el choque entre hormigas propias (que supone la ‘muerte’ de las mismas).

El bot lo bautizé como MorAnts (original, ¿verdad? :D) y lo liberé con una licencia GPL en la Forja de Rediris, dado que era requisito imprescindible del concurso de la OSL-UGR. ;)
El paquete con los fuentes, así como varios ejemplos de uso y el juego ANTS, se puede decargar -> aquí <-

Por falta de tiempo (en gran parte debido a los requititos de mi nenita, Julia :)), no pude hacer una mejor aproximación, dejando para un futuro mejoras (sustanciales) de los estados, como por ejemplo: búsqueda de caminos mínimos, rodear obstáculos, evaluar enemigos antes de atacar (número, agrupación), etc.

Además, como ‘buenos’ investigadores que somos, queda pendiente la aplicación de técnicas de las que a nosotros nos gustan, es decir, cosicas de Soft Computing (Algoritmos Genéticos, Algoritmos basados en Colonias de Hormigas o Redes Neuronales, por ejemplo). :D

Finalmente y yendo a la parte pragmática del trabajo, el caso es que aún siendo mi bot bastante ‘regulero’ (en comparación con otros del AI Challenge de Google), conseguí ganar el concurso propuesto por la Oficina de Software Libre de la UGR, cuyo premio consistía en un cheque regalo para coger ‘material’ en una tienda de informática. :D

Para los interesados diré que mis regalos fueron un e-reader y un disco duro multimedia, Yuhuuuuuu! :D

Así da gusto investigar. ;)

Histograms for Comparing Evolutionary Algorithms

Last Friday we were discussing the paper by Tirronen and Weber, «Sparkline Histograms for Comparing Evolutionary Algorithms«, presented at IJCCI 2010. This work proposes histograms that represent the distribution of values in the set of results for comparing the performance of Evolutionary Algorithms. Such a visual comparison provides a quick evaluation of the relative performance of the algorithms in a test set, as well as the overall performance of each one. Some patterns of the histograms permit to identify features such as lack of robustness, high rate of convergence to local optima, and high standard deviation. Altough this method does not replace numerical and statistical comparisons, it may be helpfull in the analysis of Evolutionary Algorithms, so we suggest you to take a look at the work of Tirronen and Weber.

Optimización evolutiva de bots para el juego Planet Wars

Aquí está la presentación del trabajo que da título al post. Es una versión actualizada del trabajo que se presentó en el IWANN 2011, así que os refiero primero a esa versión por si no estáis al tanto.

For information about an early version of this work (in English) please check here.

Estudio de un Operador de Mutación para Algoritmos Genéticos Basado en la Teoría de la Criticalidad Auto-Organizada

Our studies on the sandpile mutation operator were extended, presented at MAEB2012 and published in the proceedings (in spanish). The abstract:

La mutación montón de arena es un operador para Algoritmos Genéticos basado en un modelo de Criticalidad Auto-Organizado con el mismo nombre. El operador ha sido desarrollado con el objetivo de resolver problemas con función objetivo variable. Este artículo propone un estudio del operador y la optimización de su desempeño, experimentando diferentes estrategias que conectan el modelo auto-organizado y el Algoritmo Genético. Las pruebas sobre el algoritmo se desarrollan con un gran conjunto de problemas dinámicos, diseñados con un generador de problemas a partir de funciones-base no dinámicas. Las mejores configuraciones del algoritmo son comparadas con dos AGs recientemente propuestos para optimización dinámica. Demostramos que un AG con el operador de mutación montón  de arena es eficiente para el conjunto de pruebas que es propuesto.

Last call to submit your contribution to Natural Computing: SI on Distributed Evolutionary Computation in Informal Environments.

The deadline for submission has changed to 5 March 2012.

Papers should be submitted through the Natural Computing system by selecting this special issue (SI: Informal Environments) as “Article Type”.

Call for papers

---

Informal computing includes ways of creating computing systems which are not fixed or bound to an organization, such as:

• Parasitic or stealth computing: using computing resources without explicit authorization from the user, for instance by visiting a web page.
• Volunteer computing: the user submits resources to a pool explicitly, by running a program o visiting a web site.
• Freeriding computing: using computing resources which are free or available, to a certain extent, in the network; for instance, using Google Apps or resources such as Wolfram-Alpha. Similar to parasitic computing, except that the provider of those resources knows, but does not care (up to a certain extent).
• Ubiquitous computing: using computing power available in user devices such as mobile phones or other appliances.

Using these (and similar) kinds of computing presents its own challenges, since neither the topology nor the availability of a particular node is known; computing nodes will have different performances and capabilities (and the connection to them will too) so that evolutionary computing paradigms will have to be adapted to them to take full-advantage of the system without losing the essence of evolutionary algorithm.

Topics of interest include but are not limited to:

• Complex systems issues in parasitic/volunteer computing
• Emerging computing environments, free or low-price: cloud computing, NoSQL, REST and other web services
• Performance evaluation and measuring  (speed ups, scalability, work load…).
• Adaptation of algorithms to dynamic, ad-hoc environments
• Evolutionary computation and other bioinspired algorithms in P2P, Map/Reduce and other dynamic environments.
• Bioinspired algorithms applied to those types of environments.
• Implementation issues
• Open source implementations

Both theoretical and applied works related to the topics are sought, as well as those that present a framework that is based on an informal computing environment.

Editors

JJ Merelo, University of Granada
Maribel García Arenas, University of Granada
Juan Luis Jiménez Laredo, University of Luxemburg
Francisco Fernández de Vega, University of Extremadura
David Corne, Heriot-Watt University

Presentando el algoritmo genético basado en CouchDB

Se trata básicamente de usar CouchDB, una base de datos NoSQL basada en almacenar claves/valores, como base para un algoritmo genético basado en pool. Estos algoritmos desacoplan la población del programa, colocándola en un almacén persistente.

El trabajo ha sido presentado en el congreso MAEB de metaheurísticas y algoritmos evolutivos y bionspirados, y es el primero de una serie. El código os lo podéis descargar de el repositorio junto con los datos y demás; os podéis también descargar el trabajo completo
Aquí tenemos un video del algoritmo funcionando: