An Introduction to Metaheuristics for Optimization

An Introduction to Metaheuristics for Optimization (Natural Computing Series)
Authors: Bastien Chopard - Marco Tomassini
ISBN-10 书号: 3319930729
ISBN-13 书号: 9783319930725
Edition 版本: 1st ed. 2018
Released: 2018-11-03
Pages: 226 pages
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 but
are 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 the
same 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 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.