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

Advances in Evolutionary Algorithms

The book Advances in Evolutionary Algorithms, published by IN-TECH, is already online, with open acess. There you find the chapter Evolutionary Algorithms with Dissortative Mating on Static and Dynamic Environments, authored by me and Agostinho C. Rosa.

(…)

Non-random mating, which encloses different kinds of strategies based on parenthood or likeness of the agents involved in the reproduction game, is frequently found in natural species, and it is believed to be predominant among vertebrates. Humans, for instance, mate preferentially outside their family tree: this non-random mating scheme is called outbreeding and has its opposite in inbreeding, a selection strategy where individuals mate preferentially with their relatives (Roughgarden, 1979; Russel, 1998). It is often stated that inbreeding decreases the genetic diversity in a population while outbreeding increases that same diversity (Russel, 1998). In addition, inbreeding will increase the normal rate of a harmful allele present in the family. If inbreeding is extensive and intensive, homozygozity will increase in frequency and the family experiences a growth in the genetic load (measure of all of the harmful recessive alleles in a population or family line) of the harmful allele.

Assortative mating is another non-random mating mechanism, in which individuals choose their mates according to phenotypic similarities (Roughgarden, 1979; Russel, 1998). When similar individuals mate more often than expected by chance, we are in presence of positive assortative mating (or assortative mating in the strict sense). When dissimilar individuals mate more often, the scheme is called negative assortative mating (or dissortative mating). In humans, assortative mating is well exemplified by the correlation between heights or intelligence in partners. On the other hand, humans do not mate assortatively with respect to blood groups. This kind of behavior, which selects assortatively for some traits and not others, makes it difficult to unmask the effects of assortative mating in the population. In fact, human assortative mating is not completely positive except for some small and isolated communities (the Old Order Amish, for instance).

(…)

Carlos Miguel Fernandes

UMDAs for Dynamic Optimization Problems

by Carlos M. Fernandes, Claudio Lima and Agostinho C. Rosa

This paper investigates how the Univariate Marginal Distribution Algorithm (UMDA) behaves in non-stationary environments when engaging in sampling and selection strategies designed to correct diversity loss. Although their performance when solving Dynamic Optimization Problems (DOP) is less studied than population-based Evolutionary Algorithms, UMDA and other Estimation of Distribution Algorithms may follow similar schemes when tracking moving optima: genetic diversity maintenance, memory schemes, niching methods, and even reinicialization of the probability vectors. This study is focused on diversity maintenance schemes. A new update strategy for UMDA’s probability model, based on Ant Colony Optimization transition probability equations, is presented and empirically compared with other strategies recently published that aim to correct diversity loss in UMDA. Results demonstrate that loss correction strategies delay or avoid full convergence, thus increasing UMDA’s adaptability to changing environments. However, the strategy proposed in this paper achieves a higher performance on the DOP test set when compared with other methods. In addition, the new strategy incorporates two parameters that control the diversity of the probability model.

Carlos Miguel Fernandes

Merging Art and Science

Pherographia

(…)

Following the ideas stated in the previous section, we also designate the pheromone maps as cognitive maps. From now on, the possibilities are endless. We shall stick to the aesthetical outcome of the swarm being applied to gray-scale images and call it Pherographia: drawing by pheromones.

(At this point, it is possible to make some metaphorical links between the model and the silver salts of the traditional photographic process. Ants reinforce the “lines” by depositing more pheromone — like the chemical developer enhances the exposed silver —, while evaporation eliminates that pheromone that is no longer useful in the process of self-organization —like the fixer removes unexposed silver. Grain, in a film, appears as the result of the aggregation of silver salts when developing time is increased; the lines in this camera obscura for ants are enhanced by the constant reinforcement of pheromone over desired regions — as grain emerges from “reinforcement” of silver clusters, created by a longer developing time.)

Pherographia is a rather naïve approach to drawing. There are no shadows or highlights, only lines delimiting the main areas of the image (although some detail emerges in some regions). The ants’ drawings sometimes resemble other edge detection methods, but we still feel, when looking at the images, to be facing a children’s sketch or some neo-Palaelolithic kind of representation of reality. In that sense, Pherographia departs from Photographia. Solarization, a photographic process popularized by such artists as Man Ray (1890–1976) and László Moholy-Nagy (1895–1946), comes to mind when looking at pherographic images. Due to the discontinuities imposed by pheromone trails, pherographic representations of images that hold rich tonal gradations may also resemble cloisonnism (if one mentally fills the blank regions with colors). Perhaps the most notable artist that engaged in such style was the post-impressionist painter Paul Gauguin (1848-1903), who was influenced by Japanese Ukiyo-e prints. As stated by Roy R. Behrens*:

There is a persuasive resemblance between gestalt principles and the Japanese-inspired aesthetics.

Gestalt principles also show some resemblances with Swarm Intelligence studies. Both aim at understanding how local perceptions become organized into wholes, and this it is precisely what happens in the ant system discussed in this paper: the restricted perception of individual ants gives rises to a global perception of the environment. A braid appears to arise that embraces all these concepts.

(…)

