Detecting Groundwater Pollution Source Through Simulated Evolution

I have not yet seen an application of evolutionary computation like this one: Tracking groundwater pollution to its source. But it seems they also apply other kinds of soft computing (neural networks and simulated annealing).

Excerpt:

They point out that reliable and accurate estimation of unknown groundwater pollution sources remains a challenge because of the uncertainties involved and the lack of adequate observation data in most cases. The non-unique nature of the identification results is also an issue in finding the original source of a pollutant. They have tested the validity of different optimization algorithms including a genetic algorithm, an artificial neural network and simulated annealing and hybrid methods. All of these methods essentially process available data including pollutant concentrations and how these change over time and any monitoring data to home in on a potential source. The benefit of using such algorithms is that as more information becomes available another iteration will take investigators closer to the source.

It seems an interesting application of artificial intelligence.

New Book On The Block

Jason Brownlee has published a new book on intelligent algorithms and machine learning: Clever Algorithms Nature-Inspired Programming Recipes.

I read the topic on evolution strategies and genetic algorithms it is a well crafted text for quick reading, rapid implementation, code examples and good references at the end of each topic.

You can download the PDF, read it online or buy a real copy!

Evolving Astronomy Data Mining Through Simulated Evolution

Interesting stuff this one: The Future of Astronomy is Automated.

It seems genetic algorithms may give another kind of role for traditional astronomers -- and not only for them, but also for other kinds of data miners.

Keep your eyes wide open data miners!

Evolving Car Racing Through Simulated Evolution

Nice pointer from Martin Pelikan's blog. There is an interesting video of the simulated car racing.

Mega Man + Genetic Algorithm Vs Air Man

There is a video at YouTube in which the author claims to have developed the fighting style of Megaman using a genetic algorithm to win over Air Man (the boss of the sky-themed level in Mega Man 2).

It is interesting to notice that, over the generations, indeed, Mega Man deals more damage to Air Man. The fitness function is very simple:

F = MMLB - AMLB

MMLB = Mega Man Life Bar
AMLB = Air Man Life Bar

Negative values mean Mega Man failed to win. Otherwise, he was successful.

Just after 10 generations, Mega Man manages to win his first battle and in the next ones his skills are improved.

I wonder if Dr. Light used genetic algorithms to design its robots. If so, he would be a pioneer of evolvable hardware!

Richard Feynman's Affair With Simulated Evolution

Interesting finding this one. Surely I am not joking, but I should state it is not a profound and complete involvement of Feynman's part -- at least I see through this way and I would not get surprised if I am totally wrong about that. However, as the paper author stated in another article:

The last project that I worked on with Richard was in simulated evolution. I had written a program that simulated the evolution of populations of sexually reproducing creatures over hundreds of thousands of generations. The results were surprising in that the fitness of the population made progress in sudden leaps rather than by the expected steady improvement. The fossil record shows some evidence that real biological evolution might also exhibit such "punctuated equilibrium," so Richard and I decided to look more closely at why it happened. He was feeling ill by that time, so I went out and spent the week with him in Pasadena, and we worked out a model of evolution of finite populations based on the Fokker Planck equations. When I got back to Boston I went to the library and discovered a book by Kimura on the subject, and much to my disappointment, all of our "discoveries" were covered in the first few pages. When I called back and told Richard what I had found, he was elated. "Hey, we got it right!" he said. "Not bad for amateurs."

It would be interesting showing before Feynman's eyes what have been done in the evolutionary computation field since then. His mind is the kind of those the field needs.

Amazing reading for a Saturday afternoon. :)

Evolving Mona Lisa Through Simulated Evolution

Amazing story this one! See it here.

It is a genetic programming algorithm designed to evolve Leonardo Da Vinci's Mona Lisa. It seems that each individual is represented by 50 polygons and the fitness function is the real image of Mona Lisa. So, the polygons should be arranged as close as possible to the real one.

The final result is amazing.

Evolving UCAV Strategies Through Simulated Evolution

An article from the Wired Magazine Danger Room section outlines five top national security research challenges for the next president of United States. See it here.

The author says military application of genetic algorithms is an important one when it comes to UCAVs.

"Applications for Genetic Algorithms in Battlefield Operations - This is a natural research progression for an armed forces increasingly willing to conduct operation with unmanned aerial vehicles, or UAVs. Genetic computing and algorithms allow machines to learn through repeated trial and error, as programs can "evolve" to solve extremely difficult artificial intelligence problems. This has very clear applications for battlefield operations. For example, UAVs can be freed to develop the most efficient routes for surveillance, an experiment that has already shown some success. Genetic computing has also shown promise in forecast modeling, and additional research should be conducted to investigate its application to modeling scenarios with national security implications."

It is not a novelty, since military evolutionary computation applications date back to, at least, 1980.

