A new Bak-Sneppen Model in ECAL

We have been in this year’s edition of the European Congresso on Artificial Life (ECAL 2013) with the paper «Adapting the Bak-Sneppen Model to a Dynamic and Partially Connected Grid of Hierarchical Species». The work reports the investigations on a variation of the Bak-Sneppen model of co-evolution between interacting species. In this version, the species are randomly distributed in a 2D lattice and move through the nodes according to a simple set of rules based on hieracharchy and similarity between the species’ fitness values. Emergent patterns are detected and discussed. The paper can be downloaded here.

This paper describes and investigates a swarm intelligence system with similarity-oriented behavioral rules, hierarchical clustering and evolution by random mutation. The evolutionary scheme is based on the Bak-Sneppen model of co-evolution between interacting species. The swarm of species, in this case, is randomly distributed on a 2-dimensional grid of nodes. The number of nodes is larger than the swarm size and the species are allowed to move on the grid. The rule that defines the movement of the species through the gird is based on the similarity between the species’ fitness values and the ranking of those same values within the entire population. Meanwhile, the fitness values are modified using the rules of a 2-dimensional Bak-Sneppen model. The system is intended to be a framework for metaheuristics with spatially structured populations and we show that it displays the desired characteristics for that purpose. Furthermore, these characteristics emerge as global patterns from the local interaction of the species. Without requiring the tuning of control parameters to precise values, the system seems to self-organize into a critical state between randomness and order.

Partially Connected Topologies for Particle Swarms

One of our most recent research lines deals with network topologies for the Particle Swarm Optimization algorithm (PSO). We have been studying dynamic and partially connected topologies and the first results are reported in two papers recently published in CEC and GECCO: Partially Connected Topologies for Particle Swarm (GECCO) and A Study on Time-Varying Partially Connected Topologies for the Particle Swarm (CEC). We have concluded that a random and dynamic partially connected grid topology with von Neumann neighborhood is able to perform more consistenly than tradicional configurations. This is the abstract of the paper published in the CEC proceedings:

This paper presents a study on the effects of dynamic and partially connected 2-dimensional topologies on the performance of the particle swarm optimization (PSO). The swarm is positioned on 2-dimensional grids of nodes and the particles move through the nodes according to a simple rule. Meanwhile, the von Neumann neighborhood is used to decide which particles influence each individual. Structures with growing size are tested on a classical benchmark and compared to several configurations such as lbest, gbest and the standard von Neumann configuration. The results show that the partially connected grids with von Neumann neighborhood structure performs more consistently when compared to lbest, gbest and the standard von Neumann topology.

Self-Organized Criticality and Genetic Algorithms

Our journal paper on the Sandpile Mutation operator for Genetic Algorithms is now available online: C.M. Fernandes, J.L.J. Laredo, A.C. Rosa, J.J. Merelo, “The sandpile mutation Genetic Algorithm: an investigation on the working mechanisms of a diversity-oriented and self-organized mutation operator for non-stationary functions“, Applied Intelligence, February 2013.

Abstract: This paper reports the investigation on the sandpile mutation, an unconventional mutation control scheme for binary Genetic Algorithms (GA) inspired by the Self-Organized Criticality (SOC) theory. The operator, which is based on a SOC system known as sandpile, is able to generate mutation rates that, unlike those given by other methods of parameter control, oscillate between low values and very intense mutations events. The distribution of the mutation rates suggests that the algorithm can be an efficient and yet simple and context-independent approach for the optimization of non-stationary fitness functions. This paper studies the mutation scheme of the algorithm and proposes a new strategy that optimizes is performance. The results also demonstrate the advantages of using the fitness distribution of the population for controlling the mutation. An extensive experimental setup compares the sandpile mutation GA (GGA_SM) with two state-of-the-art evolutionary approaches to non-stationary optimization and with the Hypermutation GA, a classical approach to dynamic problems. The results demonstrate that GGA_SM is able to improve the other algorithms in several dynamic environments. Furthermore, the proposed method does not increase the parameter set of traditional GAs. A study of the distribution of the mutation rates shows that the distribution depends on the type of problem and dynamics, meaning that the algorithm is able to self-regulate the mutation. The effects of the operator on the diversity of the population during the run are also investigated. Finally, a study on the effects of the topology of the sandpile mutation on its performance demonstrates that an alternative topology has minor effects on the performance.

ICCS’12 – Swarms, Complexity and Art

