An Introduction to Genetic Algorithms (Complex Adaptive Systems) [Paperback]

Melanie Mitchell (Author)

Book Description

ISBN-10: 0262631857 | ISBN-13: 978-0262631853 | Publication Date: February 6, 1998 | Edition: Third Printing

Genetic algorithms have been used in science and engineering as adaptive algorithms for solving practical problems and as computational models of natural evolutionary systems. This brief, accessible introduction describes some of the most interesting research in the field and also enables readers to implement and experiment with genetic algorithms on their own. It focuses in depth on a small set of important and interesting topics -- particularly in machine learning, scientific modeling, and artificial life -- and reviews a broad span of research, including the work of Mitchell and her colleagues.The descriptions of applications and modeling projects stretch beyond the strict boundaries of computer science to include dynamical systems theory, game theory, molecular biology, ecology, evolutionary biology, and population genetics, underscoring the exciting "general purpose" nature of genetic algorithms as search methods that can be employed across disciplines.An Introduction to Genetic Algorithms is accessible to students and researchers in any scientific discipline. It includes many thought and computer exercises that build on and reinforce the reader's understanding of the text.The first chapter introduces genetic algorithms and their terminology and describes two provocative applications in detail. The second and third chapters look at the use of genetic algorithms in machine learning (computer programs, data analysis and prediction, neural networks) and in scientific models (interactions among learning, evolution, and culture; sexual selection; ecosystems; evolutionary activity). Several approaches to the theory of genetic algorithms are discussed in depth in the fourth chapter. The fifth chapter takes up implementation, and the last chapter poses some currently unanswered questions and surveys prospects for the future of evolutionary computation.

Editorial Reviews

Review

"An outstanding introduction to a new and important field of computer science." Tim Watson , The Computer Journal

"This is a useful introduction to the subject and is well worth reading as an entry into evolutionary computing." Chris Robbins , Computing

"This is the best general book on Genetic Algorithms written to date. It covers background, history, and motivation; it selects important, informative examples of applications and discusses the use of Genetic Algorithms in scientific models; and it gives a good account of the status of the theory of Genetic Algorithms. Best of all the book presents its material in clear, straightforward, felicitous prose, accessible to anyone with a college-level scientific background. If you want a broad, solid understanding of Genetic Algorithms—where they came from, what's being done with them, and where they are going—this is the book. John H. Holland, Professor, Computer Science and Engineering,and Professor of Psychology, The University of Michigan;External Professor, the Santa Fe Institute.

About the Author

Melanie Mitchell is Research Professor and Director of the Adaptive Computation Program at the Santa Fe Institute.

Product Details

• Paperback: 221 pages
• Publisher: A Bradford Book; Third Printing edition (February 6, 1998)
• Language: English
• ISBN-10: 0262631857
• ISBN-13: 978-0262631853
• Product Dimensions: 9.9 x 7 x 0.5 inches
• Shipping Weight: 1.1 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (18 customer reviews)
• Amazon Best Sellers Rank: #364,964 in Books (See Top 100 in Books)
  • #6 in Books > Computers & Technology > Programming > Algorithms > Genetic
  • #47 in Books > Computers & Technology > Computer Science > Artificial Intelligence > Machine Learning

More About the Author

Melanie Mitchell was born in Los Angeles, California. She attended Brown University, where she majored in mathematics and did research in astronomy, and the University of Michigan, where she received a Ph.D. in computer science, working with her advisor Douglas Hofstadter on the Copycat project, a computer program that makes analogies. She is currently Professor of Computer Science at Portland State University and External Professor at the Santa Fe Institute, and does research in the fields of artificial intelligence, cognitive science, and complex systems. She lives in Portland, Oregon with her husband and two sons. Melanie blogs about complexity at http://exploringcomplexity.blogspot.com

Customer Reviews

Most Helpful Customer Reviews

82 of 84 people found the following review helpful:

4.0 out of 5 stars Good introduction for such a short book, April 6, 2002

By 

Dr. Lee D. Carlson (Baltimore, Maryland USA) - See all my reviews
(VINE VOICE)    (HALL OF FAME REVIEWER)    (REAL NAME)   

This review is from: An Introduction to Genetic Algorithms (Complex Adaptive Systems) (Paperback)

Although short, this book gives a good introduction to genetic algorithms for those who are first entering the field and are looking for insight into the underlying mechanisms behind them. It was first published in 1995, and considerable work has been done in genetic algorithms since then, but it could still serve as an adequate introduction. Emphasizing the scientific and machine learning applications of genetic algorithms instead of applications to optimization and engineering, the book could serve well in an actual course on adaptive algorithms. The author includes excellent problem sets at the end of each chapter, these being divided up into "thought exercises" and "computer exercises", and in the latter she includes some challenge problems for the ambitious reader.

