Metaheuristics for hard optimization : methods and case studies / J. Dréo ... [and others].

Format:

Book

Contributor:

Dréo, J. (Johann)

George R. Fink Memorial Fund.

Language:

English

Subjects (All):

Combinatorial optimization.

Computer algorithms.

Physical Description:

xii, 369 pages : illustrations ; 24 cm

Place of Publication:

Berlin : Springer, [2006]

Summary:

Metaheuristics for Hard Optimization comprises of three parts. The first part is devoted to the detailed presentation of the four most widely known metaheuristics: b" the simulated annealing method, b" tabu search, b" the evolutionary algorithms, b" ant colony algorithms. Each one of these metaheuristics is actually a family of methods, of which the essential elements are discussed. In the second part, the book presents some other less widespread metaheuristics, then, extensions of metaheuristics and some ways of research are described . The problem of the choice of a metaheuristic is posed and solution methods are discussed. The last part concentrates on three case studies from telecommunications, air traffic control, and vehicle routing.

Contents:

Part I Presentation of the Main Metaheuristics

1 Simulated Annealing 23

1.2 Presentation of the method 24

1.2.1 Analogy between an optimization problem and some physical phenomena 24

1.2.2 Real annealing and simulated annealing 25

1.2.3 Simulated annealing algorithm 25

1.3 Theoretical approaches 27

1.3.1 Theoretical convergence of simulated annealing 27

1.3.2 Configuration space 28

1.3.3 Rules of acceptance 30

1.3.4 Annealing scheme 30

1.4 Parallelization of the simulated annealing algorithm 32

1.5 Some applications 35

1.5.1 Benchmark problems of combinatorial optimization 35

1.5.2 Layout of electronic circuits 36

1.5.3 Search for an equivalent schema in electronics 40

1.5.4 Practical applications in various fields 42

1.6 Advantages and disadvantages of the method 44

1.7 Simple practical suggestions for the beginners 44

2 Tabu Search 47

2.2 The quadratic assignment problem 49

2.3 Basic tabu search 51

2.3.1 Neighborhood 51

2.3.2 Moves, neighborhood 52

2.3.3 Evaluation of the neighborhood 54

2.4 Candidate list 56

2.5 Short-term memory 57

2.5.1 Hashing tables 57

2.5.2 Tabu list 59

2.5.3 Duration of tabu conditions 60

2.5.4 Aspiration conditions 66

2.6 Convergence of tabu search 66

2.7 Long-term memory 69

2.7.1 Frequency-based memory 69

2.7.2 Obligation to carry out move 71

2.8 Strategic oscillations 72

3 Evolutionary Algorithms 75

3.1 From genetics to engineering 75

3.2 The generic evolutionary algorithm 77

3.2.1 Selection operators 77

3.2.2 Variation operators 78

3.2.3 The generational loop 78

3.2.4 Solving a simple problem 79

3.3 Selection operators 81

3.3.1 Selection pressure 81

3.3.2 Genetic drift 82

3.3.3 Proportional selection 83

3.3.4 Tournament selection 88

3.3.5 Truncation selection 90

3.3.6 Replacement selections 90

3.3.7 Fitness function 92

3.4 Variation operators and representation 93

3.4.1 Generalities about the variation operators 93

3.4.2 Binary representation 97

3.4.3 Real representation 101

3.4.4 Some discrete representations for the permutation problems 108

3.4.5 Representation of parse trees for the genetic programming 113

3.5 Particular case of the genetic algorithms 118

3.6 Some considerations on the convergence of the evolutionary algorithms 119

4 Ant Colony Algorithms 123

4.2 Collective behavior of social insects 124

4.2.1 Self-organization and behavior 124

4.2.2 Natural optimization: pheromonal trails 127

4.3 Optimization by ant colonies and the traveling salesman problem 129

4.3.1 Basic algorithm 130

4.3.2 Variants 131

4.3.3 Choice of the parameters 134

4.4 Other combinatorial problems 134

4.5 Formalization and properties of ant colony optimization 135

4.5.1 Formalization 135

4.5.2 Pheromones and memory 137

4.5.3 Intensification/diversification 137

4.5.4 Local search and heuristics 138

4.5.5 Parallelism 138

4.5.6 Convergence 139

4.6 Prospect 139

4.6.1 Continuous optimization 139

4.6.2 Dynamic problems 147

4.6.3 Metaheuristics and ethology 147

4.6.4 Links with other metaheuristics 148

Part II Variants, Extensions and Methodological Advices

5 Some Other Metaheuristics 153

5.2 Some variants of simulated annealing 154

5.2.1 Simulated diffusion 154

