Professor Hans-Paul Schwefel Will Receive The Frank Rosenblatt Award 2011

From the press release:

"The 2011 IEEE Frank Rosenblatt Award will be presented at CEC 2011 (www.cec2011.org) to Dr. Hans-Paul Schwefel, Professor Emeritus, Chair of Algorithm Engineering, Faculty of Computer Science, Dortmund University of Technology, Dortmund, Germany for pioneering contributions to evolutionary computation through the theory and application of evolution strategies. Schwefel is a German computer scientist and professor emeritus at Dortmund University of Technology, where he held the chair of systems analysis from 1985 until 2006. He is one of the pioneers in evolutionary computation and one of the authors responsible for the evolution strategies. His work has helped to understand the dynamics of evolutionary algorithms and to put evolutionary computation on formal grounds.

Congratulations, Professor Hans-Paul Schwefel!

The Vision Of An Evolutionary Computation Pioneer

Photo By Juan Julián Merelo Guervós

----------------------------------------

The post below is a translation from a Spanish posting made by Carlos and put on-line at his blog (La Singularidad Desnuda). See here for the original post.

The text has to do with Professor Hans-Paul Schwefel talk at last EvoStar delivered earlier this year. I should have made the translation much before, but I was unaware of it until yesterday. Despite the delay, Carlos' text is a very good overview concerning what was said during the talk and a valuable one because reports what a person who lived all the development process of an evolutionary algorithm witnessed along that time. I added some date corrections and two pictures I got from Juan Julián Merelo Guervós Flickr album. Thank you for the pictures, JJ!

Thank you very much Carlos for permiting me translating your original text!

I hope you enjoy it!

----------------------------------------


One of the best moments during the last week EvoStar event was Professor Hans-Paul Schwefel talk. For an evolutionary computation outsider, it must be said that the three main evolutionary computation branches arose almost simutaneously and in three different places, the algorithms are the following: genetic algorithms (GA); evolutionary programming (EP); and evolution strategies (ES). These last ones were created in Germany during the middle 1960s. Professor Schwefel is one of the creators - together with Professor Ingo Rechenberg (Peter Bienert also contributed with mechanical experiments) - of the first evolution strategy version, the so called two membered elistist evolution strategy or (1 + 1)-ES - later, Professor Schwefel would add more features, such as the self-adaptation mechanism as we know it nowadays and the comma selection scheme. Professor Schwefel is one of the evolutionary computation field pioneers and the talk was named "A Pioneer's View Onto Evolutionary Computation". The talk was very valuable, not exactly by the technical aspects (which were not the main talk focus), but because of the personal perspective Professor Schwefel approached.

Below there is a picture of what the TUB evolution technique working group (Schwefel, Rechenberg, and Bienert) made during the evolution strategies' early years.



Such a talk must be structured through a temporal manner: Past, present, and future. That was the exact talk structure but taking into account an original variation: We begin with the future, going to the present, and finally reaching the past. The two initial parts were very brief. Upon the future, Professor Schwefel showed his hope of what evolutionary computation technology may achieve, however he was sensible not to make accurate predictions. After that, he clarified that part of the talk with some quotes which for some persons may sound embarrassing. The first quote was a comment made by a referee who reviewed Professor Schwefel's seminal evolution strategy work in 1970:

"There is no necessity for another optimization method [except the gradient technique]"

That is an example of a referee whose words are full of glory. The second quote came from an IBM spokesman in 1974:

"Parallel computing will not be available before the year 2000."

That is the way IBM has followed recently. Before the lights of such examples of vision of future, we only must claim that the coming years will have so many surprises concerning the capacity and application of evolutionary algorithms, mainly in hotbed fields facing problems of large complexity, such as biotechnology.

Below we see the cover of Professor Schwefel thesis Adaptive mechanismen in der Biologischen Evolution und ihr Einfluß auf die Evolutiongeschwindigkeit.



Photo By Juan Julián Merelo Guervós


The talk session dealing with the present was very brief too, and it was limited to verifing the exponential growth of the evolutionary computation community and academic production. We enter, then, in the talk part dedicated to the past, where Professor Schwefel reported his experiences in first person since the beginning of evolution strategies, the challenges faced, and all the lessons learned. The first one was "expect the unexpected", and he got it from the experiments made to find the optimal design of a nozzle. That nozzle was conceived as two funnels facing each other: By one of the entrances was injected a fluid composed of gas and a liquid subjected to high velocities, which passed through a small aperture, and was expelled at the other entrance (the nozzle exit). The objective was to achieve the maximum thrust and for that some parameters should be adjusted, such as in which point the small aperture should be put between the two entrances. Professor Schwefel had one of his first "crazy ideas" when thinking that not necessarily the two-funnels design was the optimal design, but there would be two entrances could have another forms of configuration and between them the funnels design could undergo variations, having freedom to vary their forms in three dimmesions. Applying the incipient evolution strategy technology, the following (astonishing) result was got:



