Dealing with Noisy Fitness in the Design of a RTS Game Bot

This paper is a part of my Final Degree Project and it’s the result of our participation in the Google AI Contest of 2010. It’s also my first presentation in an conference, and the first time in English. In this paper we talk about the design of a bot that can play (and win) to the game Planet Wars. In this post we can read the rules of the contest and the game.

In this paper, we study the impact of the noisy fitness in the desing of the bot, because the choose of a bad fitness can make useless the genetic algorithm.

The presentation can be found here:
http://www.slideshare.net/antaress/dealing-with-noisy-fitness-in-a-rts-game-bot-design

This paper was accepted in the EvoGame and was nominated for the best paper.

Pool based evolutionary algorithm presented in EvoStar 2012

This is the first internationally published paper (it was previously published in a Spanish conference of a series that deals with a system, intended for volunteer computing, that uses a pool for implementing distributed evolutionary algorithms. The basic idea is that the population resides in a pool (implemented using CouchDB), with clients pulling individuals from the pool, doing stuff on them, and putting them back in the pool. The algorithm uses, as much as possible, CouchDB features (such as revisions and views) to achieve good performance. All the code (for this and, right now, for the next papers) is available as open-source code.
The paper was accepted in the first edition of EvoPar as poster, and mainly concentrates on studying the effect of different parameters on scaling and performance, and comparing it with a canonical GA. Here’s the poster

The paper Pool-Based Distributed Evolutionary Algorithms Using an Object Database is available from SpringerLink if your university subscribes to it. If it does not, please send us an email.

Testing different diversity-enhacing migration and replacement policies in dynamic environments (an evolutionary robotics case)

The paper “Testing Diversity-Enhancing Migration Policies for Hybrid On-Line Evolution of Robot Controllers” has been published in Evostar 2012. This work was developed during my foreign stay at the Vrije Universiteit Amsterdam, with Doctor A.E. Eiben. Appart from having a great time of my life in Amsterdam, I did experiments, and science and stuff.

In this work, we present the results obtained from comparing several migration policies that tries to optimize in a noisy fitness environment: the on-line, on-board and hybrid evolutionary robotics problem. Three different migration policies have been studied (the most different migrant, random migrant and best migrant) and two replacement mechanisms: the migrant replaces the worst, or the migrant replaces the worst after being evaluated only if is better. Experiments with 4, 16 and 36 robots were conduced, with two different topologies (ring and panmictic) and also a comparison with other evolutionary robotics algorithms were performed. Results show that the replacement mechanism has more influence than the migration policy or topology, and it also affects the tuning of the algorithm parameters. We asked ourselves the next questions:

• Using the hybrid approach (island model), which is the best combination of migration policy, admission policy, and island topology?
• Is this combination better than the encapsulated and distributed alternatives?
• Does the number of robots affect the result and if so, how?

Conclusions, graphs and stuff and in the paper, but summarizing, multikulti technique (receive the most different individual of my population from other islands) and accept it in my population after its evaluation perform better than other alternatives, even with less migration rate.

You can also check the poster here.

The Springer link to the paper is  Testing Diversity-Enhancing Migration Policies for Hybrid On-Line Evolution of Robot Controllers but you can download the draft.

The abstract:

We investigate on-line on-board evolution of robot controllers based on the so-called hybrid approach (island-based). Inherently to this approach each robot hosts a population (island) of evolving controllers and exchanges controllers with other robots at certain times. We compare different exchange (migration) policies in order to optimize this evolutionary system and compare the best hybrid setup with the encapsulated and distributed alternatives. We conclude that adding a difference-based migrant selection scheme increases the performance.

[EVO* 12] Validating a Peer-to-Peer Evolutionary Algorithm

Tomorrow we will be presenting the work “Validating a Peer-to-Peer Evolutionary Algorithm” in Evo* 2012 held in Malaga, Spain. You can find below the abstract and presentation of the work.

This paper proposes a simple experiment for validating a Peer-to-Peer Evolutionary Algorithm in a real computing infrastructure in order to verify that results meet those obtained by simulations. The validation method consists of conducting a well-characterized experiment in a large computer cluster of up to a number of processors equal to the population estimated by the simulator. We argue that the validation stage is usually missing in the design of large-scale distributed meta-heuristics given the difficulty of harnessing a large number of computing resources. That way, most of the approaches in the literature focus on studying the model viability throughout a simulation-driven experimentation. However, simulations assume idealistic conditions that can influence the algorithmic performance and bias results when conducted in a real platform. Therefore, we aim at validating simulations by running a real version of the algorithm. Results show that the algorithmic performance is rather accurate to the predicted one whilst times-to-solutions can be drastically decreased when compared to the estimation of a sequential run.

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.

Using free cloud storage services for distributed evolutionary algorithms in GECCO 2011

Esta semana ha sido el GECCO en Dublin. Yo he asistido desde el jueves 14 hasta el sábado 16 y aunque no he podido ir a la totalidad del congreso si me ha dado tiempo a ver el ambiente general.
En este congreso he presentado el artículo titulado Using free cloud storage services for distributed evolutionary algorithms. Y la presentación la podéis encontrar en SlideShare.

En este artículo podéis encontrar cómo hemos usado Dropbox para crear un multicomputador que evoluciona un conjunto de islas que cooperan para resolver un Algoritmo Evolutivo Paralelo que actúa sobre dos problemas típicos de Computación Evolutiva (MMDP y 4-TRAP) y que, hasta el número de computadores donde lo hemos probado, es escalable puesto que los tiempos de evaluación de los individuos disminuyen a medida que añadimos nodos de computación al multi-computador.

Después de la presentación algunos de los asistentes realizaron algunas preguntas que os puedo aclarar por si os surge la duda. La primera era si todo el tráfico que se genera en la red que comparten los nodos del multi-computador llega al servidor de Dropbox para después distribuirse. Y la respuesta a esta pregunta es claramente “no”. Está claro que a la vista de los resultados de este artículo y el presentado en Nueva Orleans en CEC (Cloud-based Evolutionary Algorithms: An algorithmic study) Dropbox distribuye los datos primero a los ordenadores donde está sincronizado y después de eso al servidor de Dropbox.

Respecto a la segunda pregunta, estaba relacionada con el esquema de evolución de las islas y en el artículo podéis encontrar cómo está especificado con detalle. Una descripción general sería que cada isla evoluciona una población de individuos con un esquema generacional y un algoritmo evolutivo clásico con un operador de cruce uniforme y un mutador tipo flip-flop para codificación binaria.

The bestest MasterMind Algorithm ever

Even better Mastermind

View more presentations from Juan Julián Merelo Guervós

Well, by now, you must be a bit tired of Mastermind papers but we are not, since we are obtaining the best results ever. After introducing end games to streamline the end of the algorithms, we have tweaked the evolutionary algorithm, adding a permutation operator, for instance, to reduce the number of evaluations needed to find the solution. The results is the best yet, but, of course, there’s more to come in the future.
This paper was presented at CEC 2011 in the games session, and raised quite a bit of interest. The paper will be available from IEEExplore soon, but you can request copies now if you want

Parallel Ants at IWANN 2011

Some days ago we presented at the IWANN Conference our new work devoted to study the parallelization of Multi-Objective Ant Colony Optimization algorithms (MOACOs) following different schemes.

It was a very funny presentation (and very interesting, of course :D), because the slides included some CC memes. ;)

