Genetic algorithms+ data structures= evolution programs PDF

Preview

Summary

Artificial Intelligence ELSEVIER in Medicine Artificial Intelligence in Medicine 9 (1997) 283-287 Book reviews Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, 1996, 3rd revised and extended edition (1st edition appeared in 1992), 387 pp. (hardcover), 68 f...

Description

ELSEVIER

Artificial

Intelligence

in Medicine

9 (1997) 283-287

Artificial Intelligence in Medicine

Book reviews Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, 1996, 3rd revised and extended edition (1st edition appeared in 1992), 387 pp. (hardcover), 68 figures, 36 tables, Price DM 58. The field now called Evolutionary Computation had a slow start. In the late 60s and early 70s a number of researchers in the USA and Germany applied the principles of Darwinian evolution, based on natural selection, for problem solving. Independently from each other they established the power of evolutionary techniques and worked on the theory and applications of their own approach. These were the times of rather separate development of Genetic Algorithms, Evolution Strategies and Evolutionary Programming. From the early 90s it is more and more acknowledged that the different approaches share the same basic principles, while differing only in technical details, terminology and sometimes in the philosophy behind it. In the meanwhile, a new branch, called Genetic Programming, has also emerged and joined the family. The entire family of algorithms is called nowadays the family of Evolutionary Algorithms-a name attempting to cover all the aforementioned techniques, and even more. An Evolutionary Algorithm (EA) can actually be any population-based, stochastic search algorithm that uses a (heuristic) quality measure, called fitness, of candidate solutions and applies reproduction operators to create, and fitness-based selection to reduce, diversity in the population. The book of Z. Michalewicz has an important message that is also reflected in the title. Namely, it advocates the modem view that, regardless to representation (data structures), a problem solver can be seen as ‘evolutionary’ if it is based on the basic reproduction-selection cycle (genetic algorithms). A slight confusion, however, can arise, because the usual terminology identifies genetic algorithms with bit representation. Nevertheless, the title refers to a classic work by N. Wirth (N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, NJ, 19’76) and carries the message that encourages one to create his/her evolutionary algorithm by selecting any appropriate data structure for chromosomal repre sentation and appropriate reproduction operators. In 1992, the year of the first edition, this was a novel and a controversial point. Even today, many practitioners try to remain in the classical framework and use the standard machinery, thus working with a general method. Discussing the hierarchy of evolution programs

(Ch. 14) Michalewicz advocates a broad view extending that of Goldberg’s 1989 book (D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989). According to this new view there is no strict border between a generally applicable evolutionary problem solver and domain specific algorithms. An evolutionary algorithm can be augmented with domain specific knowledge, hereby narrowing its domain of applicability and increasing its performance. This transition from general to problem specific can be done gradually, depending on the extent of domain specific features. It is the corresponding increase in performance that determines how far one should go with this specialization and not the concerns whether the obtained method is still a genetic algorithm, an evolution strategy or any standard evolutionary algorithm. This message is still very relevant and I consider this to be the main contribution of this book. The book is divided into three parts, all together 16 chapters including conclusions, and is extended with four appendices, a reference list and a subject and name index. it provides an introduction to genetic Part I is called ‘Genetic Algorithms’; algorithms (GAS), indeed. By means of three sample problems (numerical function optimization, the iterated prisoners dilemma and the travelling salesman problem) the first chapter shows how the basic ideas can be adapted to different types of problems, and sketches the relationship between GAS, hill-climbing and simulated annealing. In the following two chapters more insight is given into ‘how’ and ‘why’ GAS work; Holland’s classical schema theorem is presented, together with the building block hypothesis and the principle of implicit parallelism, furthermore the phenomenon of deception is explained. A deficiency of this chapter is the lack of criticism on these classical results, although there were heavy discussions on the interpretation of them lately on Internet as well as at different conferences. Selection could be seen as the main theme of Ch. 4, even though the title (GAS: Selected Topics) does not clearly indicate it. The sections on sampling mechanisms, characteristics of the function and varying population size all deal with the problem of allocating the available resources, i.e. making selections, such that premature convergence to a sub-optimal solution can be avoided, or at least delayed. The convergence result based on Banach’s theorem would better fit in a separate chapter on GA convergence, while the case study on the knapsack problem belongs to the issue of constraint handling which is treated extensively later on. The title of Part II, ‘Numerical Optimization’, indicates that this part concentrates on a class of problems to be solved, rather than on algorithms. Especially interesting are Chs. 5 and 6, which discuss GAS with floating point representation and variable (decreasing) mutation strength: features that are well-known in evolution strategies. The case studies show that cross-fertilization between different EA streams is useful, even if the resulting algorithm cannot be simply categorized. Ch. 7 deals with a subject Michalewicz is an expert on. ‘Handling Constraints’ is crucial in any practical application, nevertheless, the traditional EAs are blind to constraints and knowledge on how to coop with constrained problems in an EA is still scarce. In this chapter numerical optimization under general nonlinear constraints is discussed and the author’s GENOCOP (GEnetic algorithm for Numerical Optimization for Constrained Problems) system is presented. New is