The animation shows the evolution of a nozzle design since its initial configuration until the final one. After achieving such a design it was a a little difficult understanding why the surprising design was good and a team of physicists and engineers gathered to provide an investigation aiming at devising some explanation for the final nozzle configuration. Professor Schwefel also investigated the algorithmic features of evolution strategies, what made possible different generalizations such as a surplus of offspring created, the use of non-elitist evolution strategies (the comma selection scheme), and the use of recombination beyond the well known mutation operator to generate the offpsring. The second part of the talk had to do with some topics Professor Schwefel had already approached at past evolutionary computation events, such as the gap between evolutionary computation and natural evolution (static objectives, just one optimization criterion, fixed codification, synchronous evolution, etc.). Among other aspects, Professor Schwefel told about evolution strategies holding spatial structure, using predator-prey models, different gender (male/female) introduction, and diploid codification.

In short, it was an amusement attending such a talk, as much for its content as for the lecturer, a humble and an affable person which is a pleasure to talk with. Talks like that are what makes a conference be remembered along the time.

On The Analysis Of Biological Mutations

Browsing MEDAL Blogging, I got a nice link to a post at Olivia Judson's New York Times blog, see it here: A Mutual Affair.

That link was the pointer to another Olivia Judson's post: A Random Analysis. It deals with the biological nature of DNA mutations. Are they really random? Do they follow some kind of probabilistic distribution (or density) function? Are they weighted? Do small mutations happen much more often than the larger ones?

Of course, those questions are mine, not hers. :)

She states that mutations are small modification on the biological blueprint and, depending on the way they happen - small or large -, may affect seriously or not the living being's evolutionary path.

The manner through which mutations occur - be these deleting, inserting, and so on - can also affect the genome's configuration of a specimen. She says that when deletions are more frequent than insertions, the genome's configuration is prone to be compact and small, what may influence the specimen phisiology - those creatures holding small genomes own a heavy metabolic and growing rates.

Mutations are not only random, but also work different from species to species and the mutation flavours (deletion, insertion, etc.) also occur at different rates when taking into account other species. For example, in humans, deletions are more common and prominently working on DNA bases' repetitions, such as ATATAT or AGCAGCAGC. Why do mutations often occur on those repetitions? She explains:

"The reason mutations to repeated sequences are so common is that, in such repeats, it’s easy for the DNA copying machinery of the cell to slip and lose its place, and then put in too many repeats, or too few. (Even for a person, copying something like AAAAAAAA is harder than copying ACTGTCAG. Ahhh!) And although, obviously, these mutations can only happen in part of the genome where there is a repeated sequence, they happen at such a high rate that each of us probably carries as many new slippage mutations as “point mutations” — mutations that swap one base for another, say A for C."

Genomes, as Judson said, hold mutational hotspots and coldspots. These hotspots seem to be long repetitions of DNA bases, since "copying a long repeated segment without slipping is more difficult than copying a short one." Some creatures seem to have evolved their own kinds of mutational hotspots to aim for evolutionary profits - for instance, a pathogen developing the "stealth" ability before the immune system "eyes".

She advises that the manner mutations happen may trap a species in a specific evolutionary path, denying it the exploration of other evolutionary routes:

"But the mutational peppering has a consequence. As I mentioned at the start of this article, an important source of evolutionary novelty is when one member of a pair of duplicated genes evolves to take on a new function. In Neurospora [bread mold] this can’t happen: duplicated gene pairs get destroyed. Its use of mutations to defend its genome from invasion may have inadvertently blocked off some evolutionary paths."

Very nice article! :)


My Very Own Biased Comments

I think that there are so many lessons the evolutionary computation field may learn from Olivia Judson words. Of course, her small and layman article is just an initial step in that direction.

01. On Genetic Coldspots And Hotspots

For example, there is nothing in genetic algorithms that models the so-called mutational hotspots. On the contrary, take a common genetic algorithm book and the author - likely - advises you configuring the mutation rate between the range [0.0001, 0.001]. Crossover rates are set up at some point between [0.6, 0.9]. It seems that macromutations are avoided when it comes to genetic algorithms. When dealing with problems holding strong dependencies among theirs parameters, such a set up may even be harmful for the whole optimization process, since high crossover rates - along small mutation rates - tend to allow gene pool diversity losses, what can stuck the whole population in a specific local optima and/or optimization track. Sure, the GA community has made works on modelling genetic phenomena, such as gene linkage and viral infection.

