Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Science Books Media Book Reviews

Review: An Introduction to Genetic Algorithms 77

Posted by Hemos from the the-most-fun-with-nucleotides dept.
One of the pre-eminent reviewers on Slashdot, SEGV, has returned with a review of something a bit more esoteric than our normal book review fare. Melanie Mitchell's latest work, An Introduction to Genetic Algorithms, is the subject of today's review, and is well worth the reading for those interested in said subject. Click below to find out more.
An Introduction to Genetic Algorithms
author Melanie Mitchell
pages 209
publisher rating 8/10
reviewer SEGV
ISBN
summary An excellent, brief introduction to a fascinating field. ISBN 0-262-63185-7 (PB), 0-262-13316-4 (HB)

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
This discussion has been archived. No new comments can be posted.

Review: An Introduction to Genetic Algorithms More

Review: An Introduction to Genetic Algorithms

Comments Filter:
  • 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 [ornl.gov]. 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 [ornl.gov] 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 [anl.gov] make derivative computations easy to program.

    Some helpful optimization links:

    Decision Tree for Optimization Software [asu.edu]

    GA Archives [navy.mil]
  • 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).
  • Actually, it is not GA's themselves, which are clearly an effective optimisation scheme for some problems, but the hype and worshipful awe they attract.

    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.
  • Thanks.

    [files into mental catalog]
  • 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.
  • 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.
  • 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.
  • 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).
  • 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.

  • Re:Very expensive data compression (Score:1)

    by Anonymous Coward
    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.
  • 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.
  • 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?
  • 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).
  • 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 ;-).

    --
  • "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
  • 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.
  • Actually, genetic refers to the way the algorithms BEHAVE. These are optimization algotrithm, ie they search for the minimum (maximum) of a given function in a given domain and they do so "breeding" together the best solutions avaiable at each "generation"

  • Re:Love the concept of GAs but.... (Score:1)

    by Anonymous Coward
    Well, they're not actually impossible to understand, merely difficult. This is due to the fact that these algorithms are usually judged merely on whether or not they get the right answer, not so much on how they get it. This leads to inefficient but correct coding. For example, an algorithm to calculate the average of two numbers might take the first number, double it, then add one to it, then subtract one, then divide by two, and only then might it add the two numbers in question and divide by two. The first handful of steps have a net effect of zero - the answer is right, but why the hell bother with all the rigamarole? Well, they're randomly generated. I have done a little fooling around with them myself and _do_ think that this stuff is worthwhile. I've definitely seen the machine figure out stuff that I couldn't - embarrassing, but true. I had put together a simple little assembly style language with a simple commands, like ADD, SUB, SHL (bit-shift left), SHR, etc. As a simple first test I gave it two numbers and asked for the average. Again, keeping things simple it was all integer arithmetic, etc. Shortly I had my anser and it looked like the stuff I described above, only worse sometimes (I ran it a bunch of times to see what crazy stuff I could get!). Then I decided to move on to a harder problem - find the average of three numbers. It struck me that in my mini-assembly language I didn't have a divide or multiply command - only SHL and SHR, i.e., multiply and divide by two. So once it got the sum of the three inputs, how was it going to divide by three? I couldn't see how. So I just gave it one number and asked it to give me that number divided by three - an equivalent problem. I didn't know if it could solve it, because I couldn't. It's solution (after removing all the noise of extraneous useless and/or ineffective instructions) was to take the initial number and SHL twice and set that result aside. Then again take the initial number and do a SHL three times. Then add the two together and voila!, you have the right result! Does this really work? Not really, at least not as a fully general solution. What it was doing was finding 1/4 of the number plus 1/8 of the number, which equals 3/8 of the original, number, which is close to 1/3. Given that I was using integer arithmetic, rounding caused the numbers to come out right (at least for the numbers I had randomly chosen for it.) Clever, no?
  • "Genetic Algorithms" are a different than "Genetic Programming" (see Koza's two (or more) books on genetic programming).

    Genetic algorithms generally solve "problems" by efficiently searching some problem space, often a large or poorly understood one, to attain some fitness criteria. If you can define what is "better" in terms of a solution they are a potential choice. They are not mysterious in terms of the programming.

    Genetic programming on the other hand is evolving a program (most often in a interpreted language like LISP) to accomplish some task. These programs can indeed be rather hard to understand and unravel because the evolved code is unlikely to follow human logic or program construction rules. In all honesty I've not played much with genetic programming because I'm not dead certain what it's good for (but it is interesing).
  • "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 [world-of-dawkins.com], and Moravec's Mind Children [cmu.edu].

    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.

  • As jhobson pointed out, Mitchell does cover this in a section or two.

    She also briefly discusses Goldberg's work with hybrid GAs, which I recently read in more detail in Golberg's book.

    Basically, this is where a GA searches the global space quickly, then another domain-specific routine kicks in to quickly finish searching the local space.
  • I have played around some with Genetic Algorithms and have found them interesting and useful for a variety of optimization and problems solving tasks.

    In my wanderings around the Web I haven't found a better resource than The Genetic Programming Notebook [geneticprogramming.com]. 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 [mit.edu], 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 somebody has already pointed out above, many of the examples given in text books are not typical real world problems solved with Genetic Algorithms (GA). More typical would be:
    • Complex mathematical solutions or optimizations in which conventional methods fail or are problematic. GA helps here because conventional methods tend to concentrate their energies on local features whereas a good GA will continue to act globally even when it's found a fairly optimum solution.
    • Nonmathematical problems which lack analytical solutions.but where the construction of input parameters (the chromosome encoding) and a fitness function (how well does a candidate solve the problem) can be constructed. This family of solutions could be just about anything. Game playing comes to mind as a candidate here. How about a game of global thermonuclear war?
    • GA's have shown themselves to be very useful in assisting other techniques. For instance, the training of a neural network can be accelerated with GA's. Often a GA is biased with knowledge of the solution domain that strict, blind Darwinistic evolution could not have. This is why GA's are often used to accelerate other techniques--even other GAs.

    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 [linuxjournal.com] 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!
    ----------------------------------------- ---
  • What you describe is a classic example of why Genetic Algorithms work so well in some particularly knotty mathematical domains. This is why you should never throw out all the bad cases. No matter how bad a candidate is, it may spawn a champion. For the mathematician it means that GA's continue to search globally even after a candidate global solution has been found.

    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.)
  • Once it's created, you can tinker with it all you want.

    You might think that, but it's not true. Most genetic algorithms are structured such that humans cannot understand them, let alone modify them successfully. They usually use methods that humans would never have thought of, either.
    ---
  • the way I see it is that GP uses GA. The state space is "computer code" instead of numbers, but other than that there is nothing new. You should not try to understand the resulting code, it is just the code that behaves best against your target. just like most learning algorithms for classification problems, you sould not care if there is a logic in it, as long as it solves your problem.
  • Hmm... maybe what needs to happen with Computer Science and Genetic Programming/Genetic Algorithms is what has happened in Physics with Quantum Mechanics and Relativistic mechanics, both of which still cause problems for undergrads, grads, and laymen... (and even some PhDs...)

    QM is not intuitive, and is based on statistical probabilities, not deterministic solutions. GA/GP seems to fit this realm as well.

    The problem people will have is a genetic algorithm that might "evolve" for a tough problem that people can't exactly figure out deterministically how/why it works, except to examine its output for validity. This freaks people out. If such an algorithm is to be used in control software, then do what airplane engineers do on fly-by-wire systems: put in redundant systems that have some checks-and-balances with each other and more than one fail-over mode, in other words, cover your ass. The reason they do this in FBW is because FBW systems are essentially very dynamic open-loop feedback systems, and the goal is to keep the plane flying in a more-or-less non-chaotic mode, even at some extreme inputs, or if it is in a chaotic mode, make sure that it's recoverable from. With all the feedback loops in a plane...

    The arguments people have against FBW in, say, passenger aircraft, has sounded an awful like the arguments people are using now against GA/GP.
    "We can't understand 100% the program, and don't have a 100% certainty about the program." My question is, why do we need to do this?

    Look at other important control systems: We involve the most chaotic computer systems in the world as their main control system: people, don't we? Are not people fallable? Yes they are. Just look at Homer Simpson...

    We even still let people fly airplanes, too. But I guess we've grown accustomed to the risks inherent in flying commercial air, and accept them so we don't have to drive across the pacific or Atlantic oceans...
  • ...wouldn't you use the same things you always use, your expected application and its expected worst-case scenarios?

    How would you test sorting algorithms, for instance? You pass it pre-ordered sets. You pass it big sets. You pass it small sets. You watch memory usage. You watch the stopwatch. You run it on a loaded system. You run it on an unloaded system. Etc.

    In the end, you look at your results and say, "This is the algorithm for this project." But we like a one-size-fits-all solution, and GA/GP might not provide us with those.

  • While reading Levy's book and some other sources I remember coming away with the disturbing sense that what I was looking at was not really evolution but rather a very expensive form of data compression. OK, after an enormous number of trials we manage to "evolve" a virtual ant that can successfully navigate a virtual maze. We could hard-code the same behavior, but the result is ususally not an optimal solution in terms of the space required. By definition our programming language & interpreter will contain a lot of stuff that solves for the general case. So, to mash up a bunch 'o bits and execute that at some very low level of the machine can after enough trials (& selection) produce a smaller (combined 'code' & 'data') chunk that will accomplish the same goal.



    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...
  • What's weird about this one is that it wasn't even anonymous - you could all flame the guy for being stupid if you wanted to.

    Go figure.

    --bdj

  • I taught a class on genetic algorithms last year and actually assigned this book as the main reading. It's very readable and well organized. To answer mwood's question, she does include a section on when Genetic Algorithms are useful, what sort of problems they're good at or have trouble with.
  • 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.
  • Properly done, a genetic algorithm will be both correct and efficient, as one of the things that can be bred for is speed (ie efficiency).
    ---
  • you have waaaaay too much time on your hands my friend :)
  • I'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.
  • What you described is essentially the way real virii evolve. Thus an immediate solution comes to mind: evolve some kick ass anit-virus software. Every computer would necessarily require an immune system that's capable of evolving "antibodies" capable of detecting and destroying invading virii.

    I like this idea. Next thing you know, system administration will become more like being a zookeeper. :)

  • 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).
  • 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.

    The opinion of a CS undergrad :P
  • 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
  • Just a clarification on your observations about fly-by-wire systems on aircraft. I think you are confusing the need for fly-by-wire systems with the need for flight stabilization. Meaning: some modern fighter aircraft (most notably the Mirage series and all Stealth aircraft) are inherently unstable in flight --i.e. they cannot maintain level flight on their own or under human control. Enter active control systems which stabilize the aircraft by feeding a huge number of command inputs (turns, pitches, thrust fluctuations) to the flight system: these inputs cannot be controled/sustained by either a human or any sort of mechanical device. This is why FBW is necessary in a lot of combat aircraft.

    In civil aircraft, OTOH, fly-by-wire is being adopted (mostly by Airbus) because it's cheaper: instead of running 2 and 3 lines of hydraulics throughout the plane, you run 2 FBW (and, coming up, fly-by-light) lines and 1 hydraulic as a backup. FBW has become affordable because it has been used (and understood) in military machines.

    Redundancy in aircraft systems is not because engineers do not understand/trust the control code, but because this is how aircraft are built. Any aircraft is built to at least 125% to 150% of the needed specs (so say, if the strongest recorded cross-wind is, I dunno, 60 mph, an aircraft will be designed to accommodate 90 mph). And for vital systems/parameters this margin (of safety, not error) goes up to 200% and 300%.

    I am sure that when and if GAs become good enough to be put on planes, they will be --aerospace firms are traditional early adopters-- but there will always be a backup.

    Next time you fly an airliner and the passengers applaud the landing, thinking they are congratulating a pilot, know that most likely the pilot was a backup for a real-time autopilot system ;-)...

    Don't you wish PCs were built this way? ;-)...


  • The irony being that your comment, which was marked up, is a descendant of the one you refer to. Thus proving that survival of the fittest does not apply to Slashdot - survival of the lamest is another matter...

    --

  • Last year I got to take a course at RPI [rpi.edu] 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 [mit.edu], 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.

Slashdot Top Deals

Kleeneness is next to Godelness.

Close