Chapter 1 is an overview of the main properties of genetic algorithms, along with a brief discussion of their history. The role of fitness landscapes and fitness functions is clearly outlined, and the author defines genetic algorithms as methods for searching fitness landscapes for highly fit strings. An elementary example of a genetic algorithm is given, and the author compares genetic algorithms with more traditional search methods. The author emphasizes the unique features of genetic algorithms that distinguish them from other search algorithms, namely the roles of parallel population-based search with stochastic selection of individuals, and crossover and mutation. A list of applications is given, and two explicit examples of applications are given that deal with the Prisoner's Dilemna and sorting networks. The author also gives a brief discussion as to how genetic algorithms work from a more mathematical standpoint, emphasizing the role of Holland schemas. The reader more prepared in mathematics can consult the references for more in-depth discussion.

The next chapter stresses the role of genetic algorithms in problem solving, beginning with a discussion of genetic programming. Automatic programming has long been a goal of computer scientists, and the author discusses the role of genetic programming in this area, particularly the work of John Koza on evolving LISP programs. In addition, she discusses the current work on evolving cellular automata and its role in automatic programming. The latter discussion is more detailed, this resulting from the author's personal involvement in artificial life research. Those interested in time series prediction tools will appreciate the discussion on the use of genetic algorithms to predict the behavior of dynamical systems, with an example given on predicting the behavior of the (chaotic) Mackey-Glass dynamical system. The author also gives applications of genetic algorithms in predicting protein structure, an area of application that has exploded in recent years, due to the importance of the proteome projects. The area of neural networks has also been influenced by genetic algorithms, and the author discusses how they have replaced the familiar back-propagation algorithm as a method to find the optimal weights.

Chapter 3 is more in line with what the author intended in the book, namely a discussion of the relevance of genetic algorithms to study the mechanisms behind natural selection. She discusses the "Baldwin effect", which gives a connection between what an organism has learned (a small time-scale process) to the evolutionary history of the Earth (a long time-scale process). A simple model of the Baldwin effect is given using a genetic algorithm, along with a discussion of the Ackley-Littman evolutionary reinforcement learning model, which involves the use of neural networks, and which is another computational demonstration of the Baldwin effect. In addition, the author discusses models for sexual selection and ecosystems based on genetic algorithms. These are the "artificial life" models that the author has been involved in, and she gives a very understandable overview of their properties.

Chapter 4 should suit the curiosity of the mathematician or computer scientist who wants to understand the theoretical justification behind the use of genetic algorithms. Again employing the Holland notion of schemas and adaptation as a "tension between exploration and exploitation", the author formulates a mathematical model, called the Two-Armed Bandit Problem, of how genetic algorithms are used to study the tradeoffs in this tension. The level of mathematics used here is very elementary with the emphasis placed on the intuition behind this model, with only a sketch of the model's solution given. To address the role of crossover in genetic algorithms, the author discusses in detail a class of fitness landscapes, called "Royal Road functions" that she and others have developed. The performance of the genetic algorithm employed is then compared against the three different hill-climbing methods. Formal mathematical models of genetic algorithms are also discussed, one of which involves dynamical systems, another using Markov chains, and one using the tools of statistical mechanics. The latter is very interesting from a physics standpoint but is only briefly sketched. The interested physicist reader can consult the references given by the author for further details.

Practical use of genetic algorithms demands an understanding of how to implement them, and the author does so in the last chapter of the book. She outlines some ideas on just when genetic algorithms should be used, and this is useful since a newcomer to the field may be tempted to view a genetic algorithm as merely a fancy Monte Carlo simulation. The most difficult part of using a genetic algorithm is how to encode the population, and the author discusses various ways to do this. She also details various "exotic" approaches to improving the performance of genetic algorithms, such as the "messy" genetic algorithms. One must also choose a selection method when employing genetic algorithms, and the author shows how to do this using various techniques, such as roulette wheel and stochastic universal sampling. In addition, genetic operators must also be chosen in implementing genetic algorithms, and the author emphasizes crossover and mutation for this purpose. Lastly, the values of the parameters of the genetic algorithm, such as population size, crossover rate, and mutation rate must be chosen. The author discusses various approaches to this. Although brief, she does give a large set of references for further reading.

19 of 19 people found the following review helpful:

5.0 out of 5 stars Excellent book, June 15, 2000

By 

Mark (Ottawa, Canada) - See all my reviews

This review is from: An Introduction to Genetic Algorithms (Complex Adaptive Systems) (Paperback)

This is an excellent introductory book on genetic algorithms. It's very concisely written and there are a ton of interesting projects and programs to do. I've done a few of them myself and learned a lot. This book is one of those that I keep going back to and I always find some new idea or thing to try out.

If you're a programmer and have been thinking of getting into genetic algorithms, you won't go wrong with this book. Very highly recommended.

28 of 30 people found the following review helpful:

5.0 out of 5 stars Brief and to the Point, February 20, 2000

By 

Chris McKinstry (South America) - See all my reviews

This review is from: An Introduction to Genetic Algorithms (Complex Adaptive Systems) (Paperback)

This book is brief and to the point. You won't find here pages of source code that you could have easily ftp'd yourself. What you will find is solid theory in a mere 224 pages. This is the quickest and best way to get up to speed on GA's there is. Which is why it is a standard textbook in the field.