Simulated Annealing: Theory and Applications Mathematics and Its Applications Managing Editor: M. HAZEWINKEL Centre for Mathematics and Computer Science, Amsterdam, The Netherlands Editorial Board: F. CALOGERO, Universita degli Studi di Roma, Italy Yu. I. MANIN, Steklov Institute of Mathematics, Moscow, U.S.S.R. A. H. G. RINNOOY KAN, Erasmus University, Rotterdam, The Netherlands G.-C. ROTA,M.I.T., Cambridge Mass., U.S.A. Simulated Annealing: Theory and Applications by P. J. M. van Laarhoven and E. H. L. Aarts Philips Research Laboratories. Eindhoven. The Netherlands "111... Springer-Science+B usiness Media, B. V. Library of Congress Cataloging in Publication Data Laarhoven, Peter J. M. van. Simulated annealing. (Mathematics and ilS applications) Bibliography: p. Includes index. 1. Combinatorial optimization. 2. Aigorithms. 1. Aarts, Emile H. L. II. Title. III. Series: Mathematics and its applications (D. Reidel Publishing Company) QA402.5.L3 1987 511 87-9666 ISBN 978-90-481-8438-5 ISBN 978-94-015-7744-1 (eBook) DOI 10.1007/978-94-015-7744-1 Reprinted with corrections 1988 Reprinted 1989 3-1289-400 ts Reprinted 1992 4-0292-200 ts AII Rights Reserved © 1987 by Springer Science+Business Media Dordrecht Originally published by D. Reidel Publishing Company, Dordrecht, Ho11and in 1987 Softcover reprint ofthe hardcover Ist edition 1987 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanica1 including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner SERIES EDITOR'S PREFACE Approach your problems from the right end It isn't that they can't see the solution. It is and begin with the answers. Then one day, that they can't see the problem. perhaps you will find the final question. O.K. Chesterton. The Scandal of Father 'The Hermit Clad in Crane Feathers' in R. Brown 'The point of a Pin'. van Oulik's The Chinese Maze Murders. Growing specialization and diversification have brought a host of monographs and textbooks or increasingly specialized topics. However, the "tree" of knowledg~ of mathematics and related fields does not grow only by putting forth new branches. It also ·happens, quite often in fact, that branches which were thought to be completely disparate are suddenly seen to be related. Further, the ~d and level of sophistication of mathematics applied in various sciences has changed drastically in recent years: measure theory is used (non-trivially) in regional and theoretical economics; algebraic geometry interacts with physics; the Minkowsky lemma, coding theory and the structure of water meet one another in packing and covering theory; quantum fields, crystal defects and mathematical programming profit from homotopy theory; Lie algebras are relevant to filtering; and prediction and electrical engineering can use Stein spaces. And in addition to this there are such new emerging subdisciplines as "experimental mathematics", "CFD", "completely integrable systems", "chaos, synergetics and large-scale order", which are almost impossible to fit into the existing classification schemes. They draw upon widely different sections of mathematics. This pro gramme, Mathematics and Its Applications, is devoted to new emerging (sub)disciplines and to such (new) interrelations as exempla gratia: - a central concept which plays an important role in several different mathematical and/or scientific specialized areas; - new applications of the results and ideas from one area of scientific endeavour into another; - influences which the results, problems and concepts of one field of enquiry have and have had on the development of another. The Mathematics and Its Applications programme tries to make available a careful selection of books which fit the philosophy outlined above. With such books, which are stimulating rather than definitive, intriguing rather than encyclopaedic, we hope to contribute something towards better communication among the practitioners in diversified fields. Simulated annealing is a perfect example of how introducing ideas from a completely different and at first sight, totally unrelated field may yield large and unexpected benefits. In this case, a completely new and powerful tool for global (combinatorial) optimization. Annealing is the process of heating a solid and cooling it slowly so as to remove strain and crys· tal imperfections. During this process the free energy of the solid is minimized. The initial heating is necessary to avoid becoming trapped in a local minimum. Virtually every function can be viewed as the free energy of some system and thus studying and imitating how nature reaches a minimum during the annealing process should yield optimization algorithms. Just what imitation, i.e. simula· tion, here means mathematically is of course thoroughly explained in the book and so is the under· lying relation with (statistical) physics (cf. Chapter 4 for the latter). The result is the tool called "simulated annealing", which, since its inception in 1982, has become a remarkably powerful tool in global optimization. vi SERIES EDITOR'S PREFACE Nature (and therefore technology) is, of course, full of minimizing processes, another being Maupertuis' least action principle and more tools in optimization may well result from other imita tions of Nature's ways of achieving things with least effort. As a matter of fact the algorithms in B.S. Razumikhin's book "Physical models and equilibrium methods in programming and econom ics" (Reidel 1984) are also based on such ideas. As stated above, simulated annealing as an optimization tool started in 1982, developed quickly and vigorously, and by now it seems to have reached a certain maturity, witness the present volume, the first monograph on the topic. This does not mean that there are no large fascinating problems. For instance, the tool is no panacea and also very little seems to be known about a priori condi tions on optimization problems which say something about how well simulated annealing is likely to perform. Another question is what "cooling speed" is optimal. For these and other aspects one needs experience and expert guidance. This book provides the latter. The unreasonable effectiveness of mathemat As long as algebra and geometry prcx:eeded ics in science ... along separate paths, their advance was slow and their applications limited. Eugene Wigner But when these sciences joined company they drew from each other fresh vitality and Well, if you know of a better 'ole. go to it. thenceforward marched on at a rapid pace towards perfection. Bruce Bairnsfather Joseph Louis Lagrange. What is now proved was once only ima gined. William Blake Bussum, March 1987 Michiel Hazewinkel Contents Preface 1 Introduction ,1 2 Simulated annealing 2.1 Introduction of the algorithm ..... . 7 2.2 Mathematical model of the algorithm 12 1" 3 Asymptotic convergence results 3.1 The homogeneous algorithm .. 17 3.1.1 Introduction ..... . 17 3.1.2 Existence of the stationary distribution 18 3.1.3 Convergence of the stationary distribution. . 20 3.2 The inhomogeneous algorithm. . . . . . . . 27 3.2.1 Introduction ................. 27 3.2.2 Sufficient conditions for convergence . . . . 28 3.2.3 Necessary and sufficient conditions for conver- gence ....................... 35 4: The relation with statistical physics 39 4.1 Introduction........................ 39 4.2 Equilibrium dynamics . . . . . . . . . . . . . . . . .. 40 4.3 Typical behaviour of the simulated annealing algorithm 44 4.4 Phase transitions . . . . . 48 4.5 Relation with spin glasses . . . . . . . . . . . . . . .. 50 6 Towards implementing the algorithm 66 5.1 Introduction .............. . 55 5.2 Conceptually simple cooling schedules 59 viii CONTENTS 5.3 More elaborate cooling schedules . . . . . . . . . . .. 62 5.4 Improvements of the generation mechanism for transi- tions . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6 Performance of the simulated annealing algorithm 77 6.1 Introduction........... 77 6.2 Worst-case performance results . . . . . . . . . . . . 79 6.3 Probabilistic value analysis .............. 82 6.4 Performance on combinatorial optimization problems. 88 1 Applications 99 7.1 Introduction................... 99 7.2 Applications in computer-aided circuit design 100 7.2.1 Introduction 100 7.2.2 Placement................ 101 7.2.3 Routing................. 110 7.2.4 Other applications in computer-aided circuit de- sign ........ . 118 7.3 Applications in other areas 128 7.3.1 Image processing .. 128 7.3.2 Boltzmann machines 131 7.3.3 Miscellaneous applications. 135 8 Some miscellaneous topics 139 8.1 Parallel implementations. 139 8.1.1 General algorithms. 140 8.1.2 Tailored algorithms. 143 8.1.3 Special parallel implementations 147 8.2 Continuous optimization . . . . . . . . . 148 8.2.1 Generalization of simulated annealing to con tinuous problems . . . . . . . . . . . . . . . .. 148 8.2.2 Applications of simulated annealing to continu- ous problems . . . . . . . . . . . . . . . . . .. 151 9 Summary and conclusions 153 Bibliography 151 Index 116 Preface As early as 1953, Metropolis et al. [MET53j proposed an algorithm for the efficient simulation of the evolution of a solid to thermal equi librium. It took almost thirty yearsl before Kirkpatrick et al. [KIR82j and, independently, Cerny [CER85j realized that there exists a pro found analogy between minimizing the cost function of a combina torial optimization problem and the slow cooling of a solid until it reaches its low energy ground state and that the optimization process can be realized by applying the Metropolis criterion. By substitut ing cost for energy and by executing the Metropolis algorithm at a sequence of slowly decreasing temperature values Kirkpatrick and his co-workers obtained a combinatorial optimization algorithm, which they called 'simulated annealing'. Since then, the research into this algorithm and its applications has evolved into a field of study in its own. The authors have witnessed the maturation of this field at close quar ters: at Philips Research Laboratories we have been involved in re search on the theory and applications of simulated annealing since 1983. About a year ago, we concluded that the theoretical basis of the algorithm had reached a certain level of saturation and that ma jor contributions were to be expected predominantly with respect to new applications. It was for this reason that we decided the time was ripe to write a review of the theory and applications of simulated annealing. Time has indeed proved us right: in 1986, we counted some dozens of contributions on applications of simulated annealing 1 Two earlier papers on optimization of continuous functions, [PIN70] and [KHA81], in which the analogy between statistical mechanics and optimization is already noticed, have remained widely overlooked. ix x PREFACE and virtually no major theoretical contributions. Moreover, the past few years a few succinct reviews and overviews appeared: [HAJ85], [BOU86], [WIL86a], [AAR87a] and [AAR87b] (the last two were based on a preliminary version of this monograph), indicating a need for re view papers. The aim of this monograph is to present a thorough treatment of the theoretical basis of the algorithm, to discuss computational experi ence with the algorithm and to review applications of the algorithm in various disciplines. With respect to the last item, we do not even pretend to list completely all existing applications: the area of ap plications is all but open-ended and new ones are reported almost monthly. However, we do aim to give an indication of the large vari ety of applications. While writing a monograph on simulated annealing, a technique which has been successfully applied in so many different disciplines, we were reminded of the following anecdote:2 Once upon a time a fire broke out in a hotel, where just then a sci entific conference was held. It was night and all guests were sound asleep. As it happened, the conference was attended by researchers from a variety of disciplines. The first to be awakened by the smoke was a mathematician. His first reaction was to run immediately to the bathroom, where, seeing that there was still water running from the tap, he exclaimed: "There is a solution!". At the same time, how ever, the physicist went to see the fire, took a good look and went back to his room to get an amount of water, which would be just sufficient to extinguish the fire. The electronic engineer was not so choosy and started to throw buckets and buckets of water on the fire. Finally, when the biologist awoke, he said to himself: "The fittest will survive" and he went back to sleep. In the spirit of this anecdote, we would like to recommend chapter 2 (asymptotic convergence) to mathematicians, chapters 4 and 5 (im plementation aspects) to physicists, chapter 7 (problem solving) to electrical engineers, the complete monograph to combinatorial opti mizers and another book to biologists. A monograph like this could not have been written without the sup- 2This anecdote was originally told by dr. C.L. Liu at the Workshop on Statistical Physics in Engineering and Biology, held in Lech, Austria, in July 1986.