Book reviews

285

GENOCOP III, an extension achieving better results and lower standard deviation of results than the former versions. In the last chapter of Part II evolution strategies and other methods, for instance, evolutionary programming and delta coding for numerical optimization, multimodal and multiobjective optimization are presented and compared with GAS. Part III (‘Evolution Programs’) discusses non-standard EAs that are developed for a certain problem class. Arranged around the transportation problem and the travelling salesman problem EAs with 2 dimensional (matrix) chromosomes, respectively order-based representation are presented in Chs. 9 and 10. Ch. 11 demonstrates evolution programs for various discrete problems, in particular for scheduling, time tabling, partitioning and motion planning. Together with Ch. 12, where machine learning applications are discussed these chapters provide a valuable overview of the diversity of problem areas where EAs work and also show the diversity of possible EAs. Ch. 13 is devoted to two types of EAs that form a separate category: evolutionary programming and genetic programming. As I have mentioned before, they form two of the four large streams within Evolutionary Computation. And therefore it is a pity they received only five pages all together. Furthermore, the fact that the evolutionary programming paradigm completely excludes sexual recombination (crossover) and operates solely with mutation is only implicitly brought up. This is, however, one of the main distinguishing features of evolutionary programming, certainly of the later versions generalized to handle numerical optimization problems. The importance of Ch. 14 on the hierarchy of evolution programs has been already stressed above. Technically, it contains a case study demonstrating five EAs ranging from general to problem tailored for the transportation problem. Ch. 15 nicely extends Ch. 14 by discussing evolution programs and heuristics, mainly in the context of constrained optimization. Finally, Ch. 16 contains the conclusions, or rather an overview of important research directions in which a lot of activity and significant results are expected. The appendices provide the reader with useful technical information. Appendix A, B, and C contain the source code of a simple real-coded genetic algorithm, a list of 18 numerical optimization test functions, and a collection of 12 test functions fclr constrained numerical optimization, respectively. Appendix D is especially interesting for those teaching evolutionary computation. Besides listing a number of possible projects (for students) it also touches on the issue of how to evaluate one’s experimental results and how to compare them to the outcomes of other techniques. Summarizing, this book is-of course-not perfect. There are better introductions to genetic algorithms: the treatment of evolution strategies, evolutionary programming and genetic programming could be more extensive, and I would welcome a chapter on evolutionary algorithms and neural networks. But it discusses evolutionary algorithms in a broad perspective, contains the best available treatment of the problem of constraint handling, and it includes many (415) references to important publications making the book useful to active researchers as well as

286

Book rraiews

lecturers. I have been using the earlier editions for my undergraduate course on evolutionary computation and will definitely keep doing so with this last edition. A.E. Eiben

Department

of Computer Science Leiden University The Netherlands

Z=ZZSO933-3657(96)00378-g

Suzanne J. Weghorst, Hans B. Sieburg, Karen S. Morgan (Editors). Medicine Meets Virtual Reality: Health Care in the Information Age, Studies in Health Technology and Informatics, Vol. 29, 10s Press, Amsterdam, 1996, 752 pp., hardcover, US$ 98. Virtual reality (VR) is usually described as an artificial environment, created with methods of computer graphics on high-performance rendering machines, where users wearing head-mounted displays and data-gloves, or using other interfaces, navigate and interact with the scene or each other in (near) real time. VR has become particularly popular for all kinds of simulations, including architectural and military, as well as games. In these applications, both the virtual scenes (e.g. buildings) and the possible types of interactions (e.g. movements) remain comperatively simple. The situation is far more complicated when VR techniques are to be used for applications in medicine. A very up-to-date overview of the state of the art is provided by the book edited by Weghorst, Sieburg, and Morgan. It contains the proceedings of the 4th annual Medicine Meets Virtual Reality (MMVR) conference, held in San Diego in January 1996. The book has 79 chapters, which may be roughly divided into two major categories: VR-based simulation, mostly for educational purposes, and VR as an interface to the real world. Whilst most papers are written from a system designer’s point of view, the clinician’s or user’s perspective is also covered. A major subject in the VR-based simulation category is surgical simulation and training (14 papers). Most of the systems presented focus on non-invasive or minimally invasive (‘keyhole’) procedures, such as endoscopy or laparoscopic (abdominal) surgery. Despite their clear advantages for the patient, the use of these techniques is currently limited by the small number of experienced surgeons and problems such as a limited field of vision, diminished tactile feedback, and loss of spatial orientation. Since other training methods are unsatisfactory, it is hoped that VR will eventually improve this situation. Research areas covered in the book include realistic modeling of the anatomy, its physical properties, surgical instruments, and realistic interaction between these, such as deformation and incision. Another related subject is user interface design. Even the improvement of skills using VR-based training is assessed. Other subjects include the simulation of...