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.

[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.

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:

New journal paper in press

C.M. Fernandes, J.J. Merelo, A.C. Rosa, A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization, Information Sciences, in press.

Abstract - Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating – a type of non-random mating in which individuals are chosen according to their similarities – may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune.

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.

The Sandpile Mutation Operator at Torino, Italy

Last thursday morning, at the Evo* congress, I was presenting our study on the mutation rates evolved by the Sandpile Mutation Operator, an alternative mutation scheme for GAs, specifically designed for Dynamic Optimization Problems, based on the Self-Organized Criticality Theory and the Bak-Tang-Wiesenfeld Sandpile Model.

Paper Seminar: Evolutionary Computing and Autonomic Computing: Shared Problems, Shared Solutions?

This Friday, March 11th, we will discuss the paper Evolutionary Computing and Autonomic Computing: Shared Problems, Shared Solutions? by Prof. A.E. Eiben in our Friday Paper Seminar. Quite a position paper about Self* properties in Evolutionary Algorithms and the other way around; Evolutionary Algortihms in Self* Computing.

You are welcome to attend the chat on Sala de Juntas at the ETSIIT.

View Larger Map

Crónica seminario sobre coevolución

Esta mañana hemos dado el paper seminar sobre coevolución, con un lleno absoluto. Vamos a tener que cambiar a la sala de Juntas como sigamos así.
He aprovechado para hacer mi primera presentación en Prezi que no puedo empotrar porque me salen cosas raras finalmente he podido empotrar usando esta solución.

El trabajo no decepciona: es de los tiempos cuando en siete páginas se creaba no ya un algoritmo, sino una familia completa: los algoritmos coevolutivos. Y siendo del creador de Thinking Machines y uno de los padres fundadores de la vida artificial, tampoco. Por eso es fácil de entender: se trata de crear un algoritmo que diseñe redes de clasificación que sean mejores (que necesiten menos cambios) que las existentes. Y hacerlo usando evolución; pero la evolución no funciona, porque las redes se quedan estancadas clasificando bien el (limitado) conjunto de test que se les da, y de ahí no hay quien las saque. Así que para aumentar la diversidad y crear redes capaces de clasificar más pruebas en menos cambios, creó dos poblaciones: una de redes y otra de tests. Las redes tratan de clasificar contrimás mejor, y los tests pues justamente al reves. Al final no gana ni una ni otra, sino el autor que consigue pasar a la historia y aumentar su número H. Y nosotros también, con un algoritmo muy interesante que finalmente podremos aplicar a nuestro competidor en el reto Google de inteligencia artificial (próximamente en su congreso de confianza)