Acerca de cfernandes81

Carlos M. Fernandes was born in Luanda in 1973 and lives in between Lisbon, Portugal, and Granada, Spain. He graduated (Technical University of Lisbon, 1998) in Electrotechnics Engineering and owns a master degree in the same field since 2002 (Technical University of Lisbon). He is currently pursuing a Ph.d. on Bio-inspired Computing. From 2001 to 2005 he was an assistant at Instituto Politécnico de Setúbal. (He is also a photographer and photography teacher.) Bio-inspired Computing is his major field of research: Genetic Algorithms, Estimation of Distribution Algorithms, Ant Colony Optimization, Particle Swarm Optimization and other metaheuristics. He is particularly interested in the hybridization of Bio-inspired Computing techniques with Self-Organization, Self-Organized Criticality Models and diversity maintenance strategies. In the present, Dynamic Optimization Problems are his mains target for applying such techniques. website: www.carlosmfernandes.com email: c.m.fernandes.photo@gmail.com

Back to Basics

Sometimes we tend to forget that:

Whatever the specific approach, competent, scalable genetic algorithm performance can only be obtained when building block linkage information is already in the problem coding or is identified before or during the genetic algorithm’s search. The scalability of genetic algorithms depends critically on the representation. Once the appropriate schemata are identified, the problem becomes “mixing-easy”, and fast, reliable, scalable evolutionary computation can be achieved.

Dirk Thierens, Scalability of Simple Genetic Algorithms, Evolutionary Computation, 331-352, 1999

And we shouldn’t…

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.

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.

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.

Parameter Tuning Again

Tomorrow’s seminar is again about parameter tuning. This time, we’ll discuss the paper “From Adaptive to More Dynamic Control in Evolutionary Algorithms”, by Di Tollo et al., presented last week at the Evo* congress, in Torino. Here’s the abstract:

Adaptive evolutionary algorithms have been widely developed to improve the management of the balance between intensification and diversification during the search. Nevertheless, this balance may need to be dynamically adjusted over time. Based on previous works on adaptive operator selection, we investigate in this paper how an adaptive controller can be used to achieve more dynamic search scenarios and what is the real impact of possible combinations of control components. This study may be helpful for the development of more autonomous and efficient evolutionary algorithms.

The Sandpile Mutation Operator at Torino, Italy

Last thursday morning, at the Evo* congress, I was presenting our study on the mutation rates evolved by the Sandpile Mutation Operator, an alternative mutation scheme for GAs, specifically designed for Dynamic Optimization Problems, based on the Self-Organized Criticality Theory and the Bak-Tang-Wiesenfeld Sandpile Model.

Reactive Planning for RTS games

The paper “Reactive Planning Idioms for Multi-Scale Game AI” (Weber et al.), published last year in the proceedings of the IEEE Conference on Computation Intelligence and Games (CIG 2010), proposes a technique called reactive planning for designing a bot for Real-time strategy games (RTS). The agent is implemented in ABL (a behavioral language), an environment that allows the programmer to embed the multi-level reasoning that is required for efficient and complex RTS bots. A bot for RTS games (such as the StarCraft) must deal simultaneously with several goals, making intelligent high-level decisions while micromanaging units in combat, and ABL provides features such as daemons, messaging (memory), managers and micromanagement behaviors that can be of great help for such task. The authors propose a specific framework, for the structure of the bot and interfaces, and demonstrate that the resulting agent is able to beat the built-in StarCraft bot. However, when tested against moderately skilled human players, the agent performs poorly. As far as we understood, this work deals mainly with traditional Artificial Intelligence. The open question now is: can we model some kind of adaptive behavior in this ABL environment?

The Sandpile Mutation in Rome

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.

Pherographia in Leonardo Journal

My paper “Pherographia: Drawing by Ants”, published  last April at Leonard Journal, vol. 43 (2), is now available at my webpage, here. The paper was written two years ago, when I was still reflecting on how to integrate a swarm intelligence system that Ramos and Almeida [1] devised after the seminal model by Chialvo and Milona  [2] on my photographic body-of-work (I later contributed to speed up the process, by adding a reproduction scheme to the model [3], and, somehow, “our” KANTS algorithm [4, 5] was also inspired by Ramos and Almeida’s paper). By then I was mainly interested in the similarities between pherographia –  the term coined to describe the process – and photographia (independently of being a system that may detect the edges of photos, as you may notice if you read the paper, which is not about the model itself, but about its potential as an artistic tool, about artificial art, and the metaphors that may inspired creative artwork), based on my experience as a photographer and as a black-and-white darkroom user. In addition, I tried to contextualize my experiments and works in the artificial art trend (I think I had better results on later essays on the theme of art and science, that you may find in my webpage). This is the abstract of Leonardo’s paper:

This paper addresses the hypothetical relationship of Photography and the so-called pheromone maps created by an Artificial Life system that simulates an ant colony and evolves it on monochromatic images. Pheromone — the substance used by ants to communicate via the environment — is also simulated, and, from the communication and interaction of the swarm with the environment (image), results a kind of drawing made with the artificial pheromone. Since ants are able to detect the edges of the image, the outcome is a sketch that resembles the original picture, like the old camera obscura’s drawings. The term Pherographia — meaning drawing with pheromone — arises from the analogy with camera obscura and Photography but the text goes beyond the metaphorical links between Pherographia and Photographia and explores the observable traits shared by the photographic process and the swarm’s pheromone maps. The theme is discussed within the emergent Artificial Art research field and recent theoretical advances that link Swarm Intelligence and cognitive sciences are also addressed.

In the last two years I have created some artwork based on the swarm model (namelly, Timor Mortis Conturbat Me and The Horse and the Ants). This artwork has been exhibited to an heterogeneous audience. I expect to show soon a report on these efforts.

[1] V. Ramos, F. Almeida, “Artificial Ant Colonies in Digital Image Habitats A Mass Behaviour Effect Study on Pattern Recognition”, Marco Dorigo, Martin Middendoff and Thomas Suetzle (Eds.), Proceedings 2nd International Workshop on Ant Algorithms, pp. 113-116 (2000).

[2] D. Chialvo, M. Milonas, “How Swarms Build Cognitive Maps”, Luc Steels (Ed.), The Biology and Technology of Intelligent Autonomous Agents, No. 144, NATO ASI Series, pp. 439-450 (1995).

[3] C. M. Fernandes, V. Ramos, A. C. Rosa, “Self-Regulated Artificial Ant Colonies on Digital Image Habitats”, International Journal of Lateral Computing Vol. 2, No. 1, pp. 1-8 (2005).

[4] A. Mora, C. M. Fernandes, J.-J. Merelo, V. Ramos, J. L. J. Laredo, “KohonAnts. A Self-Organizing Ant Algorithm for Clustering and Pattern Classification”, Proceedings of the XI Artificial Life Conference, pp. 428-435 (2008).