Genetic Algorithms Improve Combustion Engines

University of Wisconsin Madison's Peter Senecal has evolved a new combustion engine which cuts nitric oxide emissions three-fold, soot emissions by fifty percent and fuel consumption by fifteen percent. His genetic algorithm searches for the best combination of six parameters which determine the design of an engine. It starts from a search space of five, and includes strong heuristics to minimize the search space considered.

Comments

Re:This is standard practice for engineers.

[Petethelate]

My main concern is whether the engine can work well in the real world. Getting efficiencies in a test cell is easy (I have an acquanitence who designs engines. He has a test engine with variable compression ratio. On a good day, he can keep it running for a while at a compression ratio of 30. It's a *long* way from being roadworthy.) The variation you see on the road is much larger than in a test cell, or in other applications, like aerospace--conditions that a car engine take for granted could raise hob with an airplane engine. F'rinstance, wildly changing loads over a matter of a few seconds.

Still, the GA design methodology sounds interesting. I wasn't clear how they avoided getting stuck on local minima. Is this what the 'mutation' handled?

I wouldn't listen to that something again.

[Tau Zero]

... by the time you pay off the engine, you'll break even with the gas money you're paying...

I'd bet otherwise. When the changes are as simple as varying the shape of the combustion chamber (which is just a casting), the timing of the fuel injection (which is electronic in a lot of the new diesels, and thus software-controlled) and the exhaust gas recirculation (also controlled by a servo valve) you're talking about next to zero added hardware and thus very little added cost. Most of the cost would be one-time expenses... like running the genetic algorithms to determine the best design and operating conditions. At worst, most of the hardware changes would be like the change from linear regulating power supplies to switchers. Today, switchers are pretty darn cheap and a lot more efficient. Believe me, these things would pay for themselves in short order.
--
Ancient Goth: Someone who overthrew the Roman Empire.

Re:This is standard practice for engineers.

[Chris Hind]

A GA certainly does care about hills in the search space --- but you're also right in that it's not just a simple hill climber. How can this be so? Well, a simple hill climber just looks around it and always heads upward. If you have a search space that has a tiny hill next to a huge one, and you start a hill climber on the slopes of the tiny one, it'll chug up to the top of the tiny hill and sit there.
Now, a GA throws in a random element as well. That's to say, the next step for a GA doesn't always have to be in the 'up' direction. So start a GA on the tiny hill, and if it's random enough the population that forms the next generation will be spread out all over the tiny hill and partially up the slope of the massive hill. Natural selection then comes into play, and the parents of the next generation are the guys and gals who are climbing the mountain. Next generation, the population will be spread even further up the slope --- and of course the ones at the top get to be the mums & dads...
Of course, you can see that if the GA isn't random enough (too low mutation rate, or not enough variance in the gene pool), the GA could quite easily get stuck on the little hill. This is why when we solve problems with GAs, we tend to use lots of different starting points: we know that each starting point will probably lead us to a different (but large) local maximum, so we try to get them all.
(You could try increasing the randomness. You can see where this leads: too much randomness and you might as well be doing a random search; you're destroying the 'partial solution' that your genetically-bred creatures have found at each step.)

This is standard practice for engineers.

[acidrain]

Genetic Algorithms are a staple for engineers. About 5 years ago they used almost the same technique to achieve similar results with jet engine turbines. Civil engineers love the stuff especially. Consider the problem of finding the optimal route for a highway through mountains that involves moving the least amount of dirt. The search space is massive, but not so hilly that a GA can't function well.

Re:This is standard practice for engineers.

[Anonymous Coward]

Still, the GA design methodology sounds interesting. I wasn't clear how they avoided getting stuck on local minima. Is this what the 'mutation' handled?

"Local minima" are solutions are best amongst all similar solutions, but are worse than a whole set of solutions that takes a completely different approach. They are problematic for most optimisers because standard approaches look in the immediate vicinity of the best known solution, to find a 'direction' that improves that solution. At a local minimum there is no such direction.

GAs work around this problem by maintaining a population of solutions rather than just one solution. The population should contain a diverse selection of potential solutions. This diversity can be maintained by not being overaggresive about selecting 'better' solutions for future generations. For instance, rather than always letting the best solution win through to the next generation, instead just improve it's probability of winning a bit. Mutation is used to occassionally force a population member away from its current solution, which can help to maintain diversity. There is much debate about whether this is actually useful. One simple way to check would be to change the human genome structure so it never mutates, and see whether human progress over the next million years is obstructed ;-)

A great feature of GAs is that through tuning these kinds of parameters the researcher can explicitly choose the level of compromise between diversity of population and aggression of selection. More aggressive GAs find a solution earlier, but are more likely to get stuck in a local minimum.

An understanding of this compromise is important for using GAs effectively. Function surfaces that do not have few or no local minima should be tackled with a local search algorithm or similar. In benchmarks GAs will come out as thousands of times slower on these problems. However, it is their versatility that is their strong point, not their speed.

Not so much as a comment as a question

[Benjamin Shniper]

Important in fuel efficiency are other factors such as wind resistance, vehicle weight, and power saving devices such as efficient breaks which channel the energy created from breaking back into an electrical engine.

These fuel efficiencies are seperate to the engine, but can be co-dependant. Already cars getting 70 miles per gallon have been created simply by being dual electical/internal combustion.

As a former worker at Ford Motor Company I used a genetic algorithm to optimize fuel efficiency as a function of cost. But maybe I wasn't thourough enough... Is it possible the biggest gain is yet to come when the ENTIRE car model is fed into a genetic algorythm and optimized by geometry, with goals of fuel efficiency and vehicle cost?

-Ben

gallops

[grammar nazi]

Check out the GARAGe at Michigan State University. They use Genetic algorithms for many different and interesting problems. From consumer preference predicting to financial analysis.

There code is called Gallops, and it seems very scalable. There is a Meta-GA built into Gallops that allows the GA to genetically change itself in order to be the most efficient GA.

This is cool stuff!

Life imitates life

[dmccarty]

I gave up moderator privelages to post this comment, so I hope what I have to say has some value.

I've recently learned about Genetic Algorithms (GA) in my quest to win $15,000 from The Code Book and Simon Singh's Cipher Challenge (eGroup here). One of the stages is a deft Playfair Cipher, which have historically proven difficult to solve by hand. Using a genetic algorithm, I was able to solve the cipher in just 28 generations.

What's amazing to me is that here I have just 500 lines of code that know nothing about ciphers, Playfairs and codebreaking, yet using a simple mutation and scoring function was able to break a relatively difficult cipher.

For those that don't know, a Playfair cipher puts the English alphabet into a 5x5 grid (minus 'j') and uses pairs of letters to select other letters from the grid. Instead of a 26-letter substitution cipher, codebreakers are now faced with a daunting 676 letter-pair challenge.

My code created 1,000 random keysquares and mutated them, randomly selecting squares and swapping them with one another, or swapping entire rows and columns. The new generation was scored, and those that scored high had a better chance of making it to the next generation than those that scored low (survival of the fittest, if you will). And in just 28 generations, what was once a mass of jumbled letters slowly transformed before my eyes into perfect English. Once the solution had been found I actually felt bad about killing the process, as if I had creatd life and killed it. It was truly amazing.
--