Modern Heuristic Search Methods

, by Rayward-Smith, V. J.; Osman, I. H.; Reeves, C. R.; Smith, G. D.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780471962809 | 0471962805
Cover: Hardcover
Copyright: 12/23/1996

Buy New

Print on Demand: 2-4 Weeks. This item cannot be cancelled or returned.

$270.96

Including contributions from leading experts in the field, this book covers applications and developments of heuristic search methods for solving complex optimization problems. The book covers various local search strategies including genetic algorithms, simulated annealing, tabu search and hybrids thereof. These methods have proved extraordinarily successful by solving some of the most difficult, real-world problems. At the interface between Artificial Intelligence and Operational Research, research in this exciting area is progressing apace spurred on by the needs of industry and commerce. The introductory chapter provides a clear overview of the basic techniques and useful pointers to further reading and to current research. The second section of the book covers some of the most recent and exciting developments of the basic techniques, with suggestions not only for extending and improving these but also for hybridizing and incorporating automatic adaption. The third section contains a number of case studies, surveys and comparative studies which span a wide range of application areas ranging from the classic Steiner tree problem to more practical problems arising in telecommunications and data analysis. The coverage of the latest research and the illustrative case studies will ensure that the book is invaluable for researchers and professionals with an interest in heuristic search methods.

List of Contributors

(4)

Preface

INTRODUCTION

(26)

1 Modern Heuristic Techniques

(26)

Abstract

(1)

1.1 Introduction

(1)

1.2 Combinatorial Optimization

(1)

1.3 The Case for Heuristics

(2)

1.4 Neighbourhood Search

(1)

1.5 Simulated Annealing

(5)

1.5.1 A Simple Example

(1)

1.5.2 Generic Decisions

(2)

1.5.3 Problem Specific Decisions

(1)

1.5.4 Other Factors

(1)

1.5.5 Summary

(1)

1.6 Tabu Search

(6)

1.6.1 Basic Concepts

(1)

1.6.2 Recency

(3)

1.6.3 Frequency

(2)

1.6.4 Summary

(1)

1.7 Genetic Algorithms

(6)

1.7.1 Crossover

(1)

1.7.2 Mutation

(1)

1.7.3 Reproduction

(1)

1.7.4 A Simple Example

(2)

1.7.5 Modifications and Enhancements

(2)

1.7.6. Summary

(1)

1.8 Conclusion

(1)

REFERENCES

(3)

TECHNIQUES

(90)

2 Localized Simulated Annealing in Constraint Satisfaction and Optimization

(14)

Abstract

(1)

2.2 Introduction

(2)

2.2 Subspaces and Their Evaluation

(1)

2.3 Localized Simulated Annealing (LSA)

(2)

2.4 Analysis and Justification

(3)

2.5 Empirical Results

(4)

2.5.1 The Flight Scheduling Problem

(2)

2.5.2 The Freight Train Regrouping Problem

(1)

2.6 Conclusion

(1)

REFERENCES

(2)

3 Observing Logical Interdependencies in Tabu Search:- Methods and Results

(20)

Abstract

(1)

3.1 Introduction

(1)

3.2 Tabu Search

(8)

3.2.1 Historical Development

(1)

3.2.2 Guiding Process Versus Application Process

(2)

3.2.3 Tabu Navigation Method - Static Tabu Search

(1)

3.2.4 Reverse Elimination Method and Cancellation Sequence Method

(3)

3.2.5 Logical Interdependencies

(1)

3.2.6 Moving Gap

(2)

3.3 Applications in Location Planning

(6)

3.3.1 Network Design and Steiner Trees

(4)

3.3.2 Warehouse Location Problems

(1)

3.3.3 Further Location Problems

(1)

3.4 Conclusions

(1)

REFERENCES

(4)

4 Reactive Search: Toward Self-tunning Heuristics

(24)

Abstract

(1)

4.1 Reactive Search: Feedback Applied to Heuristics

(2)

4.2 Tabu Search: Beyond Local Search

(1)

