Springer最​新​出​版​(​2​0​1​6​年​1​0​月​)​的​智能​优​化​方​面​的​电​子​书​：​贪​婪​随​机​自​适​应​搜​索​算​法​-​G​R​A​S​P​,​作​者​是​该​算​法​的​创​始​人​，具有国际重大影响。​作​者​：​R​e​s​e​n​d​e​,​ ​M​a​u​r​i​c​i​o​ ​G​.​C​.​,​ ​R​i​b​e​i​r​o​,​ ​C​e​l​s​o​ ​C​.
Mauricio g c. resende o celso c. ribeiro Optimization by grasP Greedy randomized Adaptive Search Procedures ② Springer Mauricio g. c. resende Celso c. ribeiro Modeling and Optimization Group(mop) Instituto de ciencia da computacao Amazon. com. Inc Universidade Federal fluminense Seattle WA. usa Niteroi. Rio de janeiro. brazil ISBN978-1-4939-6528 ISBN978-1-4939-6530-4( e Book) DOI10.1007/978-1-4939-6530-4 Library of Congress Control Number: 2016948721 o Springer Science+Business Media New York 2016 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed The use of general descriptive names, registered names, trademarks, service marks, 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 The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer Science+Business Media LlC The registered company address is: 233 Spring Street, New York, NY 10013, U.S.A In memory of David Stifler Johnson Foreword In recent years, advances in metaheuristics have given practitioners a powerful framework for making key decisions in problems as diverse as telecommunications network design and supply chain planning to scheduling in transportation systems GRASP is a metaheuristic that has enjoyed wide success in practice, with an extraor- dinarily broad range of applications to real-world optimization problems. Starting from the seminal 1989 paper by Feo and resende, over the past 25 years, a large body of work on greedy randomized adaptive search procedures has emerged. a vast array of papers on grasp have been published in the open literature, and numer- ous MSc and phd theses have been written on the subject. This book is a timely and welcome addition to the metaheuristics literature, bringing together this body of work in a Single volume. The account of GRasP in this book is especially commendable for its readabil ity, covering many facets of this metaheuristic, such as solution construction, local search, hybridizations, and extensions. It is organized into four main sections: in- troduction to combinatorial optimization, fundamentals of heuristic search, basic GRASP and advanced topics the book can be used as an introductory text not only to grasp but also to combinatorial optimization, local search, path-relinking and metaheuristics in general. For the more advanced reader, chapters on hybridiza tion with path-relinking and parallel and continuous grasP present these topics in a clear and concise fashion The book additionally offers a very complete annotated bibliography of GrasP and combinatorial optimization For the practitioner who needs to solve combinatorial optimization problems, the book provides implementable templates for all algorithms covered in the text This book with its excellent overview of the state of the art of grasp. should appeal to researchers and practitioners of combinatorial optimization who have a need to find optimal or near-optimal solutions to hard optimization problems Boulder. Co. uSa Fred Glover May 2016 Preface Greedy randomized adaptive search procedures, or grasP, were introduced by T. Feo and M. resende in 1989 as a probabilistic heuristic for solving hard set covering problems. Soon after its introduction, it was recognized as a general pur- pose metaheuristic and was applied to a number of other combinatorial optimization problems, including scheduling problems, the quadratic assignment problem, the satisfiability problem, and graph planarization. At the Spring 1991 ORSA/TIMS meeting in Nashville, T Feo and M. resende presented the first tutorial on grasP as a metaheuristic, which was followed by their tutorial published in the Journal of Global optimization in 1995. Since then grasP has gained wide acceptance as an effective and easy-to-implement metaheuristic for finding optimal or near-optimal solutions to combinatorial optimization problems This book has been many years in planning. Though many books have been writ ten about other metaheuristics, including genetic algorithms, tabu search, simulated annealing, and ant colony optimization a book on grasp had yet to be published Since the subject has had 25 years to mature we feel that this is the right time for such a book. After Springer agreed to publish this book, we began the task of writing it in 2010 We have been collaborating on the design and implementation of grasP heuris tics since 1994 when we decided at the tiMs XXXII International meeting in An- chorage, Alaska, to partner in designing a GrASP for graph planarization. Since then, we have worked together on a number of papers on GrAsP, including three highly cited surveys This book is aimed at students, engineers, scientists, operations researchers, ap plication developers, and other specialists who are looking for the most appropriate and recent GRASP-based optimization tools to solve particular problems. It focuses on algorithmic and computational aspects of applied optimization with grasP. Emphasis is given to the end user, providing sufficient information on the broad spectrum of advances in applied optimization with grasP. The book grew from talks and short courses that we gave at many universities, companies, and conferences. Optimization by grasP turned out to be not only a book on grasp but also a pedagogical book on heuristics, metaheuristics and its Presa basics, foundations, extensions, and applications. We motivate the subject with a number of hard combinatorial optimization problems expressed in simple descrip tions in the first chapter. This is followed by an overview of complexity theory that makes the case for heuristics and metaheuristics as very effective strategies for solving hard or large instances of the so-called intractable NP-hard optimization problems In our view, most metaheuristics share a number of common building blocks that are combined following different strategies to overcome premature lo cal optimality. such building blocks are explored for example, in the chapters or sections on greedy algorithms, randomization, local search, cost updates and candi- date lists, solution perturbations and ejection chains, adaptive memory and elite sets path-relinking, runtime distributions and probabilistic analysis tools, parallelization strategies, and implementation tricks, among other topics. As such, preliminary ver sions of this text have been used in the last three years as a textbook for the course on metaheuristics at the graduate program in computer science at Universidade Fed eral Fluminense, Brazil, complemented with specific reading material about other metaheuristics, where it has matured and was exposed to criticisms and suggestions from many students and colleagues. The book begins in Chapter I with an introduction to optimization and a discus sion about solution methods for discrete optimization, such as exact and approxi- mate methods. including heuristics and metaheuristics We then provide in Chapter 2 a short tour of combinatorial optimization and computational complexity, in which we introduce metaheuristics as a very effective tool for approximately solving hard optimization problems This is followed in Chapter 3 with solution construction methods, includin greedy algorithms and their relation to matroids, adaptive greedy and semi-greedy algorithms, and Solution repair procedures Chapter 4 focuses on local search. We discuss solution representation, neigh- borhoods, and the solution space graph. We then focus on local search methods, covering neighborhood search strategies, cost function updates, and candidate list strategies. Ejection chains and perturbations as well as other strategies to escape from local optima are discussed Chapter 5 introduces the basic GrasP as a semi-greedy multistart procedure with local search. Techniques for accelerating the basic procedure are pointed out Probabilistic stopping criteria for GrASP are also discussed. The chapter concludes with a short introduction to the application of GrasP as a heuristic for multiobjec tive optimization Chapter 6 focuses on time-to-target plots(or runtime distributions) for compar ing exponentially distributed runtimes, such as those for GrasP heuristics, and runtimes with general distributions, such as those for GRASP with path-relinking Runtime distribution will be extensively used throughout this book to assess the performance of stochastic search algorithms Extended graSP construction heuristics are covered in Chapter 7. The chapter begins with reactive GrasP and then covers topics such as probabilistic choice of the construction parameter, random plus greedy and sampled greedy constructions, construction by cost perturbation, and the use of bias functions in construction Preface The chapter continues with the use of memory, learning, and the proximate optimal- ity principle in construction, pattern-based construction, and Lagrangean grasP. Path-relinking is introduced in Chapter 8. The chapter provides a template for path-relinking and discusses its mechanics and implementation strategies. Other topics related to path-relinking are also discussed in this chapter. This includes how to deal with infeasibilities in path-relinking, how to randomize path-relinking, and external path-relinking and its relation to diversification The hybridization of grasp with path-relinking is covered in Chapter 9. The chapter begins by providing motivation for hybridizing path-relinking with GrasP to provide grasp with a memory mechanism. It then goes on to discuss elite sets and how they can be used as a way to connect GRASP and path-relinking. The chap ter ends with a discussion of evolutionary path-relinking and restart mechanisms for GRASP with path-relinking heuristics The implementation of GrasP on parallel machines is the topic of Chap- ter 10. The chapter introduces two types of strategies for parallel implementation of GRASP: multiple-walk independent-thread and multiple-walk cooperative-thread strategies. It then goes on to illustrate these implementation strategies with three ex amples: the three-index assignment problem, the job shop scheduling problem, and the 2-path network design problem Continuous grasP extends grasp heuristics from discrete optimization to continuous global optimization This is the topic of chapter ll. After establish ing the similarities and differences between GrASP for discrete optimization and continuous GrasP (or simply C-GrasP), the chapter describes the construction and local search phases of C-GrasP and concludes with several examples apply ing C-GrasP to multimodal box-constrained optimization The book concludes with Chapter 12 where four implementations of GrasP and GRASP with path-relinking are described in detail. These implementations are for the 2-path network design problem, the graph planarization problem, the unsplit table network flow problem, and the maximum cut problem Each chapter concludes with bibliographical notes Writing this book was certainly a long and arduous task, but most of all it has been an amazing experience. The many trips between Holmdel, Seattle, and rio de Janeiro and the periods the authors spent visiting each other along the last six years have been gratifying and contributed much to fortify an already strong friendship We had a lot of fun and we are very happy with the outcome of this project. We will be even happier if the readers appreciate reading and using this book as much as we enjoyed writing it Seattle WA.USa Mauricio g.c. resende Rio de janeiro. r]. brazil Celso C. ribeiro ay2016 Acknowledgments Over the years, we have collaborated with many people on research related to topics covered in this book. We make an attempt to acknowledge all of them below, in alphabetical order, and apologize in case someone was omitted from this long list James abello, Vaneet Aggarwal, Renata Aiex, Daniel Aloise, Dario Aloise, Adri ana Alvim, Diogo Andrade, Alexandre Andreatta, David Applegate, Aleteia araujo Aaron Archer, Silvio Binato, Ernesto Birgin, Isabelle Bloch, Maria Claudia Boeres Maria Cristina Boeres, Julliany Brandao, Luciana Buriol, Vicente Campos, Suzana Canuto, Sergio Carvalho, W.A. Chaovalitwongse, Bruno Chiarini, Clayton Com mander, abraham duarte, Alexandre duarte, christophe duhamel, sandra duni Ekisoglu, Joao Lauro Faco, Djalma Falcao, Haroldo Faria Jr, Tom Feo, Eraldo Fernandes, Daniele Ferone, Paola Festa, Rafael Frinhani, Micael Gallego, Fred Glover, Fernando Carvalho-Gomes, Jose Fernando goncalves, Jose luis gonzalez- Velarde, Erico Gozzi, Allison Guedes, William Hery, Michael Hirsch, Ruben Inte rian, David Johnson, Howard Karloff, Yong Li, X Liu, David Loewenstern, Irene Loiseau. abilio Lucena. Rafael marti. Cristian martinez. simone martins ger aldo mateus. Thelma mavridou. Marcelo Medeiros. Rafael Melo, Claudio mene ses. Renato moraes. Luis moran -mirabal. Leonardo musmanno fernanda naka mura. Maria nascimento Thiago noronha. Carlos oliveira. Panos Pardalos Lu- ciana pessoa. alexandre plastino, Leonidas pitsoulis marcelo prais Fabio protti Tianbing Qian, Michelle Ragle, Sanguthevar Rajasekaran, Martin Ravetti, Vinod Rebello, Lucia Resende, Alberto reyes, Caroline rocha, Noemi rodriguez, Isabel Rosseti, Jesus sanchez-Oro. Andrea dos santos Ricardo silva. Stuart Smith. Cid de souza. mauricio de souza. reinaldo souza. Fernando stefanello. Sandra Su darksy, Franklina Toledo, Giorgio de Tomi, Gerardo Toraldo, Marco Tsitselis, Ed uardo Uchoa, Osman Lular, Sebastian Urrutia, Reinaldo vallejos, Alvaro Veiga, Ana Viana, Dalessandro Vianna, Carlos Eduardo vieira, Eugene vinod, and renato Werneck The authors are particularly indebted to Simone Martins for her careful revision of this manuscript. We are also very thankful to Fred Glover for kindly agreeing to write the foreword of this book