These are the slides:

The whole paper can be found here.

Enjoy them! ;)

About Game Bots and Ambient Assisted Living

Last week we were in IWANN Conference, held in Torremolinos (Málaga), presenting two different works. The first one is about evolving IA bots for playing games in the Google AI Challenge. The basic idea is to improve the parameters of a hard-coded bot. Results shown that the default parameters we thought are important may be not work so good, and we can learn a lot of emerging behavior of the trained bot.

Here is the presentation:

Citation is here

The second one, is about a project I was working in last year. It’s about Ambient Assisted Living, Context-awareness and other stuff like that. The presentation is not so awesome. It was presented in the satellite workshop IWAAL.

You can download the paper in Springerlink here.

Doing evolutionary algorithms with Dropbox

Why not use Dropbox as its name implies, as a box for dropping individuals that could be interchanged among different islands running evolutionary algorithms?
That’s exactly what we are doing in a series of papers that are being published and presented in IWDECIE, CEC 2011 and GECCO, in last-in, first-out order. This presentation is for the second, presented today in CEC.

Using dropbox for distributed evolutionary computation

View more presentations from Juan Julián Merelo Guervós

What we try to test in this paper is whether we can add a good number of computers (up to 4) without a saturation of the network (or of Dropbox itself), and whether there is a difference between wired and wireless. It so happens there is, but it gets smaller when you increase the number of computers.

Still many tests to to, but for the time being this looks promising. We’ll link the paper when it’s available. For the time being, if you’re interested just send us an email