Stochastic Local Search（局部搜索算法入门的经典书籍）.pdf

发布时间：2022-06-19 发布人：admin 分类：说明书资料大小：8.97M 资料格式：pdf 举报版权申诉

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第1页.png

第1页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第2页.png

第2页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第3页.png

第3页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第4页.png

第4页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第5页.png

第5页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第6页.png

第6页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第7页.png

第7页 / 共677页

caab4643-9a52-4f6e-b19a-67bc6ad96780.pdf-第8页.png

第8页 / 共677页

1558608729

Contents

Prologue

Part I: Foundations

Chapter 1. Introduction

1.1 Combinatorial Problems

1.2 Two Prototypical Combinatorial Problems

1.3 Computational Complexity

1.4 Search Paradigms

1.5 Stochastic Local Search

1.6 Further Readings and Related Work

1.7 Summary

Exercises

Chapter 2. SLS Methods

2.1 Iterative Improvement (Revisited)

2.2 'Simple' SLS Methods

2.3 Hybrid SLS Methods

2.4 Population-Based SLS Methods

2.5 Further Readings and Related Work

2.6 Summary

Exercises

Chapter 3. Generalised Local Search Machines

3.1 The Basic GLSM Model

3.2 State, Transition and Machine Types

3.3 Modelling SLS Methods Using GLSMs

3.4 Extensions of the Basic GLSM Model

3.5 Further Readings and Related Work

3.6 Summary

Exercises

Chapter 4. Empirical Analysis of SLS Algorithms

4.1 Las Vegas Algorithms

4.2 Run-Time Distributions

4.3 RTD-Based Analysis of LVA Behaviour

4.4 Characterising and Improving LVA Behaviour

4.5 Further Readings and Related Work

4.6 Summary

Exercises

Chapter 5. Search Space Structure and SLS Performance

5.1 Fundamental Search Space Properties

5.2 Search Landscapes and Local Minima

5.3 Fitness-Distance Correlation

5.4 Ruggedness

5.5 Plateaus

5.6 Barriers and Basins

5.7 Further Readings and Related Work

5.8 Summary

Part II: Applications

Chapter 6. Propositional Satisfiability and Constraint Satisfaction

6.1 The Satisfiability Problem

6.2 The GSAT Architecture

6.3 The WalkSAT Architecture

6.4 Dynamic Local Search Algorithms for SAT

6.5 Constraint Satisfaction Problems

6.6 SLS Algorithms for CSPs

6.7 Further Readings and Related Work

6.8 Summary

Exercises

Chapter 7. MAX-SAT and MAX-CSP

7.1 The MAX-SAT Problem

7.2 SLS Algorithms for MAX-SAT

7.3 SLS Algorithms for MAX-CSP

7.4 Further Readings and Related Work

7.5 Summary

Exercises

Chapter 8. Travelling Salesman Problems

8.1 TSP Applications and Benchmark Instances

8.2 'Simple' SLS Algorithms for the TSP

8.3 Iterated Local Search Algorithms for the TSP

8.4 Population-Based SLS Algorithms for the TSP

8.5 Further Readings and Related Work

8.6 Summary

Exercises

Chapter 9. Scheduling Problems

9.1 Models and General Considerations

9.2 Single-Machine Scheduling

9.3 Flow Shop Scheduling

9.4 Group Shop Problems

9.5 Further Readings and Related Work

9.6 Summary

Exercises

Chapter 10. Other Combinatorial Problems

10.1 Graph Colouring

10.2 The Quadratic Assignment Problem

10.3 Set Covering

10.4 Combinatorial Auctions

10.5 DNA Code Design

10.6 Further Readings and Related Work

10.7 Summary

Exercises

Epilogue

Glossary

Bibliography

Index

