Chopard B., Tomassini M. An Introduction to Metaheuristics for Optimization

New York: Springer, 2018. — 230 p.Heuristic methods are used when rigorous ones are either unknown or cannot be applied, typically because they would be too slow. A metaheuristic is a general optimization framework that is used to control an underlying problem-specific heuristic such that the method can be easily applied to different problems. In the last two decades metaheuristics have been successful for solving, or at least for obtaining satisfactory results in, the optimization of many difficult problems. However, these techniques, notwithstanding their common background and theoretical underpinnings,
are rather varied and not easy to grasp for the beginner. Most previous books on the subject have been written for the specialist, with some exceptions, and therefore require knowledge that is not always available to undergraduates or scholars coming from other disciplines and wishing to apply the methods to their own problems.
The present book is an attempt to produce an accessible introduction to metaheuristics for optimization for exactly these kinds of readers. The book builds on notes written for full-semester lecture courses that both authors have been giving for about a decade in their respective universities to advanced undergraduate students in Computer Science and other technical disciplines. We realized during our teaching that there were almost no texts at the level we targeted in our lectures; in spite of the existence of several good books at an advanced level, many of those had prerequisites
that were not matched by the typical students taking our courses, or were multi-author compilations that assumed a large body of previous knowledge. Thus, our motivation was to try to write a readable and concise introduction to the subject matter emphasizing principles and fundamental concepts rather than trying to be comprehensive. This choice, without renouncing rigor when needed, should be an advantage for the newcomer as many details are avoided that are unnecessary or even obtrusive at this level. Indeed, we are especially concerned with “how” and “why” metaheuristics do their job on difficult problems by explaining their functioning principles in simple terms and on simple examples and we do not try to fully describe real case studies, although we do mention relevant application fields and provide pointers to more advanced material. One feature that differentiates our approach is probably also due to our respective scientific origins: we are physicists who have done teaching
and research on computer science and interdisciplinary fields and we would like to bring a “computational science” and “complex systems” orientation to the book rather than an application-based one.
The book should be useful for advanced undergraduates in computer science and engineering, as well as for students and researchers from other disciplines looking for a concise and clear introduction to metaheuristic methods for optimization. The contents of the book reflect the choices explained above. Thus, we have given priority to well-known and well-established metaheuristics. After an introductory chapter devoted to standard computability and complexity ideas, we describe a concept that is fundamental in metaheuristics: the search space. After this basic knowledge we
describe the main metaheuristics in succeeding chapters: Tabu search, Simulated Annealing, Ant Colony methods, and Particle Swarms. Chapter 7 contains an introduction to newer metaheuristics, such as Fireflies, which are not yet as well established but which could become important in the near future. Chapters 8 and 9 are devoted to Evolutionary Algorithms. Chapters 1-9 constitute the fundamental part of the book; altogether they present the basic notions that any student and practitioner should possess about metaheuristics. The following chapters are a bit more specialized butare still very accessible from the technical viewpoint. Chapter 10, which is a little more technical than the others, is rather unique in current computer science books at this level as it brings a statistical physics approach to computational complexity. This chapter can be skipped without consequences but the ensemble mean difficulty of a class of random problem instances is a valuable point of view when contrasted with the standard worst-case complexity approach. Finally, Chapters 11 and 12 are devoted to a more detailed statistical study of the performance of metaheuristics and of the structure of problem search spaces.
In keeping with our general philosophy of simplicity, we have deliberately chosen not to present multi-objective and constrained optimization, which are very important in practice but require a number of new concepts to be introduced. In thesame vein, there are no explicit problems for the reader to solve in the book. Theoretical problems doable with pencil and paper would probably be inappropriate for the level of the book; on the other hand, numerical solutions to specific questions would certainly be very useful. Today there exist a number of excellent downloadable open software systems for several languages and environments that cover most of the methods presented in the book. The reader would be well advised to try out
one or more of these and, to this end, we provide a list of suggestions in an appendix.
We would like to thank many colleagues and collaborators for comments and discussions. They have, in one way or another, contributed to our present understanding of metaheuristics. M. Tomassini acknowledges in particular P. Collard,M. Giacobini, G. Ochoa, L. Vanneschi, and S. V´erel for many stimulating discussions during our joint work. He also thanks his former Ph.D. student F. Daolio for his help with several figures and numerical computations in Chapters 8 and 12. We would also like to express our appreciation to the Springer staff, and in particular to Ronan Nugent, whose help and support were key during the whole process. B. Chopard thanks E. Taillard for hints and advice on the Traveling Salesman problem and simulated annealing. He also thanks R. Monasson and G. Semerjian for their feedback on the chapter on computational phase transitions.