We have just back from the International Congress on Complex Systems, held in Agadir, Morocco, were we have presented the papers «Swarm Art with KANTS» and «Towards a 2-dimensional Self-organized Framework for Structured Population-based Metaheuristics». The first one continues our line of work with the KANTS algorithm as a swarm art tool and describes drawings generated by data extracted from photographs.

Original photos and respective pherogenic drawings by the KANTS algorithm

The second paper, which opens a new line of research, describes a swarm system that, guided by simple rules and with no central coordination, is driven to a state in which global patterns emerge. In that state, the components of the swarm self-organize into highly dynamic clusters. We show that the system is unpredictable and robust. We also demonstrate that the system’s variables (averaged clustering degree and averaged distance between neighboring components) dysplay 1/f noise. The abstract:

This paper proposes a swarm intelligence framework for distributed population-based metaheuristics that uses stigmergy and similarity measures as basic modeling rules with a local range of action for structuring the neighborhood. The system ­– which can be described as a cellular automaton with short-term memory – displays complex and emergent behavior whose most visible trait is the self-organization of a population of particles into dynamic clusters. These clusters tend to gather similar particles (similarity here is measured as the algebraic difference between randomly assigned fitness values). During the execution of the algorithm, the particles move through a grid of nodes leaving a mark with the fitness value of the particle in each node they visit. When deciding where to move, the particles take into account the marks in the neighborhood and tend to travel to nodes with marks that minimize the difference between the particle’s fitness and the mark’s fitness. A kind of hierarchical behavior is also modeled by forcing the particles to move toward nodes with better fitness values. We show that these simple rules conduct the system to a critical state in which clusters are constantly created and broken, while maintaining a typical pattern of clusters and paths. In addition, we demonstrate that the system’s variables display  noise, which is one of the signatures of Self-Organized Criticality (SOC). Since it does not require the tuning of control parameters to precise values, we hypothesize that the proposed system converges to SOC.

The presentation:

ECTA (2) – Swarm Art with KANTS

The second paper we have presented last weekend in Barcelona (ECTA 2012), with the title “Pherogenic Drawings” (C.M. Fernandes, A.M. Mora, J.J. Merelo, A.C.Rosa), is about swarm art and describes the application of the KANTS algorithm, an ant-clustering algorithm created by our group in 2008, to data extracted from sleep electroencephalogram (EEG) signals.

We execute KANTS on a set of Hjorth parameters extracted from the EEG of sane adult humans. In the end of the run, we translate the environmental vectors of the algorithm into an RGB image. The resulting drawings are different for each patient, since the ants, in this algorithm, are the data samples, which communicate via the environmental grid of vectors and change that same environment. Therefore, a pherogenic (from pheromone+genesis) drawing is a signature of a person’s night sleep.

The results are contextualized within the swarm and generative art — a contemporary trend that blends art, science, technology — and within my own work on generative art (check the project that won the last GECCO’s competition on Evolutionary Art, Design and Creativity, also created with KANTS). The abstract:

Social insects and stigmergy have been inspiring several significant artworks and artistic concepts that question the borders and nature of creativity. Such artworks, which are usually based on emergent properties of autonomous systems and go beyond a centralized human authorship, are a part of a contemporary trend known as generative art. This paper addresses generative art and presents a set of images generated by an ant-based clustering algorithm that uses data samples as artificial ants. These ants interact via the environment and generate abstract paintings. The algorithm, called KANTS, consists of a simple set of equations that model the local behavior of the ants (data samples) in a way that, when travelling on a heterogeneous 2-dimensional lattice of vectors, they tend to form clusters according to the class of each sample. The algorithm was previously proposed for clustering and classification. In this paper, KANTS is used outside a purely scientific framework and it is applied to data extracted from sleep-Electroencephalogram (EEG) signals. With such data sets, the lattice vectors have three variables, which are used for generating the RGB values of a colored image. Therefore, from the actions of the swarm on the environment, we get 2-dimensional colored abstract sketches of human sleep. We call these images pherogenic drawings, since the data used for creating the images are actually the pheromone maps of the ant algorithm. As a creative tool, the method is contextualized within the swarm art field.

Ant the presentation:

ECTA 2012 (1) – Self-Organized Criticality and PSO (best paper award)

