This book constitutes the refereed proceedings of the 6th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2006, held in Budapest, Hungary in April 2006.The 24 revised full papers presented were carefully reviewed and selected from 77 submissions. The papers cover evolutionary algorithms as well as various other metaheuristics, like scatter search, tabu search, memetic algorithms, variable neighborhood search, greedy randomized adaptive search procedures, ant colony optimization, and particle swarm optimization algorithms. The papers deal with representations, heuristics, analysis of problem structures, and comparisons of algorithms. The list of studied combinatorial optimization problems includes prominent examples like graph coloring, knapsack problems, the traveling salesperson problem, scheduling, graph matching, as well as specific real-world problems.
Author(s): Jens Gottlieb, Günther R. Raidl
Series: Lecture ... Computer Science and General Issues
Edition: 1
Publisher: Springer
Year: 2006
Language: English
Pages: 303
Tags: Математика;Дискретная математика;Комбинаторика;
000......Page 1
The Minimum Graph Bisection Problem......Page 11
Integer Programming Models......Page 12
Hybrid Genetic Algorithm......Page 15
Mutations......Page 16
Computational Results......Page 18
Conclusion......Page 21
Introduction......Page 23
The Workforce Scheduling Problem......Page 24
Objectives......Page 25
Similar Problems......Page 26
Multi-objective Scheduling Techniques......Page 27
Serial Schedule Generation Scheme (SGS)......Page 29
The Competitiveness of Multi-objective Genetic Algorithms......Page 30
Experimental Results......Page 31
References......Page 33
Introduction......Page 35
Representation......Page 37
Fitness Assignment......Page 38
The Algorithms......Page 39
Test Functions......Page 40
Conclusion and Further Work......Page 45
Introduction......Page 47
Previous Works on Related Problems......Page 48
Mathematical Model Formulation......Page 50
Tabu Search Algorithms......Page 51
Algorithm Implementation......Page 52
Tabu Moves and Aspiration Criterion......Page 53
Computational Experiments and Results......Page 54
References......Page 58
Introduction......Page 59
Design of a Stocking Up Policy......Page 60
Previous Approaches......Page 61
Experiments......Page 62
Small Truck......Page 63
Medium Truck......Page 64
Comparison and Analysis......Page 65
Conclusions and Future Work......Page 69
Introduction......Page 71
Greedy......Page 72
Parametrized Greedy......Page 75
GRASP......Page 78
Test Instances......Page 79
GRASP, PGRASP, and the Global Optimum......Page 80
Conclusions......Page 81
Introduction......Page 83
The Bucket Elimination Approach......Page 84
Bucket Elimination for the Still Life Problem......Page 86
A Memetic Algorithm for the MDSLP......Page 87
A Local Improvement Strategy Based on Tabu Search......Page 88
Optimal Recombination with BE......Page 89
Experimental Results......Page 90
Conclusions and Future Work......Page 93
Introduction......Page 96
Test Problems......Page 97
Small-World Graph Topologies......Page 99
The Barabási-Albert Model......Page 100
Experiment......Page 101
Conclusions......Page 106
Introduction......Page 109
Particle Swarm Optimization......Page 110
PSO for the Traveling Salesman Problem......Page 112
Computational Experiments......Page 115
References......Page 119
Introduction......Page 121
Hierarchy......Page 122
First Theoretical Results: Takeover Times......Page 124
Fitting of the Takeover Curves......Page 126
Test Problems......Page 127
Results......Page 128
Conclusions and Future Work......Page 131
Introduction......Page 133
Integer Merge Model......Page 134
Extracting Useful Information: Co-structures......Page 136
The DSATUR Heuristic......Page 138
Evolutionary Algorithm to Guide the Models......Page 139
Results......Page 141
Conclusions......Page 143
References......Page 144
Introduction......Page 145
Literature Review......Page 146
Heuristics......Page 147
Proposed GAs and Their Implementation......Page 148
Initial Population......Page 149
Mutation......Page 150
Parameters Setting......Page 151
Experimentations and Results......Page 152
References......Page 156
Introduction......Page 157
Representing Populations as Relations......Page 159
Testing Properties of Solutions for Some Graph Problems......Page 160
Crossover......Page 162
Selection......Page 163
Computing Exact Solutions......Page 164
The Quality of a Standard Evolutionary Approach......Page 165
Conclusions......Page 167
Introduction......Page 169
Scatter Search for NSP......Page 170
Computational Results......Page 176
Day Neighbourhood or Nurse Neighbourhood......Page 177
New Best Known Solutions......Page 178
Conclusions and Future Research......Page 179
References......Page 180
Introduction......Page 181
Outline of EAX......Page 182
Fast Algorithm for EAX-1AB......Page 184
Effect of the Fast Algorithm for EAX-1AB......Page 185
Selection Model for Survival......Page 186
Calculation of $\Delta$H(y)......Page 188
Comparisons with Selection Methods......Page 189
Comparisons with Other Optimization Methods......Page 190
Conclusion......Page 191
Introduction......Page 193
Problem Definition......Page 194
MA | PM for the LRP......Page 195
Chromosomes and Evaluation......Page 196
Selection of Parents and Crossover......Page 197
Population Management......Page 198
General Structure......Page 199
Commented Results......Page 201
Conclusion......Page 203
Introduction......Page 205
The Core Concept for KP......Page 206
The Core Concept for MKP......Page 207
MKP Cores and Efficiency Measures......Page 210
A Fixed Core Approach......Page 211
A Memetic Algorithm......Page 212
A Relaxation Guided VNS for the MKP......Page 213
Computational Experiments......Page 214
Conclusions......Page 216
Introduction......Page 219
Problem Setting......Page 220
Three-Phase Scheduling Approach......Page 221
NSGA-II for the Second Phase......Page 222
Combining NSGA-II with Local Search for the Second Phase......Page 223
Design of Experiments......Page 225
Performance Metrics for the Assessment of the Algorithms......Page 226
Results......Page 227
Conclusions and Future Research......Page 230
Introduction......Page 232
The Multi-objective MST......Page 233
The Algorithm......Page 235
Computational Experiments......Page 239
References......Page 242
Introduction......Page 244
A Generic Similarity Measure for Multi-labeled Graphs......Page 245
ACO for the Graph Matching Problem......Page 247
Reactive Search for the Graph Matching Problem......Page 249
Experimental Comparison Results of RS and ACO......Page 251
Conclusion and Further Work......Page 255
Introduction......Page 257
The TGV Metaphor......Page 258
Variation Operators......Page 259
Temporal Planning Problems......Page 260
CPT: An Optimal Temporal Planner......Page 261
Rationale for Using $Divide-and-Evolve$ for Temporal Planning......Page 262
Description of the State Space......Page 263
Representation-Specific Operators......Page 264
Single Objective Optimization......Page 265
A Multi-objective Problem......Page 266
Discussion and Further Work......Page 268
Introduction......Page 271
Variable Neighbourhood Search (VNS) Algorithms......Page 272
Job Shop Scheduling Problems......Page 273
The Modified VNS Implementation for JSS......Page 274
Experimental Results......Page 276
References......Page 279
Introduction......Page 282
Hybridization of Max-$npv-gpr$ Procedures......Page 284
An Illustrative Example......Page 287
Computational Experiences......Page 288
Other Application Areas......Page 289
Open Pit Mining......Page 290
Conclusions......Page 291
References......Page 292
Introduction......Page 294
Quasi-Pure Proportional Apportionment Model......Page 296
The VNTS Proposed......Page 298
Computational Experiences......Page 299
References......Page 301
300......Page 303
