Evolving Real Robot Swarms Through Simulated Evolution

Nice video this one: Deployment of Large Aerial Swarms.

It seems the authors applied an evolutionary algorithm (genetic algorithm?) to do the control of those robots.

Genetic Algorithms, Complex Systems, Economics. . .

Interesting on-line paper this one. It shows how the Santa Fé Institute's researchers, genetic algorithms, and complex systems rediscovered a classical way of economics -- but, of course, there is more than just that on the paper. It's worth reading!

Have you ever wondered how free markets could be self-adaptable?

Genetic Algorithms, Proteins, Nuclear Power And More!!!

A nice summary of a new book on natural computing and, of course, genetic algorithms are a part of it: The Lessons Of Living Things.

Well, it is not a novelty, since computers have been helping us to build things and achieve results since the early beginnings of computing. Surely, the natural approach to computation was a nice move and helped to open a new and wide research field.

Evolving Wind Turbine Blades Through Simulated Evolution

Nice video this one:

Evolving Wind Turbine Blades.

Its author applied a genetic algorithm to evolve/optimize the blade shape of a wind turbine. It reminded me of Professor Ingo Rechenberg's work on a similar task: The BERWIAN (Berliner-Windkraft-Anlage) in which his group applied another kind of evolutionary algorithm -- evolution strategies.

The «Berwian» windmill by Ingo Rechenberg takes advantage of the complex eddy effect. Active paddle tips are turned towards the centre, where the turbine is placed. The windmill was optimized by the method of «evolution strategy» at many levels (number and position of the blades, profiles, etc.).

As we are talking about green/clean energy resources, don't miss the chance of reading an interesting post at Martin Pelikan's blog on the same poetical vein (solar panels).

Evolving Bugless Programs Through Simulated Evolution

A brief and nice overview of a genetic programming application for debugging real computer code programs. See it here.

It's almost a surprise to me the programming language used was the good old C: A Real Programming Language Hero!

Genetic Algorithms, Formula 1 Cars, And Speculations...

An interesting post on the possibility of Formula 1 teams are using genetic algorithms to aerodynamically design their cars.

Another researcher had already done something similar, but completely from scratch! Even though the final result should not be expected to win a championship.

Evolving Next Generation Chips Through Simulated Evolution

See how evolutionary computation is helping to build the next set of microchips. The link:

Engineers Evolve Transistors for Next-Gen Chips.

It seems that as transistors and associated components are getting smaller (nanoscale), some little production process imperfections end up having a considerable performance impact in the final product and one of the desirable aims would be finding a way to, even though those imperfections take place, the final product could deal with them without losing too much performance.

Some English researchers are investigating how to use evolutionary algorithms to cope with that problem.

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.

Evolving Proteomics Through Simulated Evolution - UPDATED

Excellent post by our blog friend Martin Pelikan, see it here.

It deals with the use of a genetic algorithm to select a subset of conformations explaining the experimental scattering profile best.

Despite choosing geophysics as my grad school career, I consider proteomics a big deal and it would worth a lot investing time and dedication pursuing a career in that field.

It would be interesting if Martin told us what kind of genetic algorithm he applied (EDA or classical ones).

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

Martin Pelikan explained the evolutionary algorithm they used for evolving protein conformations:

"[...]The genetic algorithm we used is similar to a simple GA, but slightly crossed over with UMDA. We started with this simple method inspired by some prior work in this area and since the method worked, we used it. We tested it on artificially created examples and it worked great, and it gave reasonable results also for the real-world cases. More should be published soon, I hope."

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

Thank you very much, Martin! I hope you achieve great results!

Evolving Architecture Through Simulated Evolution

Very good post this one, see it here.

It deals with the optimization of an acoustic shell which delivers the best sound distribution along the space it covers. The author used a genetic algorithm to tune the parameters.

Evolving Fish Swimming Through Simulated Evolution

Great story about a robot tuna which has its parameters set up by a genetic algorithm. See the link below:

MIT Ocean Engineering - RoboTuna.

It reminds me of an earlier post here:

Evolving Design Through Simulated Evolution.

An excerpt from the robot tuna case:

"The third and final phase is a search for the optimum swimming performance obtainable within the physical limits imposed by the design of the RoboTuna and the length of the existing testing tank. The current analytical intractability of the fluid dynamics of this problem indicated that the most pragmatic way to proceed would be to optimize the body wave controller experimentally. In simple terms, given the seven parameters which control the swimming body wave, this can be thought of as an experimental search through seven dimentional space. This large number of dimensions quickly creates a massive logistics problem (about 282,475,249 combinations of parameters).

