Slashdot Mirror
Review: An Introduction to Genetic Algorithms
Background
It was in the early nineties when I became interested in these sorts of things. I was enrolled in a commerce program, but somehow got onto reading such popular science books as Levy's Artificial Life: A Report from the Frontier Where Computers Meet Biology and Waldrop's Complexity: The Emerging Science at the Edge of Order and Chaos.
Those books made me make my next degree a computer science degree.
Emergent Computation
I was fascinated by the idea of computation emerging from the bottom up: from simple rules acting together in simple ways. This is in marked contrast to the traditional artificial intelligence view that complex behaviour typically only arises from the top down: from the complex interactions of complex rules.
I could appreciate the uses of traditional AI techniques, but emergent computation seemed somehow right to me.
Genetic Algorithms
Notwithstanding my simplistic explanation, there's an obvious example right in front of us. Evolution is a relatively simple process (everyone's heard of Darwin, right?) that has produced very complex output (e.g. us). What if we could harness the power of this evolutionary computation?
John Holland had the idea of mimicking this process of evolution within the computer. He encoded potential solutions as strings of zeroes and ones (the language of the computer), much as human genotypes consist of DNA strands. He developed these strings into actual solutions and measured their success against a particular problem, much as we might measure our success in life. Then he bred another generation, selecting the best individuals to reproduce ("survival of the fittest"), and applying crossover ("sex") and mutation on the strings for good measure.
That's another simplistic explanation, but as time went on these strings got better and better at solving the problem. And it didn't matter which problem. The same process could be used on almost any problem. He called this process a genetic algorithm ("GA").
An Introduction
This book is a good introduction to that world. The first three chapters present an overview of the field, and illustrate how GAs can be applied both in practical problem solving and in more theoretical research environments.
The author explains some of the history and background of GAs, the biological terminology, and its equivalent GA terminology. She provides examples and uses figures effectively.
The entire book has an "overview" feel to it. It isn't very long, and aims for breadth rather than depth. Mitchell writes with clarity, and is great at explaining the subject matter. It's not a difficult book to read.
Theory and Practice
The next two chapters cover the theory and practice of genetic algorithms. Chapter 4 is the most difficult, as it covers Holland's Schema Theorem and other mathematical and statistical observations. Fortunately, you don't lose much if you gloss over the equations, and they're there if you're into that sort of thing.
Chapter 5 is the fun stuff. Mitchell doesn't provide code, but that's okay because the explanation is lucid and sufficiently detailed to implement in code. She discusses ways of encoding the problem, implementing selection methods and the various genetic operators, and setting the parameters of the GA.
To test this theory and practice, each chapter concludes with thought exercises and computer exercises.
Applicability
Dating from 1996, the book benefits from being relatively up-to-date. It borrows from papers and studies up until then, which you'll recognize if you've browsed through other literature (such as the Santa Fe Institute's Artificial Life Proceedings).
Mitchell does reserve a critical view. She's careful to point out where further study is required, and that's important as this remains a maturing area of computer science. She also points out promising avenues for future study.
Summary
I found this book to be an excellent introduction to the field, even though I'd read articles and papers on GAs beforehand. I'd recommend it to anyone interested in genetic algorithms and ready to go beyond the popular science descriptions, but not yet ready for the hardcore books and not willing to waste time on the poorer quality "GAs made E-Z" books.
Basically, this is an excellent quality "GAs in a Nutshell" book. When you've finished it, you might be interested in Goldberg's Genetic Algorithms in Search, Optimization, and Machine Learning.
The book's official site contains a more detailed table of contents, while Mitchell's book page contains solutions to selected thought exercises, an expanded index, and errata.
You can purchase this book at Amazon.
TABLE OF CONTENTS
Preface
Acknowledgements
1. Genetic Algorithms: An Overview
2. Genetic Algorithms in Problem Solving
3. Genetic Algorithms in Scientific Models
4. Theoretical Foundations of Genetic Algorithms
5. Implementing a Genetic Algorithm
6. Conclusions and Future Directions
Appendix A: Selected General References
Appendix B: Other Resources
Bibliography
Index
One thing I find sorely lacking in many books on algorithms is any discussion of why you would select one over another
Do you mean GA versus say a Newton search method? GA is sometimes referred to as a method of last resort. This may be unfair, because many practical problems are not mathematically "nice". I am just getting into GA and I have very complicated simulations underlying my objective functions. We previously computed derivatives for these; it was a huge effort both computationally and for the programmer. One thing that I like about GA is that wrapping the optimizer around an arbitrarily complex objective function is really easy. Also, the parallelism is really good ("embarassing"), especially for distributed computing with message-passing (think beowulf).
For me, the bad thing is that convergence isn't nice and quadratic like some derivative based methods out there. On the other hand, quadratic convergence generally works only near the optimum and derivative based optimizers really only find local minimums (no guarantees about the optimum being globally optimal). Derivative based methods can blow up if you pick a bad guess objective too. Perhaps a good strategy is a combination -- use GA to get into the neighborhood of the global optimum and then use derivative based methods to find it.
I should stress that all this is for my particular application (groundwater). YMMV. Others with different objectives living in differently constrained control spaces will have different experiences. Also, to be fair I should point out that programs like ADIFOR make derivative computations easy to program.
Some helpful optimization links:
Decision Tree for Optimization Software
GA Archives
The paperback is very affordable.
Melanie also has a bunch of her papers available online (on her website at SFI) which are free to download. She is a brilliant protege of John Holland.
You obviously have NO idea of what a GA is. It would seem that you think that GA's evolve intelligent beings in civilizations! GA's simply search a solution space in a manner similar to evolution. In the case of animal evolution, solution space is explored in terms of DNA sequences (the genotype is the solution space) and the optimal solution (phenotype) is the organism that survives and reproduces best. In the case of computer GAs, the reproduction is artificial; the phenotype is used only for evaluating solutions, the genotype is used for modeling. For instance I once used a GA to evolve Corewars warriors (battling computer programs). They are not advanced beings; they are simply optimal solutions.
Hmm, you make an excellent point. 1st posters are the slashdot equivilant of mutation. They introduce some totally random garbage that might just be needed to start a great lineage (this thread being prime example numero uno).
So what does a normal reply correspond to? is it asexual reproduction? there is only one parent of this message, everything in it refers to that parent.
However it is not identical to its parent so some change has gone on. Its not mutation, the result is not a random change.
Perhaps a normal reply is actually an example of cross-over, the memes of your message have mingled with the memes of my brain to produce this message.
If getting replies corresponds to reproduction then we already have a genetic slashdot, Poor messages are unlikely to to generate responses, interesting ones are. Moderation only helps reinforce this by hiding poor messages, furthur reducing the chances of reproduction.
Cheers
Tim
Let me preface this by saying that I don't know much about GA...
This is an interesting explanation, but in this case you've really just described a brute-force breadth first search. Shouldn't GA produce something better?
For example, you could apply this described approach to a travelling salesman problem, but it doesn't seem any better than just enumerating all of the cases and picking the best one (assuming you've got a few billion computers running for approximately forever, give or take a few seconds).
Slashdot is entertaining like pro wrestling is entertaining
Maybe in trying to put down the anti-evolution movement we have gone too far the other way and lost our grip on what evolution as a theory does and does not do. (And the fact that Darwin cribbed it from economics).
My experience is that whenever a young scientist meets GA's for the first time they instantly assume it will solve all the very difficult problems we have been working on for the last 50 years. And it won't. Its just an optimisation algorithm.
GA's won't find any solution you couldn't find by exhaustive search of the parameter space. (But in many cases exhaustive search will take longer than the lifetime of the universe). If your target function won't identify the desired solution, GA's won't fix it.
GA's are a useful tool to be added to the toolkit of optimisation algorithms, along with annealing methods, gradient & curvature methods, quadratic underestimators and such like. For some problems they may be the best of the bunch, but I've yet to work on such a problem.
Still, I don't doubt this is an excellent book, and I'll add it to my reading list.
Hans Moravec is a mad robot builder and futurologist who predicts a lot of far fetched stuff, most of it too complicated to explain.
In his book "mind Children" he analyses what the implications of robotics for humanity's future, hypothesizes on the requirtements for very complicated organisms, and then goes off into the far far future and looks at that too.
Some of it sounds beautiful, some of it sounds insane, but it's a good read. He was also on an old issue of wired maybe 95 96, which was how I discovered him.
You can model niching and speciation in several ways, by restricting mating by phenotypic or genotypic similarity, or by geography.
--
Marc A. Lepage
Software Developer
Thanks.
[files into mental catalog]
--
Marc A. Lepage
Software Developer
Yes I don't know why Hemos says "the latest book" (although I think it is).
I mention in the review the book dates from 1996.
--
Marc A. Lepage
Software Developer
A GA is a weak search method, meaning it doesn't use domain knowledge in its search. Constrast this with a strong search method, which uses domain knowledge. This is both an advantage and a disadvantage. The former, because it makes the algorithm reusable. The latter, because it doesn't take specific advantage of what you might know about the problem.
The GA is essentially a randomized beam search. It has a random component, but of course this can be characterized statistically. Beam search means it retains a number of search endpoints and explores them in parallel. That makes it quite parallelizable. Contrast with breadth-first or depth-first search.
The basic steps are simple. Produce a random population of chromosomes (i.e. bit strings). Evaluate their fitness (this part is problem specific). That's generation 0. Select the most fit (using biased roulette wheel selection) to reproduce, which means copying them into the next generation's population.
With some high probability, cross 2 parents at some random point. This is crossover. Also, with some low probability, each bit copied might be copied imperfectly. This is mutation.
Fitness-proportionate selection focusses the search on more promising avenues. Crossover builds new promising avenues by combining building blocks. And mutation retains diversity in the gene pool to prevent premature convergence and to help escape local maxima.
Keep doing this until the population converges on the most fit chromosomes. This step, the termination criterion, also can be customized for each problem. The best-of-run chromosome encodes the solution.
The complicated part is the encoding of the problem in the chromosomes (genotype), its decoding (expression into phenotype), and evaluation of fitness. This is problem specific. The key is that although we have a procedure for fitness evaluation, we *cannot* guess in advance what a particular chromosome's fitness is: we *must* evaluate it.
An example is a human: the only effective way to see how well they will do in life, is to run their life and watch them; you cannot predict. If you could predict, the GA would not be appropriate.
A simple example, discussed in the book, is using a GA to search the space of neural network architectures to solve a problem. Each chromosome encodes a grammar for generating a neural network. For fitness evaluation, the grammar is decoded, a neural network is produced, trained, validated, and its performance on the problem is its fitness.
This is a good example, because it is generally very difficult to predict in advance which architectures (e.g., how many hidden nodes) will be best in a neural network, for a particular problem. It usually requires a lot of domain knowledge, and therefore is hard to do on a larger scale, or in a production setting. The GA takes care of that by effectively searching the space of possible neural network architectures.
You can find lots more info in the book, or on the many GA sites on the web.
--
Marc A. Lepage
Software Developer
He didn't say "You could never understand the resulting code", he said "You shouldn't try". This is a good idea simply because it is VERY hard in some cases and not worth it in general. In much the same way you don't need to understand how Homer Simpson works to know that he is a "remorseless eating machine".
IMHO, I think your experience has more to do with issues of data and program representation, perhaps in addition to fitness evaluation, than with genetic programming per se. The algorithm can only explore the solution space that you define.
There is a theory as to how and why GAs work: Holland's Schema Theorem. That should clear up the misunderstanding of how the algorithm works.
As for its mechanics, I recommend examining Goldberg's "Simple Genetic Algorithm" (SGA) implementation. A web search should reveal many versions of it.
--
Marc A. Lepage
Software Developer
I'm reading The Selfish Gene right now!
I also recommend Waldrop's book Complexity (mentioned in my review).
Is Morovec's good? Never heard of it (or can't recall).
--
Marc A. Lepage
Software Developer
Holland's "From Chaos to Order" is actually "Emergence: From Chaos to Order". I haven't read any of Holland's books yet (though I have all of them I think) but reviews suggest "Hidden Order" is better.
--
Marc A. Lepage
Software Developer
GA or GP is usually not appropriate where algorithms are already available. Examples used in text books often use pre-solved problems to make it easier for students to understand the process. Actually evolved programs or evolved solutions are used where standard linear algorithms can't be used. For example, it is very difficult to write an algorithm that looks at pictures and determines if they are ponrographic or not. On the other hand, GA or GP could give us solutions that "help" us in identifying photographs (perhaps using criteria such as flesh toned colors, lighting, etc.). By the way, I know this is a strange example, but I believe geocities actually uses such a program.
Really? You mean, not just *difficult* to understand, but *impossible* ?
As far as I'm concerned, any successful algorithm must lend itself to some kind of analysis by living, breathing humans. The fact that it's very tricky is beside the point. (Or am I just missing the point?)
Once I wrote a project involved with GA, (the goal of the project is something else, not GA). But one of guy who mark the scores know nothing about GA. It's too difficult for me to explain to him, why GA works. So I simply erased the word "genetic" in all papers.
"You should not try to understand the resulting code".... what the HECK is that??? Why should I not try to understand something???
I must have *completely* missed the point here.
I think you guys are confusing two things:
- Code that is difficult and non-intuitive.
- Code that is impossible to understand by humans.
Why should the output of GP necessarily by #2? I find this hard to accept. The fact that it is #1 is irrelevant. But the distinction between #1 and #2 is clear.Or have I totally misunderstood?
I haven't done any GA for a few years but by keeping the best solution after each generation, aren't you liable to fall into a local minimum?
No, you have the best solution of the last generation PLUS the new breed coming from crossover and mutation
Crossover and mutation ensures that you are still searching for new solutions, while elitarism ensure that good solutions don't get lost.
Comments like this are unfit and have a low probability of being allowed to reproduce. As more and more highly fit comments come along the selection pressure will eliminate such comments.
(sigh) if only it were true.
Ok how long till we have a genetic slashdot?
Congratulations brother!
Unfortunately I have a profound mistrust of programs that I don't understand/can't maintain. While there are some areas where GA's can be very nicely applied, mainstream programming most likely won't get to use them much.
I'm more curious about their use in creating faster/cheaper hardware (but that's probably because I'm a software guy).
Unbreakable toys can be used to break other toys.
> AC's, like roaches, will live on, no matter what we do ;-) Yeah but the FP'er wasn't an AC! Power to him! :)
That'll only happen if unfit commenters weigh against a negative selection criterion. As it is, you have just as good a chance to reproduce as anyone else ;-).
--
--
There is no premature anti-fascism. -Ernest Hemingway
Who fucking cares?
"Notwithstanding my simplistic explanation, there's an obvious example right in front of us. Evolution is a relatively simple process (everyone's heard of Darwin, right?) that has produced very complex output (e.g. us).** What if we could harness the power of this evolutionary computation?"
** Disclaimer: Void in Kansas and where prohibited.
I can thoroughly recommend Artificial Life by Steven Levy for anyone who just wants to check out what this whole Artificial Life thing is all about.
One thing I find sorely lacking in many books on algorithms is any discussion of why you would select one over another. If you want to see a shining example of what I'm wanting, take a look at Knuth's _The Art of Computer Programming_ and see how he tests competing algorithms to compare their costs and benefits in actual use. I hope there's something in this book about how one would decide whether or not to use a genetic algorithm.
Now now...don't you know part of the lyrics to Harvy Danger's "Flagpole Sitta"?
;-)
been around the world and found
that only stupid people are breeding
AC's, like roaches, will live on, no matter what we do
--------------------------
Zbignew Michalewicz
Genetic Algorithms + Data Structures = Evolution Programs.
2nd ed., Springer-Verlag, 1994
Comes with useful source code. Is not afraid of equations, but is mostly practical (in this case that stuff works better than the other one).
I have run programs based on code from this book and they worked (didn't help me much 'cause the whole thing is too computationally expensive for my purposes, but that's another story entirely...)
Kaa
Kaa
Kaa's Law: In any sufficiently large group of people most are idiots.
Congradulations on being the 2ND post! Stunning accomplishment!
GAs are just another type of stochastic search, just like Annealing. They search the phase space at random points and converge to the solution with probability 1 (provided that the breeding process uses elitarism, that is the best solution is kept in the next generation).
All nice and good, but it just means that they are optimal when they perform an exaustive search.
they find an "acceptable" solution basically with the same speed as annealing does, just they are cooler (or are percieved as such) and can be used with no modification in discreet problems.
"We would like to believe this", because we are coming closer and closer to understanding how things work. Instead of recreating the human mind (like neural networks), we are trying to model it by observation. Genetic algorithms and genetic programming are an extension of the idea of neural networks, and Stuart Kauffman's biological feedback systems (sorta like cellualr automata). The reason why they are so popular is that they are coming closer to "feeling right" in that they make more sense to us.
Neuaral networks are kludgy, never really made sense to me, there always seemed to be somethine missing. Genetic programming/algorithms are coming closer to how we think we think/function, or how any biological self-organizing system behaves: feedback loops, multi-processing, and fitness according to some (possibly) external stimulus.
Even if genetic algorithms/programming is an extension of neural networks (or even matrix manipulation), who cares? They are interesting and we are getting closer to the idea of "distibuted systems", and here I use the word systems to refer to _any_ collection of entities that communicate in one way or another. After all, isn't the whole universe a system? The question isthen, what are the constituents? Is anything not?
I too was given a big jumpstart into the world of computing when I first read Stephen Levy's artificial life, Dawkins' Selfish Gene, and Moravec's Mind Children.
Those books showed me that we're actually not just playing games and getting political about OS's for no reason. The rise in the importance of technology has been exponantial ever since people started letting down the old rusty barriers against progress.
If already so much synergy results from commerce and society, then the dream of there being such an incredible future spurred me on to do computer studies, and now internet communities.
Of course, not all of the effects of a new sum-of-the-parts are positive, but the way I see it, I have to be here in this profession to make sure it goes the way I'd like it to because it's going to happen anyway.
Also, the actual theory behind alife, genetic algorithms, or even moravec's mad ramblings,
is really complicated and full of boring math and biology (too much for me: that's what I was studying when I read those books), but pop science books on all those matters can't f
ail to show those things to people who wouldn't otherwise have had the patience nor maybe
even the time or disposition to sit figuring out journals & stuff.
In my wanderings around the Web I haven't found a better resource than The Genetic Programming Notebook. It is by far the most comprehensive site I've found. Here you will find everything. The three main topics are:
- Genetic Programming
- Genetic Algorithms
- Artificial Intelligence, including A. Life.
Within each section are tutorials, FAQs, links, bibliographies, papers, journals and generally everything you need to get started and become a GP, GA or A. Life pro.These are very interesting fields which are really coming into their own with the advent of Linux and free software.
Experimenting with these techniques is as easy as downloading an existing library. One of the best is GALib, a library of C++ Genetic Algorithm objects.
Have fun.
I agree entirely. I have found GAs to be useful for certain problems. However, there I have two pet peeves on the topic:
1) GAs are totally unsuited to certain problems. Often a simple gradient search is vastly superior. Some people use GAs all the time just because they're "cool."
2) Almost all the GA code I have seen tries to work in the concepts of "chromosomes," "parents," "populations," etc. That may be suitable for some problems, but often it's an idiotic attempt to force a problem to behave like a biological system. People, drop the biology when it makes no sense for the problem!
As multiprocessing becomes cheaper (thanks in part to Linux), GA's should find more uses. It is very, very easy to parallelize a GA. (You don't need Beowulf to do it.) See September's Linux Journal for a case of a GA designed only to solve a particular mathematical problem concerning White Dwarf stars. No Beowulf here, just a customized, 33-node Genetic Algorithm machine. Cost? A mere $22,000. Not too shabby.
The book has been around for at least 3 years. Good book. GAs have a few problems: they're not guaranteed to find a solution, and they can't be characterized in terms of their running times/space requirements. This doesn't make them easy to market...
I use GAs and NNs together (the GAs design
- ---
the NNs' nodes).
And I have to report from the trenches that
there's something weird about seeing
my simple noddy matrices (thanks Numerical
Recipes) and simplistic gene splicing producing
results that are what I want - without
me even really knowing how....
No, it's absolutely nothing to do with Neurons
or Artificial Life. It just looks as cool,
that's all!! And of course, works better when
you get over the insistence on perfect analogy.
PS - application area? Horse racing!
----------------------------------------
--------------------------------------------
There's a storm a-comin'....
In other words, survival of the fittest is a very naive way of putting it. Both GA's and nature are more complex than that. We need an occasional "first poster" to keep genetic diversity alive.
A GA is basically a randomized beam search. It retains the N best individuals. It allocates more search power to more promising areas, in a roughly exponential fashion. This allows it to zone in on potential solutions. Yet the randomness keeps it from getting locked in, like a depth first search.
Also, it is optimized for "online" performance, where the cost of the search is considered along with the cost of the resulting solution. (In "offline" performance, you don't care about the cost of the search, only of the solution.)
--
Marc A. Lepage
Software Developer
Perhaps it's my view of evolution that needs to change. But I have the intuitive sense that it solves a much higher order of problem.
what most people dont understand is that genetic algorithms are usually pretty simple when explained in normal english rather than mathematical algorithms. Take for example an algorithm to find the shortest path between 2 points in a maze. Using a simple analogy we can consider a number of ants, travelling at the same velocity released from the starting point. When two ants meet, one dies, the other continues. At a fork, the ant "reproduces" to form two or more ants all travelling at the same velocity. Eventually the one which chose the shortest path will reach its destination and you can find the SP by tracing the route back. A sinple GA based SP algorithm. Now when this is put in the form of one or more mathematical equations, very few people have any *hope* of understanding it.
While reading about GAs and their uses, I thought of this... What if someone uses a GA to create some malicious program and defines the fitness set so the most fit programs are the ones that do the most damage, spread the fastest, evade detection the best, etc...
What happens then? In the natural world there are many more obstacles; oceans, vast biological diversity, etc... But in the computing world almost every computer is connected to another in some form. And the basic subsystems are similar enough that a GA based virus could sweep through almost every system on the planet before we had a chance to stop it.
On the other hand, we could always evolve Linux to take over every system on the planet. Of course our buddy Bill could do the same with his little OS...
Go figure.
--bdj
Genetic algorithms, like artificial neural networks aren't nearly as mysterious or romantic as their names imply. Both are straitforward algorithms that employ a bit of matrix math to iteratively create a nonlinear mapping scheme for a system that typically is too difficult or tedious to actually model.
We'd like to believe that we're recreating Darwinian evolution or the behavior of the brain in our computers, but the reality is far simpler and less sexy.
there's a typo in the link to GALib. the proper link is http://lancet.mit.edu/ga
What timing...I just started reading a Microsoft Press book called: "Active Visual J++" by Scott Robert Ladd. In a strange twist of fate, the book is more about Genetic Algorithms than about Java. By chapter four you are programming your own GA and the last chapter in the book is a entitled: "Life with Java," which presents Conway's Life and Brian's Brain in great detail.
For someone totally unaware about GA, it's actually a decent book to start with. The fact that it occationally teaches you something about Java as well is an unexpected bonus.
In Koza's Genetic Programming work, he does in fact interpret the code resulting from a GP. It is a set of LISP functions and terminals. He points out how the resulting solution uses an AND simply for sequencing, how "dead code" had arisen, etc. Obviously it can be done, though it may be difficult. SEGV [no cookie on new server]
a) the algorithms allow for aggregation into more powerful families, (in the traditional "extended" sense where grandchild and grandparent are included for purposes of passing along "real" education from one generation to the next) and/or formation of more powerful groups or guilds (to train young apprentices in complex and long-term technological processes upon which the organisms depend, such as modern technology)?
b) as the individual units? evolve, are they able to organize into political groups, such as Republicans or Democrats or communists or capitalists, wherein each tries by war or subterfuge or corruption of technology to oppress and enslave the other?
c) lastly, does this science have a means of testing, i.e. measuring, a system's reponse to carefully modeled shocks, such as forcasting system response to earthquakes or to progressive moral and economic collapse?
I know these questions seem a little far fetched, but I was just wondering just how far along this science is.
you have waaaaay too much time on your hands my friend :)
Satan, oscillate my metallic sonatas.
Lets write a GPL'd script that checks slashdot periodically for new stories and then immediately posts 1st post if it finds that there's no first post yet =) Cool, eh.
ACI've read an interesting article in the french edition of scientific american, a GA was used to find patterns while playing against human in 'paper scissor rock' like games.
It was used to find patterns in the human play, and it performed quite well.
I wonder if GA could be used for playing GO or other similar games in which minmax-type software are poor.
First off, thanks to all for pointing out the difference between GP and GA. That distinction was obviously lost on me before this thread (guess I better go read the book).
On the idea of understanding the code, mainstream code often requires "adjustments" and maintenance on a regular basis.
From what I understand (please correct me if I'm wrong), in order to make any change to the resultant code I'd have to change my target and completely re-run the algorithms (or at least re-run from some relatively close match). For some generic things, like a search algorithm, you don't really care about the underlying features of the algorithm so long as it works. I'm imagining that this sort of approach is less useful for code that deals with things like changing UI, database access etc. Not only because of the difficulty in defining the "target" when the target is moving, but also because some maintance would be made harder by the inability to understand how the result was achieved (thus forcing you to return to the algorithm, instead of making a quick fix).
Unbreakable toys can be used to break other toys.
Hmmmm......... it may be a book I have to buy. But the one problem with GA's for me at least is the answers they come up with don't perform as well as the answers created by a skilled programmer. Recently I used a GA to program a robot to avoid obsticles, the problem was the controller I wrote myself out-performed the GA by a large margin. In fact in a 10 min. test the robot running the GA's code would hit the wall maybe 5 or 6 times, while it would only hit once at the most using my code. Basically after researching this for awhile I found that the GA's don't work with problems that have lots of bad data (outliers). This makes them useless for most practical applications. Don't get me wrong there still great for crunching numbers or other applications where the data set is really stable. Anyway I think that GA's are great however, I don't think they will ever be used in mainstream computing.
:P
The opinion of a CS undergrad
The book is well written and provides a good summary of the research in the area and especially at Santa Fe over the last decade or so.
The main contribution of Mitchell and others has been to explore GA without the hype surrounding it at that point in time. Langton had come up with the edge of chaos theory and was instrumental in getting lots of people interested in alife. But Langton's main contribution, the so called critical lambda, is in hindsight a lot of hype. (Langton made a important discovery when he designed a self reproducing cellular automata which is probably survive his edge of chaos theory)
Mitchell and others were responsible in steering the subject to more solid grounds and her work
along with Crutchfield on the so called density problem have been very insightful and useful contributions.
GA's are good at providing insights we did not have before to a wide variety of things. For example, using GA's to understand elements of computation (say, by evolving cellular automata), elements of biology (say, as in tierra), self-reproduction (Koza's work) or in ant foraging (lots of papers) are very interesting. But they are not meant to be tools for optimization: GA is not a substitute for linear programming.
Regards
Vinay
--
Last year I got to take a course at RPI in GA's, where we used the Mitchell book. It is a great introduction to the field. We had several practial and fun programming assignments using GALib, a very complete C++ library implementing almost everything described in Mitchel's book. If you're looking for what else is happening in the field, in particular evolutionary computation, I would suggest John Holland's From Chaos To Order.