For example, this article from 1991 deals with the optimization of thrust vectoring nozzles using a genetic algorithm. Click here to see the first page. BUT, nozzle optimization dates back to late 1960s and early 1970s, as demonstraded by Professor Hans-Paul Schwefel pioneer work.

Evolving Virtual Creatures Through Simulated Evolution

Interesting project this one:

"This application is an example of evolutionary computing that you can run on your own Windows PC at home (see the download section). It uses a process similar to biological evolution to gradually evolve a population of virtual creatures in a 3D graphical and physical environment. Much of the inspiration for this project came from the wonderful work of Karl Sims. In the mid 90's Dr. Sims did something very similar, using an evolutionary algorithm to evolve the body plans and control systems of virtual creatures whose bodies were composed of jointed blocks. His creatures were evolved in simulated land and water environments for their ability to swim, walk, jump, follow a light source, and compete against opponents for control of a resource. See the related projects section for links some videos from Dr. Sims and links to other virtual creature evolution projects).

With this program you can watch a process of simulated Darwinian evolution unfold before your eyes (although the process can take several days of computer time depending on your computer speed and your evolution settings). The user is given control of many of the parameters of the evolution such as the size of the creature population, the mutation rate, the ability for which the creatures will be evolved, and many other settings. Users are encouraged to send me any interesting creatures they should happen to produce for inclusion in the Zoo. There are already numerous strange and interesting virtual creatures on display there, with many more to come."

PPSN X - Parallel Problem Solving from Nature 10th Edition

It has already began the 10th edition of the PPSN conference which was started in 1990. See the current edition site here. For a log upon the past editions, see here

It is being held at the Technical University of Dortmund (TUD, former Uni-Dortmund) and you can check the accepted papers here. It seems there will be a wide range of topics on evolutionary computation.

By the way, check the blog entry by our blog friend Juan Julián Merelo Guervós on PPSN X here. Another blog entry here, by Jorge Tavares.

Professor Hans-Paul Schwefel is the PPSN X honorary chair

Let's wait for more blogging from Dortmund at the PPSN X. [Estoy confiando en ti, JJ! Don't disapoint me! :) ]

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

On Penguins And Submarines, Airplanes, And So On!

Interesting finding here:

Aerodynamics In The Animal World. Yes, I know: Another Google automatic translation. But, it is better to read something slightly comprehensible than nothing at all. The main ideas are very clear, I think. :)

The article has to do with the aerodynamics on animal bodies, such as the Penguin's, and how it deals with aerodynamical problems - turbulence, acceleration issues, and etc.

The Penguin's streamlined body could be an inspiration when it comes to submarine body design, helping to create even quieter, faster, and more efficient submarines. Let alone it could also be applied on other areas strongly relying on aerodynamics, such as airplanes, rockets, and etc.


See a short movie of the Ṕenguin's flight here.

Evolving Electrical Circuits Through Simulated Evolution

Another application of genetic algorithm to optimize circuit components' values, see here.

The resistor's and NTC thermistor's values must be set up such that the resulting curve (from the circuit equation) matches the curve on the chart below:



At a first glance, it seems a very simple problem, but, as the article observes, it may get hard to solve as the circuit complexity increases.

It remembers me of a tale of a senior student in a class of electrical circuits. The professor put some hard circuit problems to be solved through variable substitutions and so on. There were so many derivatives to be solved and etc. The senior student used a tricky way to solve them:

01. He organized all the equations.

02. He used the Laplace transform to all of them.

03. He put all the parameters on a matrix.

04. He solved all the equations through the Gauss-Jordan method.

I was not there, but some "persons" state that the professor refused his solution!!!

I wonder if that professor is the same guy which once said that 1/2 Ohm is not the same as 0.5 Ohm!!!!

Evolutionary Computation News

Interesting news on genetic algorithms and a quick analysis of their academic/design impact upon those (and many other) areas. See here.

As you may see, there are persons which consider genetic algorithms too slow and others think they are too cute. :)

Some excerpts from the news:

"Yet there are drawbacks to the method. Although genetic algorithms have been applied with fantastic success in some cases, they fall short of being universal problem-solvers. And although evolutionary eons can be compressed into hours, finding the precise settings that will give a good solution can take months. How do you figure out which solutions are best? How often do you mutate the offspring? Computer scientists are reduced to trial-and-error knob-twiddling to get the right conditions."

"They’re too cute. Genetic algorithms don’t get bonus credibility just because that’s what nature did,"

"They are quite slow, and they require quite a bit of fiddling,"

"Genetic algorithms’ main contribution today are that they opened the door to biologically-inspired methods. The beauty and success of genetic algorithms motivated other computer scientists to look to biology for inspiration,"

By the way, I consider that genetic algorithms (and evolutionary algorithms in general) are very nice to solve problems, mainly when taking into account the lack of problem informations, such as no derivative available and/or so many constraints to handle.