Dynamic and Partially Connected Ring Topologies for Evolutionary Algorithms with Structured Populations

by Carlos Fernandes, Juan Laredo, Juan Merelo, Carlos Cotta, Agostinho Rosa
in EvoPAR

This paper investigates dynamic and partially connected ring topologies for cellular Evolutionary
Algorithms (cEA). We hypothesize that these structures maintain population diversity at a higher level and reduce the risk of premature convergence to local optima on deceptive and NP-hard fitness landscapes. A general framework for modelling partially connected topologies is proposed and three different schemes are tested. The results show that the structures improve the rate of convergence to global optima when compared to cEAs with standard topologies (ring, rectangular and square) on quasi-deceptive, deceptive and NP-hard problems. Optimal population size tests demonstrate that the proposed topologies require smaller populations when compared to traditional cEAs.

Anuncios

Unreliable Heterogeneous Workers in a pool-based evolutionary algorithm

by Mario Garcia-Valdez, Juan-J. Merelo, Francisco Fernández de Vega
in  EvoAPPS posters

In this paper the effect of node unavailability in algorithms using EvoSpace, a pool-based evolutionary algorithm, is assessed. EvoSpace is a framework for developing evolutionary algorithms (EAs) using heterogeneous and unreliable resources. It is based on Linda’s tuple space coordination model. The core elements of EvoSpace are a central repository for the evolving population and remote clients, here called EvoWorkers, which pull random samples of the population to perform on them the basic evolutionary processes (selection, variation and survival), once the work is done, the modified sample is pushed back to the central population. To address the problem of unreliable EvoWorkers, EvoSpace uses a simple re-insertion algorithm using copies of samples stored in a global queue which also prevents the starvation of the population pool. Using a benchmark problem from the P-Peaks problem generator we have compared two approaches: (i) the re-insertion of previous individuals at the cost of keeping copies of each sample, and a common approach of other pool based EAs, (ii) inserting randomly generated  individuals. We found that EvoSpace is fault tolerant to highly unreliable resources and also that the re-insertion algorithm is only needed when the population is near the point of starvation.

Tree depth influence in Genetic Programming for generation of competitive agents for RTS games

by Pablo García-Sánchez, Antonio Fernández-Ares, Antonio Miguel Mora, Pedro Ángel Castillo, Juan Julián Merelo, Jesús González
in EvoAPPS posters

This work presents the results obtained from comparing different tree depths in a Genetic Programming Algorithm to create agents that play the Planet Wars game. Three different maximum levels of the tree have been used (3, 7 and Unlimited) and two bots available in the literature, based on human expertise, and optimized by a Genetic Algorithm have been used for training and comparison. Results show that in average, the bots obtained using our method equal or outperform the previous ones, being the maximum depth of the tree a relevant parameter for the algorithm.

More info is available at the OSGiLiath Evolutionary Framework webpage.

Co-Evolutionary Optimization of Autonomous Agents in a Real-Time Strategy Game

by Antonio J. Fernández Ares, Antonio M. Mora, Maribel García Arenas, Pablo García Sánchez, Juan Julian Merelo Guervós, Pedro A. Castillo in EvoAPPS posters

This paper presents an approach based in an evolutionary algorithm, aimed to improve the behavioralparameters which guide the actions of an autonomous agent (bot) inside the real-time strategy game, Planet Wars. The work describes a co-evolutionary implementation of a previously presented method(ANONYMOUSBot), which yielded successful results, but focused in 4 vs 4 matches this time. Thus, there have been analyzed the effects of considering several individuals to be evolved (improved) at the same time in the algorithm, along with the use of three different fitness functions measuring the goodness of each bot in the evaluation. They are based in turns and position, and also inmathematical computations of linear regression and area regarding the number of ships belonging to the bot/individual to be evaluated. In addition, the variance of using an evolutionary algorithm with and without previous knowledge in the co-evolution phase is also studied, i.e., respectively using specific rivals to perform the evaluation, or just considering to this end individuals in the population being evolved. The aim of these co-evolutionary approaches are mainly two: first, reduce the computational time; and second find a robust fitness function to be used in the generation of evolutionary bots optimized for 4 vs 4 battles.

An object-oriented library in JavaScript to build modular and flexible cross- platform evolutionary algorithms

by Victor Manuel Rivas Santos, Maria Isabel Garcia Arenas, Juan Julian Merelo Guervos, Antonio Mora Garcia and Gustavo Romero Lopez.
In EvoAPPS posters (see the poster at slideshare)

This paper introduces jsEO, a new evolutionary computation library that is executed in web browsers, as it is written in Javascript. The  library allows the rapid development of evolutionary algorithm, and makes easier the collaboration between different clients by means of individuals stored in a web server. In this work, jsEO has been tested against two simple problems, such as the Royal Road function and a 128-terms equation, and analysing how many machines and evaluations it yields. This paper attempts to reproduce results of older papers using modern browsers and all kind of devices that, nowadays, have JavaScript integrated in the browser, and is a complete rewrite of the code using the popular MooTools library. Results show that the system makes easier the development of evolutionary algorithms, suited for different chromosomes representations and problems, that can be simultaneously executed in many different operating systems and web browsers, sharing the best solutions previously found.

Evolving Evil: Optimizing Flocking Strategies through Genetic Algorithms for the Ghost Team in the Game of Ms. Pac-Man

by Federico Liberatore, Antonio Mora, Pedro Castillo, Juan Julián Merelo in EvoGAMES

Flocking strategies are sets of behavior rules for the interaction of agents that allow to devise controllers with reduced complexity that generate emerging behavior. In this paper, we present an application of genetic algorithms and flocking strategies to control the Ghost Team in the game Ms. Pac-Man. In particular, we define flocking strategies for the Ghost Team and optimize them for robustness with respect to the stochastic elements of the game and effectivity against different possible opponents by means of genetic algorithm. 
The performance of the methodology proposed is tested and compared with that of other standard controllers belonging to the framework of the Ms. Pac-Man versus Ghosts Competition. The results show that flocking strategies are capable of modelling complex behaviors and produce effective and challenging agents. 

The presentation is:

 

You can also see a brief demo here (we are the ghosts :D):

Enjoy it!

(And cite us, of course :D)

Introducción a Clojure

Clojure es un miembro de la familia LISP que se ejecuta sobre la JVM pudiéndo consumir y producir para dicho entorno.

Se destaca por poseer conceptos que facilitan el desarrollo de aplicaciones concurrentes además de la flexividad que de por sí significan las macros de los LISPs. En esta presentación se hace una introducción que destaca algunas de sus características así como ejemplica mediante demos.

Para profundizar en el tema se recomienda el libro Clojure Programming (2012) de Chas Emerick, Brian Carper, and Christophe Grand así como las presentaciones hechas por su creador:

http://www.infoq.com/presentations/Value-Values

http://www.infoq.com/presentations/Simple-Made-Easy-QCon-London-2012

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

http://www.infoq.com/presentations/hickey-clojure