4.3 Some Forms of Tabu Search

(4)

4.3.1 Dynamical Systems

(1)

4.3.2 Implementations

(2)

4.4 Reactive Tabu Search (RTS)

(3)

4.4.1 Self-adjusted Prohibition Period

(1)

4.4.2 The Escape Mechanism

(1)

4.4.3 Fast Algorithms for Using the Search History

(1)

4.5 Different Ways of Escaping from a Local Attractor

(7)

4.5.1 Strict-TS

(2)

4.5.2 Fixed-TS

(1)

4.5.3 Reactive-TS

(3)

4.6 Applications of Reactive Search: a Review

(2)

4.6.1 Combinatorial Tasks

(1)

4.6.2 Continuous Optimization

(1)

4.6.3 Sub-symbolic Machine Learning (Neural Networks)

(1)

4.6.4 VLSI Systems with Learning Capabilities

(1)

4.7 Software

(1)

4.8 Acknowledgements

(1)

REFERENCES

(1)

5 Combinatorial Optimization by Genetic Algorithms: The Value of the Genotype/Phenotype Distinction

(14)

Abstract

(1)

5.1 Background

(1)

5.2 The Line Balancing Problem

(2)

5.3 An Inadequate Approach

(1)

5.4 A GA Approach

(5)

5.5 How Well Does it Work?

(2)

5.6 Conclusions

(1)

REFERENCES

(3)

6 Integrating Local Search into Genetic Algorithms

(18)

Abstract

(1)

6.1 Introduction

(1)

6.2 GAs and NS

100

(1)

6.3 No-wait Flowshop Problem

101

(1)

6.4 Graph Partitioning

102

(3)

6.4.1 The LPK Heuristic

103

(1)

6.4.2 Complementary Crossover

103

(1)

6.4.3 1-bit Hamming Hill Climber (HC)

104

(1)

6.4.4 Mutation (MUT)

104

(1)

6.5 Evaluation of the Operators

105

(2)

6.6 Recombination

107

(6)

6.7 Conclusion

113

(1)

REFERENCES

113

(4)

CASE STUDIES

117

(174)

7 Local Search for Steiner Trees in Graphs

117

(14)

Abstract

117

(1)

7.1 Introduction

117

(1)

7.2 Local Search

118

(1)

7.2.1 The Steiner Tree Problem in Graphs (SP)

118

(1)

7.3 Neighborhoods for the SP

119

(7)

7.4 Computational Results

126

(3)

REFERENCES

129

(2)

8 Local Search Strategies for the Vehicle Fleet Mix Problem

131

(24)

Abstract

131

(1)

8.1 Introduction

131

(1)

8.2 The Vehicle Fleet Mix (VFM) Problem

133

(2)

8.2.1 Representation of the VFM

133

(1)

8.2.2 Literature Review of the VFM

134

(1)

8.3 Modified RPERT Procedure (MRPERT)

135

(2)

8.4 Tabu Search

137

(7)

8.5 Computational Experience

144

(7)

8.6 Conclusion and Future Directions

151

(1)

8.7 Acknowledgement

151

(1)

REFERENCES

152

(3)

9 SA Solutions for Timetabling

155

(12)

Abstract

155

(1)

9.1 Introduction

155

(1)

9.2 Local Search, Simulated Annealing and Scheduling Problems

156

(2)

9.3 Examination Scheduling

158

(4)

9.4 Laboratory Scheduling

162

(3)

Conclusions

165

(1)

REFERENCES

166

(1)

10 A Tabu Search Algorithm for Some Discrete-Continuous Scheduling Problems

167

(14)

Abstract

167

(1)

10.1 Introduction

167

(1)

10.2 Problem Formulation

168

(4)

10.3 An Application of the Tabu Search Algorithm

172

(4)

10.3.1 Representation of a Feasible Solution

172

(1)

10.3.2 Creating a Starting Solution

172

(1)

10.3.3 Objective Function

173

(1)

10.3.4 Mechanism of Generating a Neighbourhood

173

