From Emergence to Emergency (exit)

Despite the hotel’s firealarm, which forced us all to leave the room, out to the “pleasant” New Orleans’ weather, when I was on slide 12, I eventually finished the presentation of this paper in the 2011 Congress on Evolutionary Computation: Fernandes, Isidoro, Barata, Merelo, Rosa, From Pherographia to Color Pherographia – Color Sketching with Artificial Ants Abstract—Ant algorithms are known to return effective results in those problems that may be reduced to finding paths through a graph. However, this class of bio-inspired heuristics have raised the interest of the artistic community as well, namely of the artists that work on the blurred border between art and science. This paper describes an extension of an ant algorithm that, although has been designed as an edge detection tool and a model for collective perception, has also been used for creating artworks that were exhibited to a heterogeneous audience. The algorithm is a self-organized and stigmergic social insects’ model that is able to evolve lines along the contours of an image, in a decentralized and local manner. The result is the emergence of global patterns called pheromone maps. These maps – which were later named with the term pherographia– are grayscale sketches of the original black-and-white image on top of which the model evolves. This work goes beyond grayscale images and addresses colored pherographia, by proposing several image transformation and border selection methods based on behavioral variations of the basic algorithm.

Advertisements

The Sandpile Mutation for Genetic Algorithms

The first time we presented the Sandpile Mutation was in GECCO (Atlanta, USA), in 2008. However, that version had some limitations that in the past couple of years we have tried to overcome. The first results of this new and improved version of the Sandpile Mutation, a Self-Organized Criticality (SOC) operator for Genetic Algorithms  specifically designed for dynamic optimization, will be soon available in the LNCS volume that gathers all the contributions to the Learning and Intelligent Optimization congress, held last week in Rome. In summary, this operator uses SOC systems’ abillity to completely or partly reorganised a system after a disturbance, and evolves a varying mutation rate with a particular distribution that overcomes some of the difficulties found in dynamic optimization problems.

Here is the abstract and the presentation.

This paper describes an alternative mutation control scheme for Genetic Algorithms (GAs) inspired by the Self-Organized Criticality (SOC) theory. The strategy, which mimics a SOC system known as sandpile, is able to generate mutation rates that, unlike those generated by other methods of adaptive parameter control, oscillate between very low values and cataclysmic mutations. In order to attain the desired behaviour, the sandpile is not just attached to a GA; it is also modified in order for its conduct to reflect the stage of the search, i.e., the fitness distribution of the population. Due to its characteristics, the sandpile mutation arises as a promising candidate for efficient and yet simple and context-independent approach to dynamic optimization. An experimental study confirms this assumption: a GA with sandpile mutation outperforms a recently proposed SOC-based GA for dynamic optimization. Furthermore, the proposed method does not increase traditional GAs’ parameter set.

Recent papers

These are some of the papers I published last year. Themes: Genetic Algorithms, Sleep Classification, and Self-Organization.

Fernandes, Merelo, Rosa, Investigating Replacement Strategies for the Adaptive Dissortative Mating Genetic Algorithm, in Proceedings of the 2nd Joint Conference on Computational Intelligence, 2010

Abstract:

This paper investigates the effects of modifying the Adaptive Dissortative Mating Genetic Algorithm (ADMGA) replacement strategy on the performance of the algorithm in dynamic problems. ADMGA is a variation of the standard GA with a mating restriction based on the genotypic similarity of the individuals. Dissimilar individuals mate more often than expected by chance and, as a result, genetic diversity throughout the run is maintained at a higher level. ADMGA was previously tested in dynamic optimization problems with promising results: the algorithm shows to outperform standard GAs and state-of-the-art approaches on several problems and dynamics. However, the performance of the algorithm degrades when the frequency of changes increases. Due to the premises under which ADMGA was tested, it has been argued that the replacement strategy that emerges from the algorithm’s dissortative mating strategy may be harming the performance in such situations. This study proposes alternative replacement schemes with the objective of improving ADMGA’s performance on fast changing environments (without damaging the performance on slower ones). The strategies maintain the simplicity of the algorithm, i.e., the parameter set is not increased. The replacement schemes were tested in dynamic environments based on stationary functions with different characteristics, showing to improve standard ADMGA’s performance in fast dynamic problems.

Mora, Fernandes, Herrera, Castillo, Merelo, Rosa, Sleeping with Ants, SVMs, Multilayer Percepetrons and SOMs, ISDA’10, 2010

…and a paper that was presented (not published) at a workshop in PPSN 2010 (held in Krakow), and of which an enhanced version will be present next week in Rome (at LION’11) and published in a LNCS volume.

Fernandes, J.L.J. Laredo, J.J. Merelo and A.C. Rosa, A Self-Organized Criticality Online Adjustment of Genetic Algorithms’ Mutation Rate, Workshop on Self-Tuning, Self-Configuring and Self-Generating Search Heuristics (Self* 2010), 2010

Abstract:

This paper describes an alternative mutation control scheme for Genetic Algorithms (GAs) inspired by the Self-Organized Criticality (SOC) theory. The strategy, which mimics a SOC system known as sand pile, is able to generate mutation rates that, unlike those generated by other methods of adaptive parameter control, oscillate between very low values and cataclysmic mutations. In order to attain the desired behaviour, the sandpile is not just attached to a GA; it is also modified in order for its conduct to reflect the stage of the search, i.e., the fitness distribution of the population. Due to its characteristics, the sandpile mutation arises as a promising candidate for efficient and yet simple and context-independent approach to dynamic optimization. An experimental study confirms this assumption: a GA with sandpile mutation outperforms a recently proposed SOC-based GA for dynamic optimization. Furthermore, the proposed method does not increase traditional GAs’ parameter set.

