Parallel metaheuristics : a new class of algorithms

Solving complex optimization problems with parallel metaheuristics

Parallel Metaheuristics brings together an international group of experts in parallelism and metaheuristics to provide a much-needed synthesis of these two fields. Readers discover how metaheuristic techniques can provide useful and practical solutions for a wide range of problems and application domains, with an emphasis on the fields of telecommunications and bioinformatics. This volume fills a long-existing gap, allowing researchers and practitioners to develop efficient metaheuristic algorithms to find solutions.

The book is divided into three parts:
* Part One: Introduction to Metaheuristics and Parallelism, including an Introduction to Metaheuristic Techniques, Measuring the Performance of Parallel Metaheuristics, New Technologies in Parallelism, and a head-to-head discussion on Metaheuristics and Parallelism
* Part Two: Parallel Metaheuristic Models, including Parallel Genetic Algorithms, Parallel Genetic Programming, Parallel Evolution Strategies, Parallel Ant Colony Algorithms, Parallel Estimation of Distribution Algorithms, Parallel Scatter Search, Parallel Variable Neighborhood Search, Parallel Simulated Annealing, Parallel Tabu Search, Parallel GRASP, Parallel Hybrid Metaheuristics, Parallel Multi-Objective Optimization, and Parallel Heterogeneous Metaheuristics
* Part Three: Theory and Applications, including Theory of Parallel Genetic Algorithms, Parallel Metaheuristics Applications, Parallel Metaheuristics in Telecommunications, and a final chapter on Bioinformatics and Parallel Metaheuristics

Each self-contained chapter begins with clear overviews and introductions that bring the reader up to speed, describes basic techniques, and ends with a reference list for further study. Packed with numerous tables and figures to illustrate the complex theory and processes, this comprehensive volume also includes numerous practical real-world optimization problems and their solutions.

This is essential reading for students and researchers in computer science, mathematics, and engineering who deal with parallelism, metaheuristics, and optimization in general.

Author Notes

ENRIQUE ALBA, PhD, is a Professor of Computer Science at the University of Málaga, Spain. His research interests involve the design and application of evolutionary algorithms, neural networks, parallelism, and metaheuristic algorithms to solve problems in telecommunications, combinatorial optimization, and bioinformatics. Dr. Alba has published many papers in leading journals and international conferences, and has garnered international awards for his research.

Christian Blum and Andrea Roli and Enrique AlbaEnrique Alba and Gabriel LuqueEnrique Alba and Antonio J. NebroEnrique Alba and El-Ghazali Talbi and Gabriel Luque and Nouredine MelabGabriel Luque and Enrique Alba and Bernabe DorronsoroF. Fernandez and G. Spezzano and M. Tomassini and L. VanneschiGunter RudolphStefan Janson and Daniel Merkle and Martin MiddendorfJulio Madera and Enrique Alba and Alberto OchoaF. Garcia and M. Garcia and B. Melian and J. A. Moreno-Perez and J. M. Moreno-VegaJose A. Moreno-Perez and Pierre Hansen and Nenad MladenovicM. Emin Aydin and Vecihi YigitTeodor Gabriel Crainic and Michel Gendreau and Jean-Yves PotvinMauricio G. C. Resende and Celso C. RibeiroCarlos Cotta and El-Ghazali Talbi and Enrique AlbaAntonio J. Nebro and Francisco Luna and El-Ghazali Talbi and Enrique AlbaFrancisco Luna and Enrique Alba and Antonio J. NebroErick Cantu-PazTeodor Gabriel Crainic and Nourredine HailSergio Nesmachnow and Hector Cancela and Enrique Alba and Francisco ChicanoOswaldo Trelles and Andres Rodriguez

