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.

From Pherographia To Color Pherographia

View more presentations from Carlos Fernandes

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 2^nd 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

ROBOT ARTe

Recently, I was invited by Leonel Moura to write a foreword for a catalog of one of his exhibitions. The text ended up being a kind of short essay on Art and Science, with a final overview on Artificial Life and Artificial Art. (The book may be ordered at Moura’s website.)

In science, as in art, inspiration is the milestone that marks the beginning of another journey of hard work and exhaustive study. The famous anecdote of Isaac Newton’s (1643-1727) apple is the perfect symbol of inspiration or creative leap, be it artistic or scientific — if it is possible to distinguish them. The hidden part that suddenly enlightens the whole; the cement that gives consistency to disperse thoughts; the decisive step that puts an end to a trembling walk. These are the meanings of Newton’s apple or Archimedes’s (c. 287 BC-c. 212 BC) bath (eureka!). Albert Einstein’s (1879-1955) dream of the solution to the general theory of relativity or François Jacob’s (b.1920) glimpse of how genes work together to make life possible (while enjoying a play in a Paris theatre) are some of the 20^th century’s expressions of this old “tradition”. Art, although it is less dependent on rules and verification, is also punctuated by creative leaps.

Take for instance Wassily Kandinsky (1866-1944), when he said that his Painting With a Circle (1911) was the first abstract painting. He was categorizing the result of an ongoing (personal) process of denaturalizing motifs, but in that particular work, unlike the preceding and some of the following, a radical change occurred: we no longer recognize any figure besides the circles, a shape that remained constant throughout the abstract period of his work. Apparently, Painting with a Circle was not one of Kandinsky’s favorite works at the time, and only later he acknowledged the real implications of his breakthrough. And Jackson Pollock (1912-1956) didn’t start his career by dripping paint over a canvas on the floor. On the movie Pollock (2001), Lee Krasner (his wife, played by Marcia Gay Hardner), when seeing the painter’s first work with that newly found technique, said you’ve done it, Pollock. You’ve cracked it wide open. That (dramatized) scene portrays the well-established notion of the artist cracking it wide open after a foretaste of inspiration.

But the leap is not the only link between art and science. In both we recognize that the preparation and meditation, on a problem or a feeling, precedes the creative burst; and, after the enlightenment, comes the confirmation or development of the concept. Many “beautiful” theories are thrown away without even being published, that is true, but the same happens in the artistic realm with its exasperating dead ends. When succeed in the first steps, the scientist gains insight into the subject matter through testing the theory and submitting it to methodological falsification. An artist goes deep into the subject, enhances his ideas, and sharpens his view. Chance, or randomness, also plays a crucial rule in this whole process. Many ideas are dealt with, and then discarded. Artists and scientists know what is facing an inglorious ending for a promising thought. That cognitive spark — the leap — that allows us to solve a problem, jump into the next stage, or broaden our artistic horizons is probably a matching part of two very similar methods, if not identical.

On the other hand, it is the notion of creative leap that leads many philosophers and scientists to doubt the algorithmic essence of mind, as if the evolutionary process could not create a system capable of that sudden enlightenment, or intuition. Some support their objections on quantum physics; others will stick to the vague concept of holism. But unless we believe in “skyhooks” (an expression coined by Daniel Dennett to describe a source of complexity which has not been driven by evolution), there seems to be no way around a computational representation of the mind, at least if we regard connectionism and self-organization as an extension of that line of thought and not as opposing theories. In fact, the sciences of complexity — the discipline that studies complex adaptive system and the emergence of complex behaviour — have provided not only a new breath to the old artificial intelligence and robotics fields of research, too much dependent on the manipulation of symbols associated with the GOFAI (Good-Old-Fashioned-Artificial-Intelligence), but they also contributed to an alternative view of the human mind. Nowadays, complexity and (new) connectionism are shedding some light on this problem and are gradually erasing the mysticism around emergent and complex behaviour. We will address these issues later. First, let us look at a few dialogues between art and science throughout History. (…)

Carlos M. Fernandes

An Ant-based Rule for UMDA’s Update Strategy

by C. M. Fernandes, C. F. Lima, J.L.J. Laredo, A.C. Rosa, and J.J. Merelo

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.

To appear soon at the European Congress on Artificial Life (ECAL 2009)

Carlos M. Fernandes

A Camera Obscura for Ants

A short version of a paper I recently wrote on the concept of pherographia, called A Camera Obscura for Ants, appears in the last issue of SIGEVOlution, SIGEVO‘s newsletter . Here.

Carlos M. Fernandes, Fernando Pessoa, 2008

Carlos Miguel Fernandes