Last weekend we were in Barcelona presenting two papers at the 4th International Conference on Evolutionary Computation Theory and Applications (ECTA 2012). One is an extension of the work presented at PPSN in the last September and its title is “Using Self-Organized Criticality for Adjusting a Particle Swarm” (C.M. Fernandes, J.J. Merelo and A.C. Rosa). We use the Bak-Sneppen model (which is known to display Self-Organized Critically) for controlling the parameters of the Particle Swarm Optimization (PSO) algorithm. We test the proposed strategy on two different topologies for the swarm and show that the performance is very stable throughout the test set. The paper and the corresponding talk won the best paper award of the congress. This is the abstract:

The local and global behavior of Self-Organized Criticality (SOC) systems may be an efficient source for controlling the parameters of a Particle Swarm Optimization (PSO) without hand-tuning. This paper proposes a strategy based on the SOC Bak-Sneppen model of co-evolution for adjusting the inertia weight and the acceleration coefficients values of the PSO. In order to increase exploration, the model is also used to perturb the position of the particles. The resulting algorithm is named Bak-Sneppen PSO (BS-PSO). An experimental setup compares the new algorithm with versions of the PSO with varying inertia weight, including a state-of-the-art algorithm with dynamic variation of the weight value and perturbation of the particles’ positions. The parameter values generated by the model are investigated in order to understand the dynamics of the algorithm and explain its performance.

And this is the presentation:

Particle Swarm Optimization in PPSN 2012

«Controlling the Parameters of the Particle Swarm Optimization with a Self-Organized Criticality Model» (Fernandes, Merelo, Rosa) is the title of the paper we have presented last week in PPSN. The key idea of the project is to use a Self-Organized Criticallity system called the Bak-Sneppen model of co-evolutionary speciesfor controlling the parameters (inertia weight and acceleration coefficients) of the PSO, as well a pertubation factor of the particles’ positions. In this stage of the research, the model is used as a black-box that, in each iteration, feeds each particle with specific parameter values related to the model’s dynamics. The evolution of the species seemed to fit the control requirements of the PSO parameters, and, in fact, the proposed scheme attained very interesting results when compared to other control strategies. Furthermore, neither the model nor the PSO require fine-tuning: the swarm is totally controlled by the Bak-Sneppen model. The paper can be found here. The abstract:

This paper investigates a Particle Swarm Optimization (PSO) with a Self-Organized Criticality (SOC) strategy that controls the parameter values and perturbs the position of the particles. The algorithm uses a SOC system known as Bak-Sneppen for establishing the inertia weight and acceleration coefficients for each particle in each time-step. Besides adjusting the parameters, the SOC model may be also used to perturb the particles’ positions, thus increasing exploration and preventing premature convergence. The implementation of both schemes is straightforward and does not require hand-tuning. An empirical study compares the Bak-Sneppen PSO (BS-PSO) with other PSOs, including a state-of-the-art algorithm with dynamic variation of the weight and perturbation of the particles. The results demonstrate the validity of the algorithm.

Abstracting the Abstract: a swarm art project

Last Wednesday, my latest swarm-art project «Abstracting the Abstract» (with the collaboration of JJ Merelo and Antonio Mora) won the GECCO Evolutionary Art, Design and Creativity Competition. The work is based on KANTS, a ant algorithm for clustering and classification that was proposed by our research group in 2008. Early this year, I started using KANTS as a generative art tool, by trying to generate 2-dimensional representations of human sleep. The first results will be presented in October in the ECTA2012. «Abstracting the Abstract» goes one step further and uses famous abstract paintings as input samples to the KANTS algorithm. The result is the swarm’s «interpretation» of the painting. Here and here you’ll find, respectively, the artist statement and the technical paper. Below you’ll find an example of a swarm painting, as well as GECCO’s presentation.

Carlos M. Fernandes, Abstracting the Abstract #5 (after Miró)

Histograms for Comparing Evolutionary Algorithms

Last Friday we were discussing the paper by Tirronen and Weber, «Sparkline Histograms for Comparing Evolutionary Algorithms«, presented at IJCCI 2010. This work proposes histograms that represent the distribution of values in the set of results for comparing the performance of Evolutionary Algorithms. Such a visual comparison provides a quick evaluation of the relative performance of the algorithms in a test set, as well as the overall performance of each one. Some patterns of the histograms permit to identify features such as lack of robustness, high rate of convergence to local optima, and high standard deviation. Altough this method does not replace numerical and statistical comparisons, it may be helpfull in the analysis of Evolutionary Algorithms, so we suggest you to take a look at the work of Tirronen and Weber.

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.