Given that it takes approximately 5 minutes to make a single experimental run down the tank, it would take a time frame in the order of millions of years to perform a blind search through all the combinatorial possiblities in the persuit of an optimum (it is no coincidence that this is about the same amount of time it took for the biological tuna to evolve to its present form). Obviously a more efficient search mechanism is needed, in orger to find the optimum before either time ran out or the apparatus failed mechanically. After a survey of many existing multidimensional space search techniques, a robust, seft-optimizing system based on a Genetic Algorithm was developed."

Evolving Robot Gait Through Simulated Evolution

Interesting story brought to me via my news webservice:

Students - And Robots - Learn In Professor´s Robotics Lab.

The genetic algorithm applied is the CGA - Cyclic Genetic Algorithm. Not to be confused with the cGA - Compact Genetic Algorithm, an EDA.

The main ideas behind CGA are the following:

Parker made modifications to the standard genetic algorithm to invent the cyclic genetic algorithm (CGA), a method by which cycles of behavior can be learned. The CGA is a method where the computer can self-generate code. In real life, this means that a robot who encounters mud, for instance, might adapt with a different gait. A robot that loses a leg could learn to walk without it.

To demonstrate, Parker changed the parameters on the computer to tell one robot that it was suddenly carrying a heavy load. The robot took on a new walk - slow, deliberate and heavy on stability. In further tests, he showed how the CGA could adapt the robot control codes for partial and full loss of one or two of its legs. "The original CGA method was very limited because it couldn´t react to sensory input," Parker said.

More formaly it can be put as:

"Cyclic Genetic Algorithms were developed to allow for the representation of a cycle of actions in the chromosome. They differ from the standard GA in that the chromosome is in the form of a circle with two tails. The tails of the CGA chromosome are provided to allow for pre and post-cycle procedures. They provide a means for completing tasks before and after entering the cycle. For gait sequence generation, the pre-cycle can position the legs in a ready to walk posture and the post-cycle can return the robot to a stable at rest posture. In our application, we used only the pre-cycle tail. TheCGA genes can be one of several possibilities. They can be as simple as normal genes that represent traits of the individual or they can be as complicated as cyclic sub-chromosomes that can be trained separately by a CGA. For our purposes, the genes represent tasks that are to be completed in a set amount of time. The trained chromosome will contain the cycle of primitive instructions that will be continually repeated by our robot's simple controller to produce a gait.

CGAs can have both fixed and variable length chromosomes. In either case, the system must be able to allot the proper number of tasks to each phase and be flexible enough to allow the CGA to form a complete cycle. When fixed length are used, the tasks at each gene can be repeated. The number of repetitions is encoded in the gene. In this way, fixed length chromosomes can take on the desirable characteristics of variable yet maintain the increased control of training fixed.

Evolving Design Through Simulated Evolution

Amazing article from Elisava:

Bionics And Design: Witnesses To The Evolution Of This Approach.

Some quotes from the text:

"[...] Natural history research, even that which seems to be no more than the fruit of pure and empty curiosity, can have very real uses, which would be enough to justify it even to those who only want research into useful things, if before condemning we could have the patience to wait for time to show the use we could make of its [...]."

Rene-Antoine Ferchault de Reaumur, A History of Wasps - 1719.


"It is the story of the development of the branch of mathematics called the calculus of variations, which concerns questions of optimization —finding forms or patterns that maximize or minimize a particular quantity Is the igloo the optimal housing form for minimal heat loss to the outside? Do bees really use the least possible ammount of wax in constructing their hexagonal cells?"

Stefan Hildebrandt & Anthony Tromba - 1985


"The oldest shells in the universe are the crusts of the cooling stars... We can compare them to an egg-shell: they are formed on the surface of moving liquid drops. In long-ago prehistory, about 400 million years ago, living nature took advantage of the fact that a curved structure is 50 to 100 times stronger than a flat structure of the same thickness. This means that the protecting envelope around fragile micro-organisms can as much reduce the expense of material and weight as obtain a greater degree of protection[...]."

Heinz Isler - 1989


"I believe that flowers —vivacious or woody plants— not only present the most frequent type of shell, but that they are also those of the greatest beauty. They offer a complementary perfection: they are kinetic structures. According to need, they can vary their form to open or close the flower, or even to aid the process of pollinization[...]."

Heinz Isler - 1989