Foreword	p. xi
Preface	p. xiii
Contributors	p. xv
Part I Introduction to Metaheuristics and Parallelism	p. 1
1 An Introduction to Metaheuristic Techniques	p. 3
1.1 Introduction	p. 3
1.2 Trajectory Methods	p. 8
1.3 Population-Based Methods	p. 19
1.4 Decentralized Metaheuristics	p. 28
1.5 Hybridization of Metaheuristics	p. 29
1.6 Conclusions	p. 31
References	p. 31
2 Measuring the Performance of Parallel Metaheuristics	p. 43
2.1 Introduction	p. 43
2.2 Parallel Performance Measures	p. 44
2.3 How to Report Results	p. 48
2.4 Illustrating the Influence of Measures	p. 54
2.5 Conclusions	p. 60
References	p. 60
3 New Technologies in Parallelism	p. 63
3.1 Introduction	p. 63
3.2 Parallel Computer Architectures: An Overview	p. 63
3.3 Shared-Memory and Distributed-Memory Programming	p. 65
3.4 Shared-Memory Tools	p. 68
3.5 Distributed-Memory Tools	p. 70
3.6 Which of Them?	p. 74
3.7 Summary	p. 75
References	p. 76
4 Metaheuristics and Parallelism	p. 79
4.1 Introduction	p. 79
4.2 Parallel LSMs	p. 80
4.3 Case Studies of Parallel LSMs	p. 81
4.4 Parallel Evolutionary Algorithms	p. 85
4.5 Case Studies of Parallel EAs	p. 87
4.6 Other Models	p. 93
4.7 Conclusions	p. 95
References	p. 96
Part II Parallel Metaheuristic Models	p. 105
5 Parallel Genetic Algorithms	p. 107
5.1 Introduction	p. 107
5.2 Panmictic Genetic Algorithms	p. 108
5.3 Structured Genetic Algorithms	p. 110
5.4 Parallel Genetic Algorithms	p. 112
5.5 Experimental Results	p. 118
5.6 Summary	p. 121
References	p. 122
6 Parallel Genetic Programming	p. 127
6.1 Introduction to GP	p. 127
6.2 Models of Parallel and Distributed GP	p. 130
6.3 Problems	p. 134
6.4 Real-Life Applications	p. 137
6.5 Placement and Routing in FPGA	p. 139
6.6 Data Classification Using Cellular Genetic Programming	p. 144
6.7 Concluding Discussion	p. 150
References	p. 150
7 Parallel Evolution Strategies	p. 155
7.1 Introduction	p. 155
7.2 Deployment Scenarios of Parallel Evolutionary Algorithms	p. 156
7.3 Sequential Evolutionary Algorithms	p. 159
7.4 Parallel Evolutionary Algorithms	p. 159
7.5 Conclusions	p. 165
References	p. 165
8 Parallel Ant Colony Algorithms	p. 171
8.1 Introduction	p. 171
8.2 Ant Colony Optimization	p. 172
8.3 Parallel ACO	p. 175
8.4 Hardware Parallelization of ACO	p. 190
8.5 Other Ant Colony Approaches	p. 195
References	p. 197
9 Parallel Estimation of Distribution Algorithms	p. 203
9.1 Introduction	p. 203
9.2 Levels of Parallelism in EDA	p. 204
9.3 Parallel Models for EDAs	p. 206
9.4 A Classification of Parallel EDAs	p. 216
9.5 Conclusions	p. 219
References	p. 220
10 Parallel Scatter Search	p. 223
10.1 Introduction	p. 223
10.2 Scatter Search	p. 224
10.3 Parallel Scatter Search	p. 225
10.4 Application of Scatter Search to the p-Median Problem	p. 229
10.5 Application of Scatter Search to Feature Subset Selection	p. 232
10.6 Computational Experiments	p. 239
10.7 Conclusions	p. 243
References	p. 244
11 Parallel Variable Neighborhood Search	p. 247
11.1 Introduction	p. 247
11.2 The VNS Metaheuristic	p. 248
11.3 The Parallelizations	p. 251
11.4 Application of VNS for the p-median	p. 258
11.5 Computational Experiments	p. 262
11.6 Conclusions	p. 263
References	p. 264
12 Parallel Simulated Annealing	p. 267
12.1 Introduction	p. 267
12.2 Simulated Annealing	p. 268
12.3 Parallel Simulated Annealing	p. 269
12.4 A Case Study	p. 275
12.5 Summary	p. 283
References	p. 284
13 Parallel Tabu Search	p. 289
13.1 Introduction	p. 289
13.2 Tabu Search	p. 290
13.3 Parallelization Strategies for Tabu Search	p. 291
13.4 Literature Review	p. 294
13.5 Two Parallel Tabu Search Heuristics for Real-Time Fleet Management	p. 302
13.6 Perspectives and Research Directions	p. 305
References	p. 306
14 Parallel Greedy Randomized Adaptive Search Procedures	p. 315
14.1 Introduction	p. 315
14.2 Multiple-Walk Independent-Thread Strategies	p. 317
14.3 Multiple-Walk Cooperative-Thread Strategies	p. 323
14.4 Some Parallel GRASP Implementations	p. 327
14.5 Conclusion	p. 340
References	p. 341
15 Parallel Hybrid Metaheuristics	p. 347
15.1 Introduction	p. 347
15.2 Historical Notes on Hybrid Metaheuristics	p. 348
15.3 Classifying Hybrid Metaheuristics	p. 350
15.4 Implementing Parallel Hybrid Metaheuristics	p. 355
15.5 Applications of Parallel Hybrid Metaheuristics	p. 358
15.6 Conclusions	p. 359
References	p. 359
16 Parallel Multiobjective Optimization	p. 371
16.1 Introduction	p. 371
16.2 Parallel Metaheuristics for Multiobjective Optimization	p. 372
16.3 Two Parallel Multiobjective Metaheuristics	p. 377
16.4 Experimentation	p. 379
16.5 Conclusions and Future Work	p. 386
References	p. 387
17 Parallel Heterogeneous Metaheuristics	p. 395
17.1 Introduction	p. 395
17.2 Heterogeneous Metaheuristics Survey	p. 397
17.3 Taxonomy of Parallel Heterogeneous Metaheuristics	p. 400
17.4 Frameworks for Heterogeneous Metaheuristics	p. 404
17.5 Concluding Remarks	p. 406
17.6 Annotated Bibliography	p. 407
References	p. 412
Part III Theory and Applications	p. 423
18 Theory of Parallel Genetic Algorithms	p. 425
18.1 Introduction	p. 425
18.2 Master-Slave Parallel GAs	p. 428
18.3 Multipopulation Parallel GAs	p. 430
18.4 Cellular Parallel GAs	p. 437
18.5 Conclusions	p. 438
References	p. 439
19 Parallel Metaheuristics Applications	p. 447
19.1 Introduction	p. 447
19.2 Parallel Metaheuristics	p. 448
19.3 Graph Coloring	p. 451
19.4 Graph Partitioning	p. 452
19.5 Steiner Tree Problem	p. 456
19.6 Set Partitioning and Covering	p. 457
19.7 Satisfiability Problems	p. 459
19.8 Quadratic Assignment	p. 462
19.9 Location Problems	p. 464
19.10 Network Design	p. 468
19.11 The Traveling Salesman Problem	p. 471
19.12 Vehicle Routing Problems	p. 476
19.13 Summary	p. 479
References	p. 480
20 Parallel Metaheuristics in Telecommunications	p. 495
20.1 Introduction	p. 495
20.2 Network Design	p. 496
20.3 Network Routing	p. 502
20.4 Network Assignment and Dimensioning	p. 504
20.5 Conclusions	p. 510
References	p. 510
21 Bioinformatics and Parallel Metaheuristics	p. 517
21.1 Introduction	p. 517
21.2 Bioinformatics at a Glance	p. 519
21.3 Parallel Computers	p. 522
21.4 Bioinformatic Applications	p. 526
21.5 Parallel Metaheuristics in Bioinformatics	p. 534
21.6 Conclusions	p. 543
References	p. 543

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents