Workshop on Spatially Structured Metaheuristics

We cordially invite you to attend the following two-presentations on Spatially Structured Metaheuristics. This mini-workshop will be held at 11.30 a.m. in the CITIC-UGR building (June 26th, 2014).

Spatially Structured Metaheuristics: Principles and Practical Applications
by Juan Luis Jiménez Laredo (University of Luxembourg)

A relevant number of metaheuristics are based on population. Although conventions may establish different names, individuals in evolutionary algorithms, ants in ant colony optimization or particles in particle swarm optimization belong to the same side of a coin: they are all  atomic elements of the population (a.k.a. building-blocks). In this context, spatially structured metaheuristics investigate how to improve the performance of metaheuristics by confining these elements in neighborhoods. This talk aims at presenting the working principles of spatially structured metaheuristics and practical applications to enhance diversity, scalability and robustness.

 

Spatially Structured Metaheuristics: Dynamic and Self-organized Topologies
by Carlos M. Fernandes (University of Lisbon)

Population based metaheuristics are computational search or optimization methods that use a population of possible solutions to a problem. These solutions are able communicate, interact and/or evolve. Two types of strategies for structuring population are possible. In panmictic populations, every individual is allowed to interact with every other individual. In non-panmictic metaheuristics, also called spatially structured population-based metaheuristics, the interaction is restricted to a pre-defined or evolving structure (network). Traditional spatially structured metaheuristics are built on pre-defined static networks of acquaintances over which individuals can interact. However, alternative strategies that overcome some of the difficulties and limitations of static networks (extra design and tuning effort, ad hoc decision policies, rigid connectivity, and lack of feedback from the problem structure and search process) are possible. This talk discusses dynamic topologies for spatially structured metaheuristics and describes a new model for structuring populations into partially connected and self-organized networks. Recent applications of the model on Evolutionary Algorithms and Particle Swarm Optimization are given and discussed.

Advertisements

Evolution using JavaScript in EvoStar

JavaScript, despite its age, is considered now an emergent language, since it is starting to have a ecosystem that allows the development of complex and high-performance applications. That is why in the recent EvoStar we had a poster that uses evolutionary algorithms libraries written using it. It is based on MOOTools to create an object-oriented browser-based library called jsEO, and is entitled An object-oriented library in JavaScript to build modular and flexible cross-platform evolutionary algorithms.

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)

Volunteer-based evolutionary algorithms al dente

Planning the cook of a time consuming optimization problem? Have you considered to let a crowd of volunteers to help you in this endeavor? In a volunteer-based system,  volunteers provide you with free ingredients (CPU cycles, memory, internet connection,..) to be seasoned with only a pinch of peer-to-peer or desktop-grid technology.

If you are looking for a delicious cook of a volunteer-based evolutionary algorithm, you can find our recipe in this paper published in Genetic Programming and Evolvable Machines (pre-print version available here)

Title: “Designing robust volunteer-based evolutionary algorithms

Abstract This paper tackles the design of scalable and fault-tolerant evolutionary algorithms computed on volunteer platforms. These platforms aggregate computational resources from contributors all around the world. Given that resources may join the system only for a limited period of time, the challenge of a volunteer-based evolutionary algorithm is to take advantage of a large amount of computational power that in turn is volatile. The paper analyzes first the speed of convergence of massively parallel evolutionary algorithms. Then, it provides some guidance about how to design efficient policies to overcome the algorithmic loss of quality when the system undergoes high rates of transient failures, i.e. computers fail only for a limited period of time and then become available again. In order to provide empirical evidence, experiments were conducted for two well-known problems which require large population sizes to be solved, the first based on a genetic algorithm and the second on genetic programming. Results show that, in general, evolutionary algorithms undergo a graceful degradation under the stress of losing computing nodes. Additionally, new available nodes can also contribute to improving the search process. Despite losing up to 90% of the initial computing resources, volunteer-based evolutionary algorithms can find the same solutions in a failure-prone as in a failure-free run.

Sistemas Clasificadores

Los sistemas clasificadores son una fusión entre los algoritmos evolutivos, el aprendizaje por refuerzo y el supervisado. Se conocen como Learning Classifier Systems. El viernes pasado aproveché la reunión del grupo para presentar una breve revisión histórica y dar detalles sobre quizá el algoritmo más importante introducido en este campo, el eXtended Classifier System o XCS de Wilson.

Básicamente, el algoritmo busca mediante evolución genética y aprendizaje un conjunto de reglas que modelen la solución a un problema donde existe recompensa. Las reglas se componen de una condición y una acción. La población de reglas representa para cualquier condición dada, cual será la mejor acción. Esto se consigue asociando al espacio de entrada una predicción de la mejor recompensa futura obtenida para cada acción posible.

Entonces, dado un estado que representa el entorno, se buscan las reglas cuya condición coincide, y de ellas se toma la acción que ofrece mejor recompensa futura.

La tarea no es fácil, los algoritmos formales de aprendizaje por refuerzo, necesitan a priori un conocimiento determinista de las posibles entradas y las transiciones resultantes de las acciones, dejando poco o nada para la búsqueda y aplicación de generalización.

Con XCS este problema se resuelve introduciendo algunos ajustes a la componente genética. La idea general es básicamente repartir los recursos (reglas) para que representen todo el espacio con la mayor precisión y generalización posible. Como no es algo que se pueda resumir en unas pocas líneas, aquí os dejo la presentación:

“The L-Co-R co-evolutionary algorithm: a comparative analysis in medium-term time-series forecasting problems” at ECTA

Our paper “The L-Co-R co-evolutionary algorithm: a comparative analysis in medium-term time-series forecasting problems” was accepted for oral presentation in the latest ECTA-IJCCI conference.

The abstract:
This paper presents an experimental study in which the effectiveness of the L-Co-R method is tested. L-Co-R is a co-evolutionary algorithm to time series forecasting that evolves, on one hand, RBFNs building an appropriate architecture of net, and on the other hand, sets of time lags that represents the time series in order to perform the forecasting using, at the same time, its own forecasted values. This coevolutive approach makes possible to divide the main problem into two subproblems where every individual of one population cooperates with the individuals of the other. The goal of this work is to analyze the results obtained by L-Co-R comparing with other methods from the time series forecasting field. For that, 20 time series and 5 different methods found in the literature have been selected, and 3 distinct quality measures have been used to show the results. Finally, a statistical study confirms the good results of L-Co-R in most cases.

Paper “Testing the Differences of Using RGB and HSV Histograms During Evolution in Evolutionary Art” in ECTA

This week we are presenting the paper “Testing the Differences of Using RGB and HSV Histograms During Evolution in Evolutionary Art” in the Evolutionary Computation Theory and Applications.

This is the work we developed in the Hackathon of the Spanish Free Software Contest of the University of Granada with the help of several students of our university (who are also authors!).

In this work we have added Processing to our OSGiLiath (service oriented architecture for evolutionary algorithms) framework to generate images from individual representations to work with generative art. The fitness is the equality to a predefined image. HSV, RGB and a combination of both have been used.

The abstract:

This paper compares the use of RGB and HSV histograms during the execution of an Evolutionary Algorithm. This algorithm generates abstract images that try to match the histograms of a target image. Three different fitness functions have been used to compare: the differences between the individual with the RGB histogram of the test image, the HSV histogram, and an average of the two histograms at the same time. Results show that the HSV fitness also increases the similarities of the RGB (and therefore, the average) more than the other two measures.

And here is the poster:

ecta