×

Ant colony optimization. (English) Zbl 1092.90066

A Bradford Book. Cambridge, MA: MIT Press (ISBN 0-262-04219-3). xiv, 305 p. (2004).
Based on the social behaviors of insects various researchers have developed and investigated corresponding search paradigms to solve optimization problems and especially hard combinatorial optimization problems. The ant system as a dynamic optimization process reflecting the natural interaction between ants searching for food is one such example. The ants’ (or agents’) ways are influenced by two different kinds of search criteria. The first is the local visibility of food, i.e., the attractiveness of food in each ant’s neighborhood. Secondly, each ant’s way through its food space is affected by the other ants’ trails as indicators for possibly good directions. The intensity of trails itself is time-dependent: as time goes by, parts of the trails are “gone with the wind,” meanwhile the intensity may increase by new and fresh trails. With the quantities of these trails changing dynamically, an autocatalytic optimization process is started forcing the ants’ search into most promising regions. This process of interactive learning can easily be modeled for most kinds of optimization problems by using simultaneously and interactively processed search trajectories.
Ant colony optimization starts at the above metaphor of an ant system and enhances it into a general class of methods following a set of biologically inspired ideas and concepts. A population of ants or agents are assumed to indirectly communicate via distributed, dynamically changing information. That is, ant colony optimization is a population based metaheuristic applying cooperation and communication eventually combined with some sort of stochasticity. Certainly, this is a general concept and it needs a great deal of ingenuity to fill it with life and to make it successful when applied to hard optimization problems. Basically, two things can help to do so: on one hand, something that many applications of this paradigm somewhat lack when trying to achieve enhanced performance, namely that it is useful to hybridize with a local search component. On the other hand, learning from this book helps, too.
The book comprises seven chapters starting from a gentle introduction regarding ant systems to more advanced topics in ant colony optimization. Each chapter has a good “handwaving” part letting the reader know what to expect. From this starting point things are developed up to the most recent research developments. Bibliographical remarks help the reader to find appropriate entry points into the literature of the respective chapter. Finally, each chapter is closed with a few “things to remember” and some exercises. Most of these exercises mean that you really have to implement something. Therefore, whoever follows the authors really gets it.
The first chapter provides the basic development of the search paradigm by describing easily derived experimental setups to mimic the ant system behavior. Based on that a simple stochastic model proposed in the literature is recapitulated and put into perspective. Chapter 2 gives simple application hints as well as pointers to commonalities and differences with respect to other well-known metaheuristics. While ant colony optimization implementations are still not yet successfully outperforming state-of-the art algorithms for the travelling salesman problem, this type of application deserves a special chapter to provide generally applicable ideas for permutation type combinatorial optimization problems (Chapter 3). Some theoretical considerations are given in Chapter 4. The subsequent chapters are devoted to various applications in different areas with an emphasis on some routing problem in telecommunications networks. Some concluding remarks and pointers to web resources are provided in Chapter 7 and an appendix.
The book under review provides a very comprehensive treatment of the ant system and ant colony optimization paradigm. As we said, it needs a great deal of ingenuity to fill the overall concepts around ant colony optimization with life to work successfully. This book helps to do so. At its publication date it provides a most comprehensive state-of-the art collection of papers dealing with ant colony optimization and the reader will appreciate all the pointers to existing literature. If you are convinced of ant systems and that ant colony optimization work, then this is “your” book, you will love it. And, what if you are sceptical about ant systems and the ant colony optimization paradigm? Then, nevertheless, you will probably appreciate the professionalism of Dorigo and Stützle in writing things down. You will find that the authors are clever marketing specialists for promoting their paradigm. But you will probably also be confirmed in your scepticism. To summarize, the field of ant colony optimization has matured over almost 15 years and this is where subsequent researchers should start if they want to get the most appropriate entry point. Independent of whether you believe in the paradigm or not, judging on the book as a whole, it is a well done piece of literature.
This review, has (originally been published in Math. Meth. Oper. Res. 63, No. 1, 191–192 (2006)).

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDFBibTeX XMLCite