Praise for Stochastic Local Search: Foundations and Applications ‘Hoos and Stützle, two major players in the ﬁeld, provide us with an excellent overview of stochastic local search. If you are looking for a book that covers all the major meta- heuristics, gives you insight into their working and guides you in their application to a wide set of combinatorial optimization problems, this is the book.’ Marco Dorigo, Université Libre de Bruxelles ‘Stochastic Local Search: Foundations and Applications provides an original and synthetic presentation of a large class of algorithms more commonly known as meta- heuristics. Over the last 20 years, these methods have become extremely popular, often representing the only practical approach for tackling so many of the hard combinatorial problems that are encountered in real-life applications. Hoos and Stützle’s treatment of the topic is comprehensive and covers a variety of techniques, including simulated an- nealing, tabu search, genetic algorithms and ant colony optimization, but a main feature of the book is its proposal of a most welcome unifying framework for describing and analyzing the various methods.’ Michel Gendreau, Université de Montréal ‘Local search algorithms are often the most practical approach to solving constraint satisfaction and optimization problems that admit no fast deterministic solution. This book is full of information and insights that would be invaluable for both researchers and practitioners.’ Henry Kautz, University of Washington ‘This extensive book provides an authoritative and detailed exposition for novices and experts alike who need to tackle difﬁcult decision or combinatorial optimization prob- lems. The chapters span fundamental theoretical questions such as, “When and why do heuristics work well?” but also more applied aspects involving, for instance, the com- parison of very different algorithms. The authors are university faculty members and leading players in their research ﬁelds; our communities will enjoy in particular their book’s valuable teaching material and a “complete” bibliography of the state of the art for the ﬁeld.’ Olivier Martin, Université Paris-Sud, Orsay ‘The authors provide a lucid and comprehensive introduction to the large body of work on stochastic local search methods for solving combinatorial problems. The text also covers a series of carefully executed empirical studies that provide signiﬁcant further insights into the performance of such methods and show the value of an empirical sci- entiﬁc methodology in the study of algorithms. An excellent overview of the wide range of applications of stochastic local search methods is included.’ Bart Selman, Cornell University

‘Stochastic local search is a powerful search technique for solving a wide range of combi- natorial problems. If you only want to read one book on this important topic, you should read Hoos and Stützle’s. It is a comprehensive and informative survey of the ﬁeld that will equip you with the tools and understanding to use stochastic local search to solve the problems you come across.’ Toby Walsh, Cork Constraint Computation Centre University College Cork ‘This book provides remarkable coverage and synthesis of the recent explosion of work on randomized local search algorithms. It will serve as a good textbook for classes on heuristic search and metaheuristics as well as a central reference for researchers. The book provides a uniﬁcation of a broad spectrum of methods that enables concise, highly readable descriptions of theoretical and experimental results.’ David L. Woodruff, University of California, Davis

Stochastic Local Search Foundations and Applications

This Page Intentionally Left Blank

Stochastic Local Search Foundations and Applications Holger H. Hoos Department of Computer Science University of British Columbia Canada Thomas Stützle Department of Computer Science Darmstadt University of Technology Germany AMSTERDAM • BOSTON • HEIDELBERG • LONDON NEW YORK • OXFORD • PARIS • SAN DIEGO SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO MORGAN KAUFMANN PUBLISHERS IS AN IMPRINT OF ELSEVIER

Senior Editor Publishing Services Manager Editorial Coordinator Editorial Assistant Cover Design Cover Image Text Design Composition Technical Illustration Copyeditor Proofreader Indexer Interior printer Cover printer Denise Penrose Simon E. M. Crump Emilia Thiuri Valerie Witte Gary Ragaglia and Holger H. Hoos “Antelope Canyon” c Thomas Morse/Chuck Place Photo Rebecca Evans and Associates Kolam USA Dartmouth Publishing, Inc. Lori Newhouse Calum Ross Robert Swanson The Maple-Vail Book Manufacturing Group Phoenix Color Morgan Kaufmann Publishers is an imprint of Elsevier. 500 Sansome Street, Suite 400, San Francisco, CA 94111 This book is printed on acid-free paper. © 2005 by Elsevier Inc. All rights reserved. Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopying, scanning, or otherwise—without prior written permission of the publisher. Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: permissions@elsevier.com.uk. You may also complete your request on-line via the Elsevier homepage (http://elsevier.com) by selecting “Customer Support” and then “Obtaining Permissions.” Library of Congress Cataloging-in-Publication Data Application submitted ISBN: 1-55860-872-9 For information on all Morgan Kaufmann publications, visit our Web site at www.mkp.com. Printed in the United States of America 04 05 06 07 08 5 4 3 2 1

[Science] ... is not a steady march from ignorance to knowledge. It’s more like mountaineering expedition. On the way up an unscaled peak, climbers will gain some altitude on one route, then ﬁnd it’s a dead end. They’ll spot a better one, backtrack a little and move on. The fact that they sometimes have to take a step backward for every two steps forward doesn’t mean they are wasting their time. It means that inching up an uncharted mountain is tough work. When you step back, though, and take a look at the overall picture — a long view from the upper slopes of the mountain — it turns out in hindsight that the path was clear. (Michael D. Lemonick, Science Writer)

分享到：

赞收藏

资料库

Stochastic Local Search（局部搜索算法入门的经典书籍）.pdf

相关推荐

人工智能

热门标签

最新资料