Drawing by Ants

My paper Pherographia: Drawing by Ants appears in the current volume and issue of Leonardo Journal (Vol.43, issue 2). Here is the abstract:

ABSTRACT: This paper addresses the hypothetical relationship of photography and so-called pheromone maps created by an artificial life system that simulates an ant colony and causes its activity to evolve based on the contours of images. Pheromone—used by ants to communicate via the environment—is also simulated, and from the communication and interaction of the swarm with the environment (an image) there results a kind of drawing made with the simulated pheromone. Since ants are able to detect the edges of the image, the outcome is a sketch that resembles the original image, as with old camera obscura drawings. This text explores the observable traits shared by the photographic process and the swarm’s pheromone maps. The theme is discussed in the context of the emergent artificial art research field; recent theoretical advances that link swarm intelligence and cognitive sciences are also addressed.

Carlos M. Fernandes

Diversity-enhanced Genetic Algorithms for Dynamic Optimization

Yesterday, in Lisbon, I defended my PhD thesis on Evolutionary Algorithms for dynamic optimization.  The pdf of the document is here, and this is the abstract:

Many industrial applications have dynamic components that lead to variations of the fitness function and Genetic Algorithms (GAs) adaptiveness is an appropriate tool to solve this type of problems. The thesis proposes two new evolutionary methods to tackle dynamic problems. The first acts upon mating and avoids crossover between similar individuals, via a self-regulated mechanism, thus preserving genetic diversity. The second is a new mutation operator able to evolve self-regulated mutation rates with a particular distribution that is suited for dynamic optimization. Finally, an efficient hybrid method that combines both strategies is proposed. The objective and main claim is the possibility of designing nature-inspired protocols for GAs that are efficient when evolving on dynamic environments while preserving algorithms’ complexity and not requiring a priori information about the problem.

The proposals are tested on a wide range of problems and are able to outperform frequently other GAs, namely when the frequency of change is lower. The hybrid scheme proves to be particularly effective since it broadened the range of dynamics in which each method by itself excels. As projected, the proposed techniques are robust and do not increase parameters’ set, thus fulfilling necessary conditions for real-world applications.

Carlos M. Fernandes

ECAL 2009

Last week I went to Budapest to present the paper “An Ant-Based Rule for UMDA’s Update Strategy” in the 10th European Conference on Artificial Life (ECAL 2009). ECAL is one of the leading congresses in the area and some of the most relevant work in the Artificial Life research field is presented there in first hand. It is held every two years and this time the capital of Hungary was chosen to host the event. The Academy of Sciences, in Roosevelt tér (square), on the banks of the Danube and with a perfect view on the Castle and the hills of Buda was ECAL’s headquarters for 4 days.

Only 30% of the accepted papers were selected for oral presentation. The remaining was scheduled for poster sessions (although all the accepted papers were published in full-length in two LNCS volumes) that lasted…the whole day! I cannot understand why not all the congresses follow a line similar to PPSN (a poster-only congress, with 90 minutes sessions) when it comes to poster sessions, but ECAL’s strategy is, my opinion, particularly ineffective and exhausting.

As for our paper, it presents a study on an alternative update strategy for the Univariate Marginal Distribution Algorithm based on the ACO computational paradigm and first presented here. The aim is to control the balance between exploration and exploitation in order to avoid diversity loss, reduce the optimal population size and improve the scalability of the algorithm on hard problems. The results confirmed the hypothesis. This is the abstract:

This paper investigates an update strategy for the Univariate Marginal Distribution Algorithm (UMDA) probabilistic model inspired by the equations of the Ant Colony Optimization (ACO) computational paradigm. By adapting ACO’s transition probability equations to the univariate probabilistic model, it is possible to control the balance between exploration and exploitation by tuning a single parameter. It is expected that a proper balance can improve the scalability of the algorithm on hard problems with bounded difficulties and experiments conducted on such problems with increasing difficulty and size confirmed these assumptions. These are important results because the performance is improved without increasing the complexity of the model, which is known to have a considerable computational effort.

Authors: Carlos M. Fernandes, Claudio F. Lima, J.L.J. Laredo, J.J. Merelo and A.C. Rosa

Inside [Art and Science]

Inside gathers 22 artists that interact with science, and aims at bridging the gaps between natural sciences and humanities. The exhibition opens at Cordoria (Lisbon) on the September 24. I will contribute to the it with an artwork based on Pherographia, and also with a text on art, science and consilience that will appear in the catalogue:

When once asked what he would have liked to be if not a neurologist, Egas Moniz (1874-1955) replied: a painter, if I just had the skills. This statement, which is not surprising for those who are aware of the tight links between art and science and the related nature of scientific and artistic creativity, is the perfect starting point for some thoughts on the role (and the meaning) of talent, not only in art, but also in the realm of scientific research and development. The discussion will drive us to through the importance of talent and creativity in art and in the contemporary movements that merge it with science, of which artificial art is one of the branches.

Carlos M. Fernandes