Modern Heuristic Search Methods

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

• ISBN13: 9780471962809
• ISBN10: 0471962805
• Edition: 1st
• Format: Hardcover
• Copyright: 1996-12-23
• Publisher: Wiley

Summary

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.

Author Biography

V. J. Rayward-Smith is the editor of Modern Heuristic Search Methods, published by Wiley.

I. H. Osman is the editor of Modern Heuristic Search Methods, published by Wiley.

C. R. Reeves is the editor of Modern Heuristic Search Methods, published by Wiley.

G. D. Smith is the editor of Modern Heuristic Search Methods, published by Wiley.

Table of Contents

List of Contributors	v	(4)
Preface	ix
INTRODUCTION	1	(26)
1 Modern Heuristic Techniques	1	(26)
Abstract	1	(1)
1.1 Introduction	1	(1)
1.2 Combinatorial Optimization	2	(1)
1.3 The Case for Heuristics	3	(2)
1.4 Neighbourhood Search	5	(1)
1.5 Simulated Annealing	6	(5)
1.5.1 A Simple Example	7	(1)
1.5.2 Generic Decisions	8	(2)
1.5.3 Problem Specific Decisions	10	(1)
1.5.4 Other Factors	10	(1)
1.5.5 Summary	11	(1)
1.6 Tabu Search	11	(6)
1.6.1 Basic Concepts	11	(1)
1.6.2 Recency	12	(3)
1.6.3 Frequency	15	(2)
1.6.4 Summary	17	(1)
1.7 Genetic Algorithms	17	(6)
1.7.1 Crossover	18	(1)
1.7.2 Mutation	18	(1)
1.7.3 Reproduction	18	(1)
1.7.4 A Simple Example	19	(2)
1.7.5 Modifications and Enhancements	21	(2)
1.7.6. Summary	23	(1)
1.8 Conclusion	23	(1)
REFERENCES	24	(3)
TECHNIQUES	27	(90)
2 Localized Simulated Annealing in Constraint Satisfaction and Optimization	27	(14)
Abstract	27	(1)
2.2 Introduction	27	(2)
2.2 Subspaces and Their Evaluation	29	(1)
2.3 Localized Simulated Annealing (LSA)	30	(2)
2.4 Analysis and Justification	32	(3)
2.5 Empirical Results	35	(4)
2.5.1 The Flight Scheduling Problem	36	(2)
2.5.2 The Freight Train Regrouping Problem	38	(1)
2.6 Conclusion	39	(1)
REFERENCES	39	(2)
3 Observing Logical Interdependencies in Tabu Search:- Methods and Results	41	(20)
Abstract	41	(1)
3.1 Introduction	41	(1)
3.2 Tabu Search	42	(8)
3.2.1 Historical Development	42	(1)
3.2.2 Guiding Process Versus Application Process	43	(2)
3.2.3 Tabu Navigation Method - Static Tabu Search	45	(1)
3.2.4 Reverse Elimination Method and Cancellation Sequence Method	45	(3)
3.2.5 Logical Interdependencies	48	(1)
3.2.6 Moving Gap	48	(2)
3.3 Applications in Location Planning	50	(6)
3.3.1 Network Design and Steiner Trees	50	(4)
3.3.2 Warehouse Location Problems	54	(1)
3.3.3 Further Location Problems	55	(1)
3.4 Conclusions	56	(1)
REFERENCES	57	(4)
4 Reactive Search: Toward Self-tunning Heuristics	61	(24)
Abstract	61	(1)
4.1 Reactive Search: Feedback Applied to Heuristics	61	(2)
4.2 Tabu Search: Beyond Local Search	63	(1)
4.3 Some Forms of Tabu Search	64	(4)
4.3.1 Dynamical Systems	65	(1)
4.3.2 Implementations	66	(2)
4.4 Reactive Tabu Search (RTS)	68	(3)
4.4.1 Self-adjusted Prohibition Period	68	(1)
4.4.2 The Escape Mechanism	69	(1)
4.4.3 Fast Algorithms for Using the Search History	70	(1)
4.5 Different Ways of Escaping from a Local Attractor	71	(7)
4.5.1 Strict-TS	72	(2)
4.5.2 Fixed-TS	74	(1)
4.5.3 Reactive-TS	75	(3)
4.6 Applications of Reactive Search: a Review	78	(2)
4.6.1 Combinatorial Tasks	78	(1)
4.6.2 Continuous Optimization	79	(1)
4.6.3 Sub-symbolic Machine Learning (Neural Networks)	79	(1)
4.6.4 VLSI Systems with Learning Capabilities	79	(1)
4.7 Software	80	(1)
4.8 Acknowledgements	81	(1)
REFERENCES	81	(1)
5 Combinatorial Optimization by Genetic Algorithms: The Value of the Genotype/Phenotype Distinction	85	(14)
Abstract	85	(1)
5.1 Background	85	(1)
5.2 The Line Balancing Problem	86	(2)
5.3 An Inadequate Approach	88	(1)
5.4 A GA Approach	89	(5)
5.5 How Well Does it Work?	94	(2)
5.6 Conclusions	96	(1)
REFERENCES	96	(3)
6 Integrating Local Search into Genetic Algorithms	99	(18)
Abstract	99	(1)
6.1 Introduction	99	(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