Of course, detecting and handling the mutational coldspots is very valuable too, since we could avoid flipping bits (or a set of them) that must undergo small modifications or none at all.

I think that the optimization process of a given real world problem could benefit in some sense from that flavour of genetic phenomenon, since mutational hotspots and coldspots seem, at a first glance, to be useful for escaping local optima - remember: some problems require the modification of ALL parameters at same time to escape a local optimum. BUT... they could be harmful too. To avoid that drawback, mechanisms of self-adaptation could help to overtake that type of situation and could even implicitly identify mutational hotspots and coldspots, handling each one according to their respective nature.

Mutational hotspots and coldspots in non-decomposable problems should be addressed considering the relationship between those bits located at those spots and the others - sure, and between those spots' bits themselves. A well designed mutation operator would be very important here. (Again, a self-adaptation mechanism would be helpful.)

Upon the evolution without mutation, see her another nice article: Stop The Mutants!

Another important point has to do with the detection of those mutational hotspots and coldspots. Although there are some works from the Estimation of Distribution Algorithms (EDA) community handling problems that loosely resemble those genetic phenomena (see the Extended Compact Genetic Algorithm or the Hierarchical Bayesian Optimization Algorithm), they were designed under the statistical philosophy of the EDAs - an approach that throws away the genetic stuffs in genetic algorithms replacing them by statistical sampling and probabilistic distribution functions. Let alone that their bioinspired aspect is completely flawed, since in nature there is not an entity that captures data, analyses them, and etc. I guess those methods were designed much more as an optimization tool rather than intended to be a medium to increase our understanding of biological evolution. As optimization tools, those methods have a nice performance, mainly when it comes to discrete nearly decomposable problems. Summing up this paragraph: Despite a loosely resemblance between some genetic phenomena and the inner working of some EDAs, the later were not bioinspired.

For the EDA enthusiasts, I left a simple question: Is there a probability distribution that behaves in the same way mutational hotspots and coldspots do? :)

My hunch: I guess there is!

02. On Gene Deletion And Duplication

One of the few works I am aware of using abstractions of those two genetic phenomena is Professor Hans-Paul Schwefel's nozzle experiment, see it here: Optimization of a Two-Phase Nozzle with an Evolution Strategy. John Koza has used a kind of deletion and duplication too.

He got impressive results applying those genetic phenomena as an experimental optimization abstraction.






Those nozzle designs were obtained through a (1+1)-ES - without computer!

03. On Long DNA Base Repetitions

I have little to say here, since in "01" I have said a lot about a similar phenomenon. But, the way the genes interact in DNA seem to be much more important than their arrangement itself.

In the evolutionary computation realm, that problem has been addressed by linkage learning techniques in genetic algorithms and through correlated mutations in evolution strategies.

Professor Schwefel's Keynote At EvoStar

Our blog friend Juan Julián Merelo Guervós is posting about the EvoStar 2008 event.

His first post is a short summary concerning the opening keynote given by Professor Hans-Paul Schwefel, see it here.

His recent post summarizes a little bit more the keynote presented by Professor Schwefel, see here.

Very interesting posts!

Upon the future of evolutionary computation, Professor Schwefel said that "the unexpected should be expected".

Professor Schwefel also mentioned a situation when a paper reviewer commented the following: "Why should other optimization algorithms be necessary?" This comment is strongly correlated to traditional optimization methods and the development of the evolution strategies, since some researchers - along the 1960s and 1970s - thought that gradient-based methods and others techniques (such as Gauss-Seidel method) were all the stuffs they needed.

He also spoke of the application of evolution strategies (under the form of the so-called experimental optimization) to a two-phase flashing nozzle optimization, which was performed without computers! Even today, it is not possile to calculate what happens within such nozzle: thermodynamically far away from equilibrium, drag between slow water droplets and fast steam, three-dimensional turbulent boundary layer with liquid sublayer, supersonic behind nozzle throat, etc.

There were several challenges to be overtaken when preparing the grounds to the evolution strategy, such as self-adaptation, non-elitist selection method, parallelism, and so on. He obtained inspiration in natural systems to implement solutions to those problems.

An important comment that evolutionary computation researchers should pay attention:

"He's commented that evolutionary algorithms are getting less bio-inspired in time, this is not good or bad, but it's more interesting for him to look at models than to have super-tweaked ultra-tuned purportedly bio-inspired algorithms."

An Interview With Ingo Rechenberg

Here you are an interesting interview with Ingo Rechenberg, see here.

The interview concerns his speech upon biological paradigms applied to engineering and technology: The Future Becomes More Biological - A Bionik World in the Year 2099.

There is a video too, see here

His speech was part of the European Futurists Conference 2007.