5.2.2 Microcanonic annealing 155

5.2.3 The threshold method 157

5.2.4 "Great deluge" method 157

5.2.5 Method of the "record to record travel" 157

5.3 Noising method 159

5.4 Method of distributed search 159

5.5 "Alienor" method 160

5.6 Particle swarm optimization method 162

5.7 The estimation of distribution algorithm 166

5.8 GRASP method 169

5.9 "Cross-Entropy" method 170

5.10 Artificial immune systems 172

5.11 Method of differential evolution 173

5.12 Algorithms inspired by the social insects 175

6 Extensions 179

6.2 Adaptation for the continuous variable problems 179

6.2.1 General framework of "difficult" continuous optimization 179

6.2.2 Some continuous metaheuristics 185

6.3 Multimodal optimization 196

6.3.1 The problem 196

6.3.2 Niching with the sharing method 196

6.3.3 Niching with the deterministic crowding method 199

6.3.4 The clearing procedure 201

6.3.5 Speciation 203

6.4 Multiobjective optimization 206

6.4.1 Formalization of the problem 206

6.4.2 Simulated annealing based methods 208

6.4.3 Multiobjective evolutionary algorithms 211

6.5 Constrained evolutionary optimization 216

6.5.1 Penalization methods 217

6.5.2 Superiority of the feasible individuals 219

6.5.3 Repair methods 220

6.5.4 Variation operators satisfying the constraint structures 221

6.5.5 Other methods dealing with constraints 223

7 Methodology 225

7.2 Problem modeling 227

7.3 Neighborhood choice 228

7.3.1 "Simple" neighborhoods 228

7.3.2 Ejection chains 230

7.3.3 Decomposition into subproblems: POPMUSIC 231

7.3.4 Conclusions on modeling and neighborhood 233

7.4 Improving method, simulated annealing, taboo search...? 235

7.5 Adaptive Memory Programming 235

7.5.1 Ant colonies 236

7.5.2 Evolutionary or memetic algorithms 236

7.5.3 Scatter Search 236

7.5.4 Vocabulary building 238

7.5.5 Path relinking 239

7.6 Iterative heuristics comparison 240

7.6.1 Comparing proportion 241

7.6.2 Comparing iterative optimization methods 243

8 Optimization of UMTS Radio Access Networks with Genetic Algorithms 251

8.2 Introduction to mobile radio networks 252

8.2.1 Cellular network 252

8.2.2 Characteristic of the radio channel 253

8.2.3 Radio interface of the UMTS 255

8.3 Definition of the optimization problem 261

8.3.1 Radio planning of a UMTS network 261

8.3.2 Definition of the optimization problem 262

8.4 Application of the genetic algorithm to automatic planning 265

8.4.1 Coding 265

8.4.2 Genetic operators 266

8.4.3 Evaluation of the individuals 267

8.5 Results 267

8.5.1 Optimization of the capacity 269

8.5.2 Optimization of the loads 270

8.5.3 Optimization of the intercellular interferences 272

8.5.4 Optimization of the coverage 272

8.5.5 Optimization of the probability of access 273

9 Genetic Algorithms Applied to Air Traffic Management 277

9.1 En route conflict resolution 277

9.1.1 Complexity of the conflict resolution problem 280

9.1.2 Existing resolution methods 280

9.1.3 Modeling of the problem 281

9.1.4 Implementation of the genetic algorithm 285

9.1.5 Theoretical study of a simple example 288

9.1.6 Numerical application 292

9.1.7 Remarks 295

9.2 Ground Traffic optimization 296

9.2.1 Modeling 296

9.2.2 BB: the 1-against-n resolution method 300

9.2.3 GA and GA+BB: genetic algorithms 301

9.2.4 Experimental results 303

10 Constraint Programming and Ant Colonies Applied to Vehicle Routing Problems 307

10.2 Vehicle routing problems and constraint programming 308

10.2.1 Vehicle routing problems 308

10.2.2 Constraint programming 309

10.2.3 Constraint programming applied to PDP: ILOG Dispatcher 314

10.3 Ant colonies 316

10.3.1 Behavior of the real ants 316

10.3.2 Ant colonies, vehicle routing problem and constraint programming 316

10.3.3 Ant colony algorithm with backtracking 317

10.4 Experimental results 323

A Modeling of Simulated Annealing Through the Markov Chain Formalism 331

B Complete Example of Implementation of Tabu Search for the Quadratic Assignment Problem 339.

Notes:

Includes bibliographical references and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the George R. Fink Memorial Fund.

ISBN:

354023022X

OCLC:

61703224

Publisher Number:

9783540230229