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

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:

Call for papers: Natural Computation Special Issue on Distributed Evolutionary Computation in Informal Environments

Introduction

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.
Thus, the main topics of the workshop are (but will not be limited to):

• Performance prediction and analysis
• New computing paradigms
• Practical applications
• Implementations

Call for papers

The papers should be related to evolutionary computation and other bioinspired metaheuristics such as ant colony optimization algorithms and particle swarm systems.

• 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 of the workshop are sought, as well as those that present a framework that is based on an informal computing environment.

Deadline

UpdateDeadline for submission is February 15th. Papers will be submitted through the Natural Computing system, by selecting this special issue (SI: Informal Environments) as “Article Type”. Authors from the IWDECIE workshop are specially invited, and their reviews will be taken into consideration.

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 la Vega, University of Extremadura
David Corne, Heriot-Watt University

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.

Dynamic Control in Evolutionary Algorithms

Last Friday, in our weekly meeting, the paper by Di Tollo et al. “From Adaptive to More Dynamic Control in Evolutionary Algorithms” was presented and discussed. This work in centered on the adaptation of application rates of different types of crossover. A performance function is defined that takes into account the quality of solutions and diversity generated by each crossover. By varying a user-defined variable (teta), the importance of each factor can be regulated in order to set the desired compromise between quality and diversity (which gives rise to the idea of applying a multi-objective approach here). Then, after credit assignment (for each crossover), an operator is selected by Probability Matching (PM) or Multi-Armed Bandit (MAB) strategies.

For testing the proposed scheme, the authors define a framework with 20 different crossover operators of which the main characteristics are known (i.e., whether they favor intensity/exploitation or diversification/exploration). The system is applied to SAT problems. Several conclusions are drawn from those simple experiments. First, the type of SAT problem greatly influences the behavior of the system, as well as the criteria used to compute the performance of the operator and the selection strategy (PM or MAB). That is, setting teta to a hypothetical compromise value between intensification and diversification leads to a variety of different behaviors and not necessarily to that expected compromise.

The second part of the experiments is focused on the dynamic variation of teta. The authors conclude that the variation strategy influences the behavior of the algorithm and the progress of the system. They also conclude that, in fact, it is possible to favor diversity-oriented crossover or quality-oriented crossover by tuning teta. That is, it is possible to control the desired features by changing the teta value during the search.

[EuroGP'2011] A Peer-to-Peer Approach to Genetic Programming

Right today, April 28th, we have been presenting the paper “A Peer-to-Peer Approach to Genetic Programming” in EuroGP 2011  held in Torino, Italy within the Evo* conference series.  You can find below the abstract and the presentation of the work.

This paper proposes a fine-grained parallelization of the Genetic Programming paradigm (GP) using the Evolvable Agent model (EvAg). The algorithm is decentralized in order to take full-advantage of a massively parallel Peer-to-Peer infrastructure. In this context, GP is particularly demanding due to its high requirements of computational power. To assess the viability of the approach, the EvAg model has been empirically analyzed in a simulated Peer-to-Peer environment where experiments were conducted on two well-known GP problems. Results show that the spatially structured nature of the algorithm is able to yield a good quality in the solutions. Additionally, parallelization improves times to solution by several orders of magnitude.

Talk about parameter setting in Evolutionary Algorithms

Next friday I’ll give a talk about parameter control and parameter tunning (focusing in the latter) in EAs. I’ve read several papers of professor A. E. Eiben, about this interesting area and I will explain the differences among several kinds of parameters, different classification of settings and the state of the art with examples. You are all invited.

Date: Friday 15th. 12:00 pm.

Place: Sala de Juntas, ETS. Ingenierías en Informática y Telecomunicación. Universidad de Granada.

Pablo.