Metaheuristics For Hard Optimization: Methods And Case Studies

Metaheuristics for Hard Optimization J. Dr´eo A. P´etrowski P. Siarry E. Taillard Metaheuristics for Hard Optimization Simulated Annealing, Tabu Search, Evolutionary and Genetic Algorithms, Ant Colonies, … Methods and Case Studies With 140 Figures 123 Johann Dr´eo Professor Patrick Siarry Universit´e Paris XII, Facult´e des Sciences, LiSSi 61 avenue du Ge´n´eral de Gaulle, 94010 Cr´eteil, France Alain P´etrowski Institut National des Télécommunications, 9 rue Charles Fourier, 91011 Evry, France Professor Eric Taillard EIVD, Ecole d’Ingénieurs du Canton de Vaud route de Cheseaux 1, 1400 Yverdon-les-Bains, Switzerland Translator: Amitava Chatterjee Originally published in French by Eyrolles, Paris (2003) under the title: “M´etaheuristiques pour l’optimisation difficile" Book coordinated by Patrick Siarry Library of Congress Control Number: 2005930496 ISBN-10 3-540-23022-X Springer Berlin Heidelberg New York ISBN-13 978-3-540-23022-9 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media. springeronline.com © Springer-Verlag Berlin Heidelberg 2006 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Camera-ready by the Author and SPI Publisher Services Cover design: de’blik, Berlin Printed on acid-free paper SPIN 11009153 62/3141/SPI 543210 Preface Metaheuristics for Hard Optimization comprises of three parts. The first part is devoted to the detailed presentation of the four most widely known metaheuristics: • • • • the the the the simulated annealing method; tabu search; genetic and evolutionary algorithms; ant colony algorithms. Each one of these metaheuristics is actually a family of methods, of which we try to discuss the essential elements. Some common features clearly appear in most metaheuristics, such as the use of diversification, to force the exploration of regions of the search space, rarely visited until now, and the use of intensification, to go thoroughly into some promising regions. Another common feature is the use of memory to archive the best encountered solutions. One common drawback for most metaheuristics still is the delicate tuning of numerous parameters; theoretical results available by now are not sufficient to really help in practice the user facing a new hard optimization problem. In the second part, we present some other metaheuristics, less widespread or emergent: some variants of simulated annealing; noising method; distributed search; Alienor method; particle swarm optimization; estimation of distribution methods; GRASP method; cross-entropy method; artificial immune systems; differential evolution. Then we describe some extensions of metaheuristics for continuous optimization, multimodal optimization, multiobjective optimization and contrained evolutionary optimization. We present some