Optimization by GRASP-ebook-2016
Springer最新出版(2016年10月)的智能优化方面的电子书：贪婪随机自适应搜索算法-GRASP,作者是该算法的创始人，具有国际重大影响。作者：Resende, Mauricio G.C., Ribeiro, Celso C.Mauricio g c. resende o celso c. ribeiroOptimization by grasPGreedy randomized Adaptive SearchProcedures②SpringerMauricio g. c. resendeCelso c. ribeiroModeling and Optimization Group(mop) Instituto de ciencia da computacaoAmazon. com. IncUniversidade Federal fluminenseSeattle WA. usaNiteroi. Rio de janeiro. brazilISBN978-1-4939-6528ISBN978-1-4939-6530-4( e Book)DOI10.1007/978-1-4939-6530-4Library of Congress Control Number: 2016948721o Springer Science+Business Media New York 2016This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part ofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitationbroadcasting, reproduction on microfilms or in any other physical way, and transmission or informationstorage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodologynow known or hereafter developedThe use of general descriptive names, registered names, trademarks, service marks, etc in this publicationdoes not imply, even in the absence of a specific statement, that such names are exempt from the relevantprotective laws and regulations and therefore free for general useThe publisher, the authors and the editors are safe to assume that the advice and information in this bookare believed to be true and accurate at the date of publication. Neither the publisher nor the authors orthe editors give a warranty, express or implied, with respect to the material contained herein or for anyerrors or omissions that may have been madePrinted on acid-free paperThis Springer imprint is published by Springer NatureThe registered company is Springer Science+Business Media LlCThe registered company address is: 233 Spring Street, New York, NY 10013, U.S.AIn memory ofDavid Stifler JohnsonForewordIn recent years, advances in metaheuristics have given practitioners a powerfulframework for making key decisions in problems as diverse as telecommunicationsnetwork design and supply chain planning to scheduling in transportation systemsGRASP is a metaheuristic that has enjoyed wide success in practice, with an extraor-dinarily broad range of applications to real-world optimization problems. Startingfrom the seminal 1989 paper by Feo and resende, over the past 25 years, a largebody of work on greedy randomized adaptive search procedures has emerged. a vastarray 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 timelyand welcome addition to the metaheuristics literature, bringing together this bodyof work in a Single volume.The account of GRasP in this book is especially commendable for its readability, covering many facets of this metaheuristic, such as solution construction, localsearch, hybridizations, and extensions. It is organized into four main sections: in-troduction to combinatorial optimization, fundamentals of heuristic search, basicGRASP and advanced topics the book can be used as an introductory text notonly to grasp but also to combinatorial optimization, local search, path-relinkingand metaheuristics in general. For the more advanced reader, chapters on hybridization with path-relinking and parallel and continuous grasP present these topics ina clear and concise fashion The book additionally offers a very complete annotatedbibliography of GrasP and combinatorial optimizationFor the practitioner who needs to solve combinatorial optimization problems, thebook provides implementable templates for all algorithms covered in the textThis book with its excellent overview of the state of the art of grasp. shouldappeal to researchers and practitioners of combinatorial optimization who have aneed to find optimal or near-optimal solutions to hard optimization problemsBoulder. Co. uSaFred GloverMay 2016PrefaceGreedy randomized adaptive search procedures, or grasP, were introduced byT. Feo and M. resende in 1989 as a probabilistic heuristic for solving hard setcovering problems. Soon after its introduction, it was recognized as a general pur-pose metaheuristic and was applied to a number of other combinatorial optimizationproblems, including scheduling problems, the quadratic assignment problem, thesatisfiability problem, and graph planarization. At the Spring 1991 ORSA/TIMSmeeting in Nashville, T Feo and M. resende presented the first tutorial on grasPas a metaheuristic, which was followed by their tutorial published in the Journal ofGlobal optimization in 1995. Since then grasP has gained wide acceptance as aneffective and easy-to-implement metaheuristic for finding optimal or near-optimalsolutions to combinatorial optimization problemsThis book has been many years in planning. Though many books have been written about other metaheuristics, including genetic algorithms, tabu search, simulatedannealing, and ant colony optimization a book on grasp had yet to be publishedSince the subject has had 25 years to mature we feel that this is the right time forsuch a book. After Springer agreed to publish this book, we began the task of writingit in 2010We have been collaborating on the design and implementation of grasP heuristics since 1994 when we decided at the tiMs XXXII International meeting in An-chorage, Alaska, to partner in designing a GrASP for graph planarization. Sincethen, we have worked together on a number of papers on GrAsP, including threehighly cited surveysThis book is aimed at students, engineers, scientists, operations researchers, application developers, and other specialists who are looking for the most appropriateand recent GRASP-based optimization tools to solve particular problems. It focuseson algorithmic and computational aspects of applied optimization with grasP.Emphasis is given to the end user, providing sufficient information on the broadspectrum 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 abook on grasp but also a pedagogical book on heuristics, metaheuristics and itsPresabasics, foundations, extensions, and applications. We motivate the subject with anumber of hard combinatorial optimization problems expressed in simple descriptions in the first chapter. This is followed by an overview of complexity theorythat makes the case for heuristics and metaheuristics as very effective strategies forsolving hard or large instances of the so-called intractable NP-hard optimizationproblems In our view, most metaheuristics share a number of common buildingblocks that are combined following different strategies to overcome premature local optimality. such building blocks are explored for example, in the chapters orsections on greedy algorithms, randomization, local search, cost updates and candi-date lists, solution perturbations and ejection chains, adaptive memory and elite setspath-relinking, runtime distributions and probabilistic analysis tools, parallelizationstrategies, and implementation tricks, among other topics. As such, preliminary versions of this text have been used in the last three years as a textbook for the courseon metaheuristics at the graduate program in computer science at Universidade Federal Fluminense, Brazil, complemented with specific reading material about othermetaheuristics, where it has matured and was exposed to criticisms and suggestionsfrom many students and colleagues.The book begins in Chapter I with an introduction to optimization and a discussion about solution methods for discrete optimization, such as exact and approxi-mate methods. including heuristics and metaheuristicsWe then provide in Chapter 2 a short tour of combinatorial optimization andcomputational complexity, in which we introduce metaheuristics as a very effectivetool for approximately solving hard optimization problemsThis is followed in Chapter 3 with solution construction methods, includingreedy algorithms and their relation to matroids, adaptive greedy and semi-greedyalgorithms, and Solution repair proceduresChapter 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 liststrategies. Ejection chains and perturbations as well as other strategies to escapefrom local optima are discussedChapter 5 introduces the basic GrasP as a semi-greedy multistart procedurewith local search. Techniques for accelerating the basic procedure are pointed outProbabilistic stopping criteria for GrASP are also discussed. The chapter concludeswith a short introduction to the application of GrasP as a heuristic for multiobjective optimizationChapter 6 focuses on time-to-target plots(or runtime distributions) for comparing exponentially distributed runtimes, such as those for GrasP heuristics, andruntimes with general distributions, such as those for GRASP with path-relinkingRuntime distribution will be extensively used throughout this book to assess theperformance of stochastic search algorithmsExtended graSP construction heuristics are covered in Chapter 7. The chapterbegins with reactive GrasP and then covers topics such as probabilistic choice ofthe construction parameter, random plus greedy and sampled greedy constructions,construction by cost perturbation, and the use of bias functions in constructionPrefaceThe 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 forpath-relinking and discusses its mechanics and implementation strategies. Othertopics related to path-relinking are also discussed in this chapter. This includes howto deal with infeasibilities in path-relinking, how to randomize path-relinking, andexternal path-relinking and its relation to diversificationThe hybridization of grasp with path-relinking is covered in Chapter 9. Thechapter begins by providing motivation for hybridizing path-relinking with GrasPto provide grasp with a memory mechanism. It then goes on to discuss elite setsand how they can be used as a way to connect GRASP and path-relinking. The chapter ends with a discussion of evolutionary path-relinking and restart mechanisms forGRASP with path-relinking heuristicsThe implementation of GrasP on parallel machines is the topic of Chap-ter 10. The chapter introduces two types of strategies for parallel implementation ofGRASP: multiple-walk independent-thread and multiple-walk cooperative-threadstrategies. It then goes on to illustrate these implementation strategies with three examples: the three-index assignment problem, the job shop scheduling problem, andthe 2-path network design problemContinuous grasP extends grasp heuristics from discrete optimization tocontinuous global optimization This is the topic of chapter ll. After establishing the similarities and differences between GrASP for discrete optimization andcontinuous GrasP (or simply C-GrasP), the chapter describes the constructionand local search phases of C-GrasP and concludes with several examples applying C-GrasP to multimodal box-constrained optimizationThe book concludes with Chapter 12 where four implementations of GrasP andGRASP with path-relinking are described in detail. These implementations are forthe 2-path network design problem, the graph planarization problem, the unsplittable network flow problem, and the maximum cut problemEach chapter concludes with bibliographical notesWriting this book was certainly a long and arduous task, but most of all it hasbeen an amazing experience. The many trips between Holmdel, Seattle, and rio deJaneiro and the periods the authors spent visiting each other along the last six yearshave been gratifying and contributed much to fortify an already strong friendshipWe had a lot of fun and we are very happy with the outcome of this project. We willbe even happier if the readers appreciate reading and using this book as much as weenjoyed writing itSeattle WA.USaMauricio g.c. resendeRio de janeiro. r]. brazilCelso C. ribeiroay2016AcknowledgmentsOver the years, we have collaborated with many people on research related to topicscovered in this book. We make an attempt to acknowledge all of them below, inalphabetical order, and apologize in case someone was omitted from this long listJames abello, Vaneet Aggarwal, Renata Aiex, Daniel Aloise, Dario Aloise, Adriana Alvim, Diogo Andrade, Alexandre Andreatta, David Applegate, Aleteia araujoAaron Archer, Silvio Binato, Ernesto Birgin, Isabelle Bloch, Maria Claudia BoeresMaria Cristina Boeres, Julliany Brandao, Luciana Buriol, Vicente Campos, SuzanaCanuto, Sergio Carvalho, W.A. Chaovalitwongse, Bruno Chiarini, Clayton Commander, abraham duarte, Alexandre duarte, christophe duhamel, sandra duniEkisoglu, Joao Lauro Faco, Djalma Falcao, Haroldo Faria Jr, Tom Feo, EraldoFernandes, Daniele Ferone, Paola Festa, Rafael Frinhani, Micael Gallego, FredGlover, Fernando Carvalho-Gomes, Jose Fernando goncalves, Jose luis gonzalez-Velarde, Erico Gozzi, Allison Guedes, William Hery, Michael Hirsch, Ruben Interian, David Johnson, Howard Karloff, Yong Li, X Liu, David Loewenstern, IreneLoiseau. abilio Lucena. Rafael marti. Cristian martinez. simone martins geraldo mateus. Thelma mavridou. Marcelo Medeiros. Rafael Melo, Claudio meneses. Renato moraes. Luis moran -mirabal. Leonardo musmanno fernanda nakamura. Maria nascimento Thiago noronha. Carlos oliveira. Panos Pardalos Lu-ciana pessoa. alexandre plastino, Leonidas pitsoulis marcelo prais Fabio prottiTianbing Qian, Michelle Ragle, Sanguthevar Rajasekaran, Martin Ravetti, VinodRebello, Lucia Resende, Alberto reyes, Caroline rocha, Noemi rodriguez, IsabelRosseti, Jesus sanchez-Oro. Andrea dos santos Ricardo silva. Stuart Smith. Cidde souza. mauricio de souza. reinaldo souza. Fernando stefanello. Sandra Sudarksy, Franklina Toledo, Giorgio de Tomi, Gerardo Toraldo, Marco Tsitselis, Eduardo Uchoa, Osman Lular, Sebastian Urrutia, Reinaldo vallejos, Alvaro Veiga,Ana Viana, Dalessandro Vianna, Carlos Eduardo vieira, Eugene vinod, and renatoWerneckThe authors are particularly indebted to Simone Martins for her careful revisionof this manuscript. We are also very thankful to Fred Glover for kindly agreeing towrite the foreword of this book
下载地址
用户评论
