Racing With Evolutionary Algorithms

There is an interesting comparison among different evolutionary algorithms on the control of three legged robots. From the paper abstract:

"Abstract:

Building a three legged robot is an extremely challenging task. Since three legged walking is not yet common neither in nature nor in technology it is not a priori clear what a three legged walking gait should look like. The term paper compares several techniques to find feasible gaits, using different numerical optimization strategies including IDEA, CMA-ES and Lazy Learning. All calculations have been on a specifically developed mechanics model."

See here an animation of the racing of the four robots got by the evolutionary algorithms applied.

The evolutionary algorithms applied were:

1. CMA-ES (Covariance Matrix Adaptation Evolution Strategy).

2. IDEA (Iterated Density Estimation Evolutionary Algorithm, an EDA).

3. Random Search.

4. Lazy Learning.

We can clearly see that the CMA-ES outperformed the other three evolutionary algorithms. CMA-ES is a poweful evolutionary algorithm and uses very small populations - such as two or few individuals. It can deal with problems which exhibit some or all the following features:

01. Ill-conditioning.
02. Non-separability/Non-decomposability.
03. Noise.
04. Rotation (or transformations in general) of the coordinate system.
05. Multi-modality.
06. Non-smooth.

It is well known that genetic algorithms (and other approaches) have difficulty when dealing with problems that exhibit some (or all) of those features above.

There is another animation of a solution (robot) got by the CMA-ES, see here. Click here for a summary upon the subject.


Could CMA-ES also be applied to control much more complex robots? See below some speculations.

More than three legs!




A multi-legged robot roaming through a rocky environment:




Even Martians could use a CMA-ES to control their three legged robots!



:-)

Ingo Rechenberg On Radiovisionen

There is a talk by Ingo Rechenberg, from the Technical University of Berlin - TUB, upon his research in the field of Bionics and Evolution Technique. See here (in German).

For a summary about the talk, see here.

Ingo Rechenberg - Evolution Strategies For Technical Innovation

I found a nice video interview with Ingo Rechenberg from the Technical University of Berlin - TUB. See here or you can download the (.mov) file here - this last one is in German.

It is a short documentary-like news upon Rechenberg's work. The so-called evolution strategy's Experimentum Crucis is shown and Rechenberg performs a short simulation of that experiment - an experimental optimization¹. The image below there is the Experimentum Crucis set up.



The video is a nice and very interesting summary about Rechenberg's research.

Here you are some video stills:


The original issue on Der Spiegel magazine:



A closer view upon Rechenberg picture:



Ingo Rechenberg at Sahara Desert researching the Sandfish:



Rechenberg among children comparing the working of the Evolution Strategy with the blindfold game:



Rechenberg in front of the Magic Square problem which he solved through an Evolution Strategy:



The multi-winglets evolved via an Evolution Strategy:



Closer view on the multi-winglets:




Der Bioniker:



And, finally, the frog himself :)





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

Notes:

1 - Experimental Optimization means that you have a real physical, mechanical, electrical, optical, chemical, etc, object or some model, like physical, of the real object - and absolutely no computer - and you want to alter some of its properties (size, charge, temperature, pressure, etc.) in order to achieve an improved performance according to some criterion (criteria). Before the end of the 1960s Ingo Rechenberg and Hans-Paul Schwefel did not think of using the Evolution Strategy as a numerical method. Computers were not yet available in larger numbers, and if so, their power was rather weak.

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

Evolutionary Computation Comic Strip... Well, at least it seems one!

I found a Power Point presentation (named Just What Are "Building Blocks" - How do (should) Evolutionary Algorithms “work”?), by Chris Stephens, upon some critiques related to Building Block Hypothesis and, also, on the Building Blocks itself. That presentation was held at FOGA 2007. I paid attention to four slides, I guess they speak by themselves. It's so intelligent and funny! :)











Stephens made interesting question on the Building Block Hypothesis, see below:

"Building Block" Hypothesis:

A GA works by combining short, low-order,
highly fit schemata (“building blocks”) into
fitter higher order schemata.

- But how would we recognise one if we saw one?
- Building what?
- How many of them are there?
- Just how are they combined together?
- When is recombination beneficial?
- How does the effect of recombination depend on the fitness landscape (and on other operators/parameters)?

The good old Building Block Hypothesis! I remember that, once, at a evolutionary computation class, I asked the professor how someone could guarantee that the unknown solution of a problem could be achieved through short, low order, above average schemata, if the solution itself is unknown?! What if the solution is neither short nor has low order? Could a genetic algorithm get the optimum also working through strings with below average fitnesses? The professor was so categoric and said that the Building Block Hypothesis really explains the way genetic algorithms work.

Well, when the problem has to do with decomposable/separable fitness functions, it should work fine, however put some dependencies among variables and you will see what happens - even for EDAs the dependencies can represent a frightening nightmare, since, when dealing with strong dependencies, the probability distribution that samples the strings can be almost computationally unfeasible to calculate.

Operations Research Blogs

Michael Trick's Operations Research Blog has two posts upon a couple of OR blogs. See here, and here. I should confess that I liked the title of one of them: Punk Rock Operations Research. It's so sweet to hear such a blog's name! I guess the author maybe likes bands as Misfits, The Who, and so on!

Both are added to the OR index links. :)

A Personal Summary Upon The 2007 IEEE Symposium on Computational Intelligence

Peter Chen has written a personal summary about the 2007 IEEE Symposium on Computational Intelligence. See here.

I guess it should be interesting to attend such a Symposium, mainly due the fact that someone could attend a myriad of tutorials (35), poster presentations, and competitions, and, also, it was held at Hawaii! Beach, sunsets, sunrises, beautiful clouds, the Pacific ocean, the landscape, aloha shirts, and, surely, the Symposium itself, since there were so many interesting persons there to talk and exchange ideas. :)