Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Genetic algorithms + data structures = evolution programs (2nd, extended ed.)
Michalewicz Z., Springer-Verlag New York, Inc., New York, NY, 1994. Type: Book (9783540580904)
Date Reviewed: Aug 1 1995

The idea of using genetic algorithms for optimization problems is so intuitively appealing that it is often mentioned in popular science articles. This book is a self-contained account, presupposing only basic undergraduate mathematics. Being based on various papers by the author, it is “not really a textbook” in style (for example, it has no exercises), but in fact would be quite usable as a course text. This second edition adds various topics, such as varying population size implementations and constraint handling techniques for the knapsack problem, and corrects typos.

The flavor of the book can be illustrated by one of the topics, the nonlinear transportation problem. Mathematically, there is a feasible set of matrices v = ( v i j ), defined as the set of matrices with nonnegative entries and with certain prescribed row and column sums. Also, a nonnegative matrix ( c i j ) and a nonnegative function f ( c , x ) are given. The problem is to find a feasible matrix v that minimizes the objective function F ( v ) = ∑ i j f ( c i j , v i j ). An algorithm GENETIC-2 is proposed and studied via simulation. Here is a brief description of the algorithm, with typical parameter values in parentheses. An initial population (size 40) of feasible matrices is chosen by a simple randomized procedure. To generate an individual v in the next generation, choose at random from the current generation two individuals v1 and v 2 with probabilities proportional to F ( v i ). With a certain probability (0.75), set v = v 1. With a certain probability (0.05), perform a crossover by setting v = &ggr; v 1 + ( 1 - &ggr; ) v 2 for a constant &ggr; (0.35). With the remaining probability (0.2), construct v from v 1 via a mutation procedure, as follows. Pick random sets R, C of rows and columns. Set v = v 1 outside R × C. On R × C, generate the values of v by a simple randomized procedure designed to give a submatrix with row and column sums equal to those of the submatrix of v 1. Two different procedures are used (with a chance of 0.5 each): one is intended to produce submatrices nearer the center of the feasible region, and the other is intended to produce submatrices nearer the boundary of the feasible region.

This is an example of what the author calls an evolution program, to distinguish it from a genetic algorithm, in which feasible solutions are explicitly coded as binary strings. Other evolution programs are described for other problems, including traveling salesperson, drawing directed graphs, scheduling, path planning in a mobile robot environment, and machine learning.

Readers’ opinions of this book are likely to be determined by their prior tastes and experience. The book succeeds as an introduction to the subject. Its strength is in discussing the numerous variations of the details of setting up genetic algorithms and evolution programs. I particularly liked the one-paragraph summaries of research papers that analyze such variations. Nonexperts who read the book will certainly learn some new tricks they would not think of for themselves. As a nonexpert, I cannot judge how well the selection of topics covers the range of problems for which evolution programs may be useful (ironically, one of the most popular application areas, stock market strategies, is never mentioned). Readers with theoretical tastes may be less satisfied. The lack of visible theoretical guidelines behind the choice of specific mutation and crossover operators is a little disconcerting, the book’s one foray into non-elementary mathematics (the fixed-point theorem for contraction mappings) reveals hopeless confusion, and the explanations of how and why these algorithms work hardly go beyond the commonsense heuristics of the “building-block hypothesis.”

Reviewer:  D. Aldous Review #: CR118780 (9508-0569)
Bookmark and Share
 
Miscellaneous (F.2.m )
 
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Miscellaneous": Date
An efficient algorithm for sequential random sampling
Vitter J. (ed) ACM Transactions on Mathematical Software 13(1): 58-67, 1987. Type: Article
Aug 1 1988
How to sign given any trapdoor permutation
Bellare M., Micali S. Journal of the ACM 39(1): 214-233, 1992. Type: Article
Oct 1 1994

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy