Scatter Search: Methodology and Implementations in C

Ön Kapak
Springer Science & Business Media, 28 Şub 2003 - 291 sayfa
The book Scatter Search by Manuel Laguna and Rafael Martí represents a long-awaited "missing link" in the literature of evolutionary methods. Scatter Search (SS)-together with its generalized form called Path Relinking-constitutes the only evolutionary approach that embraces a collection of principles from Tabu Search (TS), an approach popularly regarded to be divorced from evolutionary procedures. The TS perspective, which is responsible for introducing adaptive memory strategies into the metaheuristic literature (at purposeful level beyond simple inheritance mechanisms), may at first seem to be at odds with population-based approaches. Yet this perspective equips SS with a remarkably effective foundation for solving a wide range of practical problems. The successes documented by Scatter Search come not so much from the adoption of adaptive memory in the range of ways proposed in Tabu Search (except where, as often happens, SS is advantageously coupled with TS), but from the use of strategic ideas initially proposed for exploiting adaptive memory, which blend harmoniously with the structure of Scatter Search. From a historical perspective, the dedicated use of heuristic strategies both to guide the process of combining solutions and to enhance the quality of offspring has been heralded as a key innovation in evolutionary methods, giving rise to what are sometimes called "hybrid" (or "memetic") evolutionary procedures. The underlying processes have been introduced into the mainstream of evolutionary methods (such as genetic algorithms, for example) by a series of gradual steps beginning in the late 1980s.
 

İçindekiler

INTRODUCTION
1
Historical Background
4
12 Scatter Tabu Search Hybrid 1990
6
13 Scatter Search Template 1998
8
Basic Design
11
21 Summary of Notation
14
C Code Conventions
16
TUTORIAL Unconstrained Nonlinear Optimization
23
2 Explicit Memory
128
31 Diversification
131
311 Computer Code
133
32 Intensification
135
321 Computer Code
136
33 Reference Set
138
CONNECTIONS WITH OTHER POPULATION BASED APPROACHES
141
Genetical Algorithm
142

Diversification Generation Method
24
11 Computer Code
26
Improvement Method
28
21 Computer Code
29
Reference Set Update Method
31
31 Computer Code
33
Subset Generation Method
37
41 Computer Code
38
Combination Method
39
51 Computer Code
40
Overall Procedure
41
61 Computer Code
44
Summary of C Functions
46
TUTORIAL 01 Knapsack Problems
49
Diversification Generation Method
50
11 Computer Code
52
Improvement Method
55
21 Computer Code
57
References Set Update Method
59
31 Computer Code
61
Subset Generation Method
62
Combination Method
63
51 Computer Code
64
Overall Procedure
65
61 Computer Code
66
Summary of C Functions
67
TUTORIAL Linear Ordering Problem
69
Diversification Generation Method
71
21 Computer Code
74
Improvement Method
76
31 Computer Code
79
Reference Set Update Method
82
Combination Method
83
51 Computer Code
85
Summary of C Functions
86
Advanced Scatter Search Designs
89
Reference Set
90
11 Dynamic Updating
91
12 Rebuilding and MultiTier Update
93
121 Rebuilding
94
122 2Tier Update
95
123 3Tier Update
99
13 Solution Duplication and Diversity Control
102
131 Minimum Diversity Test
103
132 Hashing
105
Subset Generation
107
Specialized Combination Methods
112
31 Variable Number of Solutions
114
32 Binary Variables
116
Diversification Generation
118
42 GRASP Constructions
120
USE OF MEMORY IN SCATTER SEARCH
123
1 Tabu Search
124
11 SS and GA Comparison
146
111 Improvement Method
149
112 Combination Method
150
113 Computational Testing
154
Part Oath Relinking
160
21 Simultaneous Relinking
166
22 Dealing with Infeasibility
167
23 Extrapolated Relinking
168
24 Multiple Guiding Solutions
170
25 Constructive Neighborhoods
172
26 Vocabulary Building
173
27 Computer code
177
INTENSIFICATION AND DIVERSIFICATION
180
SCATTER SEARCH APPLICATIONS
185
11 Computer code
187
MultiObjective Bus Routing
189
Arc Crossing Minimization in Graphs
191
Maximum Clique
193
Graph Coloring
195
Periodic Vehicle Loading
197
Capacitated Multicomodity Network Design
198
JobShop Scheduling
201
Capacitated Chinese Postman Problem
202
91 Testing population designs
204
Vehicle Routing
206
Binary Mixed Integer Programming
208
112 Generating Diverse Solutions
210
Iterated Restart Procedures
212
Paralleliation for the PMedian
215
OptQuest Application
217
Commercial Scatter Search Implementation
219
General OCL Design
223
Constraints and Requirements
225
OCL Functionality
227
31 Defining Constraints and Requirements
232
32 Boundary Search Strategy
235
Computational Experiments
239
Conclusions
245
Appendix
246
Experiences and Future Directions
255
Experiences and Findings
256
12 Improvement Method
258
13 Reference Set Update Method
260
14 Subset Generation Method
263
15 Combination Method
264
MultiObjective Scatter Search
266
21 Independent Sampling Technique
269
23 Aggregation Selection Technique
270
Maximum Diversity Problem
271
Implications for Future Developments
274
REFERENCES
277
INDEX
285
Telif Hakkı

Diğer baskılar - Tümünü görüntüle

Sık kullanılan terimler ve kelime öbekleri

Kaynakça bilgileri