(1)

10.3.5 Structure of the Tabu List

174

(2)

10.4 Computational Experiments

176

(3)

10.5 Final Remarks

179

(1)

10.6 Acknowledgements

179

(1)

REFERENCES

179

(2)

11 The Analysis of Waste Flow Data from Multi-Unit Industrial Complexes Using Genetic Algorithms

181

(16)

Abstract

181

(1)

11.1 Introduction

181

(1)

11.2 Applicability of the Genetic Algorithm

182

(1)

11.3 The Flow of Industrial Waste Within Large Complexes

183

(4)

11.4 The Algorithm

187

(5)

11.4.1 String Encoding

187

(2)

11.4.2 The Fitness Function

189

(1)

11.4.3 Crossover Operator

190

(1)

11.4.4 Mutation Operator

191

(1)

11.5 Results

192

(2)

11.5.1 Input Data Generation

192

(1)

11.5.2 Results for a Four Factory System

192

(2)

11.6 Applications of the Algorithm

194

(1)

11.7 Acknowledgements

195

(1)

REFERENCES

195

(2)

12 The Evolution of Solid Object Designs Using Genetic Algorithms

197

(16)

Abstract

197

(1)

12.1 Introduction

197

(1)

12.2 Representation

198

(1)

12.3 Correcting Illegal Designs

198

(1)

12.3.1 Method 1

198

(2)

12.3.2 Method 2

200

(1)

12.3.3 Method 3

201

(1)

12.3.4 Where to Correct the Designs

202

(1)

12.4 The Evolution of a Table

203

(7)

12.4.1 Size

203

(1)

12.4.2 Mass

204

(1)

12.4.3 Stability

205

(2)

12.4.4 Flat Surface

207

(1)

12.4.5 Supportiveness and Stability

208

(2)

12.4.6 What the Tables are Not

210

(1)

12.5 Conclusions

210

(1)

REFERENCES

211

(2)

13 The Convoy Movement Problem With Initial Delays

213

(22)

Abstract

213

(1)

13.1 Introduction

213

(3)

13.2 A Branch-and-Bound Approach

216

(5)

13.3 A Hybrid Approach : Using GAs for Delays and B&B for Paths

221

(6)

13.4 A Pure GA Approach

227

(3)

13.5 Conclusions

230

(2)

REFERENCES

232

(3)

14 A Comparison of Heuristics for Telecommunications Traffic Routing

235

(20)

Abstract

235

(1)

14.1 Introduction

235

(1)

14.2 Background

236

(5)

14.2.1 The Genetic Algorithm

236

(2)

14.2.2 Simulated Annealing

238

(3)

14.3 Problem Specification

241

(3)

14.4 Results

244

(7)

14.5 Current and Future Work

251

(1)

14.6 Conclusions

252

(1)

14.7 Acknowledgements

253

(1)

REFERENCES

253

(2)

15 A Brief Comparison of Some Evolutionary Optimization Methods

255

(18)

Abstract

255

(1)

15.1 Introduction

255

(1)

15.2 The Optimization Problems

256

(1)

15.3 The Optimizers

257

(3)

15.4 Initial Results

260

(1)

15.5 Optimizer Tuning

261

(2)

15.6 Conclusion

263

(8)

REFERENCES

271

(2)

16 When `Herby' met `EIViS' -- Experiments with Genetics Based Learning Systems

273

(18)

Abstract

273

(1)

16.1 Introduction

274

(1)

16.2 Genetics Based Learning

274

(1)

16.3 Herby

275

(8)

16.3.1 System Components

278

(1)

16.3.2 The Environment

279

(1)

16.3.3 The Agent

279

(3)

16.3.4 The Ecology

282

(1)

16.3.5 Interim and Prospectus

282

(1)

16.3.6 Corollary

282

(1)

16.4 Exploring Ecological Vision with EIViS

283

(5)

REFERENCES

288

(3)

Index

291

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Modern Heuristic Search Methods

Summary

Author Biography

Table of Contents

Supplemental Materials