*R. R. Behrens, “Art, Design and Gestalt Theory”, Leonardo Vol. 39, No. 4, pp. 299-303 (1998).

Technical stuff (and inspiration) in:

1. 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).

2. 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 2^nd International Workshop on Ant Algorithms, pp. 113-116 (2000).

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

and my website on Photography.

Carlos Miguel Fernandes

The Crank Scientists

Let me try to sum up. On the one hand, we have a large number of true but commonplace ideas, especially about how simple rules can lead to complex outcomes, and about the virtues of toy models. On the other hand, we have a large mass of dubious speculations (many of them also unoriginal). We have, finally, a single new result of mathematical importance, which is not actually the author’s. Everything is presented as the inspired fruit of a lonely genius, delivering startling insights in isolation from a blinkered and philistine scientific community. We have been this way before.

[Some cranks] are brilliant and well-educated, often with an excellent understanding of the branch of science in which they are speculating. Their books can be highly deceptive imitations of the genuine article — well-written and impressively learned….
[C]ranks work in almost total isolation from their colleagues. Not isolation in the geographical sense, but in the sense of having no fruitful contacts with fellow researchers…. The modern pseudo-scientist… stands entirely outside the closely integrated channels through which new ideas are introduced and evaluated. He works in isolation. He does not send his findings to the recognized journals, or if he does, they are rejected for reasons which in the vast majority of cases are excellent. In most cases the crank is not well enough informed to write a paper with even a surface resemblance to a significant study. As a consequence, he finds himself excluded from the journals and societies, and almost universally ignored by competent workers in the field….. The eccentric is forced, therefore, to tread a lonely way. He speaks before organizations he himself has founded, contributes to journals he himself may edit, and — until recently — publishes books only when he or his followers can raise sufficient funds to have them printed privately.Thus Martin Gardner’s classic description of the crank scientist in the first chapter of his Fads and Fallacies. In lieu of superfluous comments, let us pass on to Gardner’s list of the “five ways in which the sincere pseudo-scientist’s paranoid tendencies are likely to be exhibited.”

1. He considers himself a genius.
2. He regards his colleagues, without exception, as ignorant blockheads. Everyone is out of step except himself….
3. He believes himself unjustly persecuted and discriminated against….
4. He has strong compulsions to focus his attacks on the greatest scientists and the best-established theories. When Newton was the outstanding name in physics, eccentric works in that science were violently anti-Newton. Today, with Einstein the father-symbol of authority, a crank theory of physics is likely to attack Einstein in the name of Newton….
5. He often has a tendency to write in a complex jargon, in many cases making use of terms and phrases he himself has coined….

(1) is clearly true. (2) is clearly true. (3) is currently false, or at least not much on display in this book. (4) is clearly true, though Wolfram, befitting someone who was once a respectable physicist, aims to undermine Newton and Einstein, indeed the entire tradition of physical science since Galileo. (5) is true only to a very small degree (mercifully).

When the crank’s I.Q. is low, as in the case of the late Wilber Glenn Voliva who thought the earth shaped like a pancake, he rarely achieves much of a following. But if he is a brilliant thinker, he is capable of developing incredibly complex theories. He will be able to defend them in books of vast erudition, with profound observations, and often liberal portions of sound science. His rhetoric may be enormously persuasive. All the parts of his world usually fit together beautifully, like a jig-saw puzzle.The natural result is a cult following. Wolfram certainly has that, to judge from his sales, the attendance at his “New Kind of Science” conventions, and the reader reviews on Amazon. (I presume they are not all a claque hired by Wolfram Media.) This frankly is part of a disturbing trend, pronounced within the field of complex systems. In addition to Wolfram, I might mention the cult of personality around Ilya Prigogine, and Stuart Kauffman’s book Investigations, or even the way George Lakoff uses “as cognitive science shows” to mean “as I claimed in my earlier books”.

Cosma Shalizi, on Stephen Wolfram and his book A New Kind of Science

Unfortunately, the world of science is full of cranks. To make things worse, only a few of them are “brilliant thinkers”, as Cosma Shalizi admits it when referring to Wolfram. The rest are just a bunch of frustrated scientists, trying to reach the top by engaging in irrelevant research, disguised as novelty or new science (the “so what” research, if you allow me to steal the expression from Agostinho). We all know a few of them.

(On another field of knowledge, one could question if the overrated philosopher Friedrich Hegel, the master of jargon, was not some kind of crank. Well, he sure founded a perverse way of “thinking”, and we shall not discard the hypothesis that he was the father of all the Wolframs in this world. Furthermore, his dependence on the political establishment – the King of Prussia, Frederick William III – somehow reminds us that the decline of Though in western civilization – of which we are now more aware – in the beginning of the XXI century, is mainly due to the gradual loss of independence from the political power. We are treading dangerous paths, when accepting public funding for research that not only comes with rules and directives from governments and burocrats, but also reflects modern trends that are more devoted to ideology, utopia or prejudice, than to the methods of modern science. Just try to submit a project that aims at refuting the theory of the anthropogenic origins of the global warming, and then you will know what I mean.)

Carlos Miguel Fernandes