Scatter Search: Methodology and Implementations in CSpringer 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 |
277 | |
285 | |
Diğer baskılar - Tümünü görüntüle
Scatter Search: Methodology and Implementations in C Manuel Laguna,Rafael Martí Sınırlı önizleme - 2012 |
Sık kullanılan terimler ve kelime öbekleri
applied array assigned b₁ b₂ best solution found branch and bound Combination Method combination strategies combining solutions Computer Code consists constraints constructed context create current solution defined diverse solutions Diversification Generation Method double elements elite solutions evaluations feasible Figure frequency genetic algorithms Glover graph guiding solutions heuristic high quality solutions improved solutions Improvement Method infeasible initiating solution instances int sol integer iteration knapsack problems Laguna and Martí linear ordering problem local optimum local search matrix maximum mechanism memory metaheuristic min_dist minimize multiobjective optimization neighborhood newsol nonlinear optimization nprob nvar objective function value objval optimal solutions optimization problems path relinking pb->nvar performed permutation PSize random Reference Set Update reference solutions scatter search implementation sector selected set of solutions Set Update Method simulation solutions in RefSet SS pb SSAbort SSImprove_solution SSInt_array step structure Subset Generation Method tabu search trial solutions tutorial chapters variable void votes weight