Slashdot Mirror
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.
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?
About 25 years ago there was an experiment done by one of our fellow programmers who decided that computer software can be programmed by using Darwin theory of evolution. A large mainframe was programmed to create small pieces of machine code (functions) and then the generated code would run a series of tests and the tests were designed to grade the selected code by utility, the heuristic was accomplishing sorting of a character string. Basically, a generated function would run on input provided by the tester code (where input is a randomized character string) and the output would be compared to a sorted character string. If a strain of code produced output that looked a little like a sorted string, this function would be stored for the future generations. After running this tests for a week, the best family of generated functions was fed back into the mainframe, the test functions were adjusted and some strains of code were introduced into the machine that were written by the programmer that would help to speed up the process. The functions were allowed to mutate and to reproduce by combining features from some functions into new ones. At the end a computer program was generated that sorted the entire string of characters. Interestly enough, the programmer could not figure out exactly how the string was sorted, the software was just too complex to understand (I supposed he did not want to waste time trying).
I think anything at all can be accomplished by GE, the only drawback would be that us - humans - may fall out of the production loop. We will not have to understand why an engine with octagonal and hexagonal and other types of parts work better than something else. It will be too complex for us to understand, and even if we could, who would bother? We would just use the results that appear as if by magic.
But I guess there are drawbacks in all methods...
You can't handle the truth.
Genetic Programming and Genetic Algorithms really work. Here's the general idea behind genetic algorithms (and a specific example - curve fitting)
1)Express the problem and solution space in terms of a set of numbers.
ex: coefficients on x^i where i steps from 0 to 100.
2)Express a fitness function - this can be very difficult!
ex: testing 1000 different points, fitness = sum of standard deviations
3)Generate a random set of hypothetical solutions to the problem - it's best to generate 100-1000.
4) Test the fitness of each possible solution.
ex. just as stated in 2, sum the standard deviations.
5) Keep all the solutions so far (within reason) and add:
5a)Some mutations of some of them.
ex. change some of the coefficients a bit.
5b)Some crossovers of some of them.
ex. take some coefficients from solution X, and THE OTHER COEFFICIENTS from solution Y.
Note: mutation and crossover policies have to be well designed so as to stop local minimum issues.
6)Go back to 4) until the fitness of a solution is within some threshold of the ideal fitness
(in my example, that might be 10.000000 or something).
Check out the following resource for source code if you want to try it out yourself:
http://www.aic.nrl.navy.mil/galist/src/
--
Ancient Goth: Someone who overthrew the Roman Empire.
Time is Nature's way of keeping everything from happening at once... the bitch.
This is true, but if you're driving an old car instead of buying a new one, you're helping the environment also, so perhaps it balances out.
...
I wonder which does more damage to the environment - burning up more gas in an old car, or building a new one. Considering the amount of energy and effort that must go into building a new car, I would say that it might actually be more environmentally sound to drive one that is old and uses more gas, than to buy a new one.
Anyway, I have no sympathy for people who whine about gas prices. If you're going to destroy the environment, then you should pay for it. And you should pay for it at a rate far greater than the rate at which you currently pay for gas in the U.S. Like, say, $5.00/gal. I would be SO happy if gas went up to $5.00/gal (as long as it wasn't just the oil companies getting rich, but instead a tax which go to something useful).
And no, I don't own a car, or any motor vehicle at all in fact (I live in NYC where they are less than useless), but even if I did, I would still want to pay $5.00 to be reminded every time I went to the pump what damage I was doing to the world. And of course, I want everyone else to be reminded of that as well.
Hey America - get off your fat asses, get out of your SUV's, and try *walking* or *biking* to work (or, if it's too far, then - heaven forbit - move closer to work!)
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.)
nal 11
GAs tend to be useful in discrete problems, where standard non-linear optimizers don't apply. Even there, GAs are often inferior to other stochastic algorithms. In general, the use of a genetic algorithm requires more performance evaluations than simulated annealing, and frequently more than simple stochastic hill-climbing.
There's one key exception, however. If the objective function has essentially cylindrical optima (e.g. the function f(x, y) = (1 - x^2) * (1 - y^2)), then the crossover operator allows the system to use "hyperplane search": the "crossover operator" (used in the generation of the new population members) will frequently tend to take the good parts of different candidates and glue them together, making better offspring.
What's sometimes surprising is how many objective functions can be encoded so that they have roughly cylindrical optima relative to the cross-over operator. For instance, in the old work on the Travelling Salesman Problem, van Gucht et al. used segments of circuits as crossovers, and that gives a roughly hypercylindrical objective function, thus speeding up convergence.
All this means that without actually looking at the particular objective function and encoded, we can't really tell whether the use of the GA was wise or not. It depends on the constraints of the problem.
So...the question is...who gets the patent, and what for? Can the engineer really claim that he "invented" this engine because he used GA? Should the algorithm itself be patented? Inventing machines. Food for thought.
It's 10 PM. Do you know if you're un-American?
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.
-- http://thegirlorthecar.com funny dating game for guys
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
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!
Keeping
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.
--
Have fun: Join D.N.A. (National Dyslexics Association)
Does anybody know any more about why the GA the researcher used had such a small population size? Population of 4 + 1 elite seems mighty small to me- 50 or 60 sounds more like it, even if it takes ten times longer per round to evaluate, because you typically want more diversity. Or in this problem did he find that the diversity wasn't worth it? Does anybody know?
--
-jacob
-jacob