"Nature offers us a range of secrets that will not be revealed except with much patience and love [...]."

Le Ricolais - 1935-1969

Evolving Crystal Structure Through Simulated Evolution

From my news webservice I got this interesting sample of genetic algorithm application, see here.

An excerpt:

"[Julio] Facelli, director of the University of Utah's Center for High Performance Computing and a biomedical informatics professor, uses NCSA's Mercury cluster to predict crystal structures for organic molecules that are frequently used in pharmaceuticals, fertilizers, and explosives."

"Modeling the crystal structure of a given substance, Facelli and his team begin with nothing more than the atoms in the molecule and the nature of their bonds. They're looking for structures with the lowest energies, which typically mark the molecules' standard crystal structures or something very close. The problem is that this straightforward data and straightforward goal create billions of possible solutions. Just imagine finding the needle of the lowest energy in that haystack of possible structures."

"'An exhaustive search is not feasible, so we have to have a way to direct the search,' says Facelli. '[Genetic algorithms] are based on the principle of survival of the fittest. Trial solutions compete with one another in the population for survival and produce offspring for the next generation of tests. These algorithms offer excellent scaling properties, which make them good for large-scale parallel computing systems like those at NCSA and emerging computational grids like TeraGrid.'"

Here the article outlines through a simple manner the inner working of the genetic algorithm used:

"For example, an initial calculation on NCSA's Mercury may run 20 simulations on 20 different processors simultaneously, calculating possible crystal structures for a given set of atoms and their bonds. The energies for these structures are compared. The 10 with the lowest energies are kept, and the features of those 10 are mixed and matched to generate the structures for another 10 possible structures. Energies are calculated again, comparisons are made, best candidates are kept, and the cycle continues.

The 'mating operation,' as the mixing and matching is called, stagnates quickly, producing very similar structures over the course of thousands of generations. To combat this lack of variety, the genetic algorithm also introduces arbitrary mutations into the process, occasionally taking one variable from one of the best candidates and including a random number for that variable in the next generation."

Stagnation has been, since immemorial times, a hard drawback to overcome, mainly when using an elitist selection method. Taking into account that those individuals holding the lowest levels of energy are the best ones, then it is, in some sense, normal that the genetic algorithm got stuck quickly. Surely, there already are techniques to treat that, such as truncation selection.

If I were the author and considering he is using mutation and crossover, I would set up a high mutation rate (0.85 to 0.95) and a mild crossover rate (0.45-0.6), of course I would put the elitist rate (the number of fittest individuals saved per generation) as a rate of 1/7 of population size. Inversion could help too!

Evolving Missile Trajectory Through Simulated Evolution

I have found an old school evolution strategy article, from 1980: Optimization of missile trajectories by means of evolution strategy. You can read the first page here.

From the abstract:

Evolution Strategy is an optimum seeking method which attempts to apply the rules of biological evolution - mutation and selection - as closely as possible to technical optimization problems.
In the paper results are presented showing the successful application of evolution strategy to missile trajectory optimization problems like

- Range optimization of a ballistic rocket and e boost-glide missile

- Optimization of miss distance due to lateral wind of a Short range antitank missile

- Optimal trajectory shaping A comparison with other optimization methods is given to show the efficiency of evolution strategy.

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


From the introduction we can understand a little of the academic Zeitgeist along that period, see below:

"The paper deals with solutions of optimization problems which we have gained by the application of evolution strategy to missile engineering and development. Evolution strategy is an imitation of nature's way of optimization, a game of mutation and selection. Since nature has been man's teacher in many ways it might appear quite obvious to apply the laws of biological evolution to problems of engineering and technology.

On the Other hand there are also objections to that method, the most important ones being that "cut and try" is a sign of poor engineer and craftsmanship and that we cannot afford nature's lavishness in means and in time to wait for the result. Based on a number of number of encouraging results [1], [2] we have tried to gather our own experience with the matter and will present the results we have achieved.

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

It seems that the author worked to the famous German aircraft manufacturer Messerschmitt, which gave birth to the world's first operational turbojet fighter aircraft, the so-called Messerschmitt Me 262.

Below the old Messerschmitt logo.

Evolving Design Through Simulated Evolution

Nice post from RASMUS BRØNNUM upon evolutionary architectural diagrams, see here. It is a Java program called ArchiKlugethat that evolves structures and shows on-the-fly some of the current results. The program runs in a applet and you can even manipulate the structures using your mouse to rotate them and exhibit a different perspective of the evolving structure.