Parallel Metaheuristics A New Class of Algorithms

by Alba, Enrique

• ISBN13: 9780471678069
• ISBN10: 0471678066
• Edition: 1st
• Format: Hardcover
• Copyright: 2005-09-08
• Publisher: Wiley-Interscience

Summary

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 Biography

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.

Table of Contents

Foreword	xi
Preface	xiii
Contributors	xv
Part I INTRODUCTION TO METAHEURISTICS AND PARALLELISM	1	(104)
An Introduction to Metaheuristic Techniques	3	(40)
Christian Blum
Andrea Roli
Enrique Alba
Introduction	3	(5)
Trajectory Methods	8	(11)
Population-Based Methods	19	(9)
Decentralized Metaheuristics	28	(1)
Hybridization of Metaheuristics	29	(2)
Conclusions	31	(12)
References	31	(12)
Measuring the Performance of Parallel Metaheuristics	43	(20)
Enrique Alba
Gabriel Luque
Introduction	43	(1)
Parallel Performance Measures	44	(4)
How to Report Results	48	(6)
Illustrating the Influence of Measures	54	(6)
Conclusions	60	(3)
References	60	(3)
New Technologies in Parallelism	63	(16)
Enrique Alba
Antonio J. Nebro
Introduction	63	(1)
Parallel Computer Architectures: An Overview	63	(2)
Shared-Memory and Distributed-Memory Programming	65	(3)
Shared-Memory Tools	68	(2)
Distributed-Memory Tools	70	(4)
Which of Them?	74	(1)
Summary	75	(4)
References	76	(3)
Metaheuristics and Parallelism	79	(26)
Enrique Alba
El-Ghazali Talbi
Gabriel Luque
Nouredine Melab
Introduction	79	(1)
Parallel LSMs	80	(1)
Case Studies of Parallel LSMs	81	(4)
Parallel Evolutionary Algorithms	85	(2)
Case Studies of Parallel EAs	87	(6)
Other Models	93	(2)
Conclusions	95	(10)
References	96	(9)
Part II PARALLEL METAHEURISTIC MODELS	105	(318)
Parallel Genetic Algorithms	107	(20)
Gabriel Luque
Enrique Alba
Bernabe Dorronsoro
Introduction	107	(1)
Panmictic Genetic Algorithms	108	(2)
Structured Genetic Algorithms	110	(2)
Parallel Genetic Algorithms	112	(6)
Experimental Results	118	(3)
Summary	121	(6)
References	122	(5)
Parallel Genetic Programming	127	(28)
F. Fernandez
G. Spezzano
M. Tomassini
L. Vanneschi
Introduction to GP	127	(3)
Models of Parallel and Distributed GP	130	(4)
Problems	134	(3)
Real-Life Applications	137	(2)
Placement and Routing in FPGA	139	(5)
Data Classification Using Cellular Genetic Programming	144	(6)
Concluding Discussion	150	(5)
References	150	(5)
Parallel Evolution Strategies	155	(16)
Gunter Rudolph
Introduction	155	(1)
Deployment Scenarios of Parallel Evolutionary Algorithms	156	(3)
Sequential Evolutionary Algorithms	159	(1)
Parallel Evolutionary Algorithms	159	(6)
Conclusions	165	(6)
References	165	(6)
Parallel Ant Colony Algorithms	171	(32)
Stefan Janson
Daniel Merkle
Martin Middendorf
Introduction	171	(1)
Ant Colony Optimization	172	(3)
Parallel ACO	175	(15)
Hardware Parallelization of ACO	190	(5)
Other Ant Colony Approaches	195	(8)
References	197	(6)
Parallel Estimation of Distribution Algorithms	203	(20)
Julio Madera
Enrique Alba
Alberto Ochoa
Introduction	203	(1)
Levels of Parallelism in EDA	204	(2)
Parallel Models for EDAs	206	(10)
A Classification of Parallel EDAs	216	(3)
Conclusions	219	(4)
References	220	(3)
Parallel Scatter Search	223	(24)
F. Garcia
M. Garcia
B. Melian
J. A. Moreno-Perez
J. M. Moreno-Vega
Introduction	223	(1)
Scatter Search	224	(1)
Parallel Scatter Search	225	(4)
Application of Scatter Search to the p-Median Problem	229	(3)
Application of Scatter Search to Feature Subset Selection	232	(7)
Computational Experiments	239	(4)
Conclusions	243	(4)
References	244	(3)
Parallel Variable Neighborhood Search	247	(20)
Jose A. Moreno-Perez
Pierre Hansen
Nenad Mladenovic
Introduction	247	(1)
The VNS Metaheuristic	248	(3)
The Parallelizations	251	(7)
Application of VNS for the p-median	258	(4)
Computational Experiments	262	(1)
Conclusions	263	(4)
References	264	(3)
Parallel Simulated Annealing	267	(22)
M. Emin Aydin
Vecihi Yigit
Introduction	267	(1)
Simulated Annealing	268	(1)
Parallel Simulated Annealing	269	(6)
A Case Study	275	(8)
Summary	283	(6)
References	284	(5)
Parallel Tabu Search	289	(26)
Teodor Gabriel Crainic
Michel Gendreau
Jean-Yves Potvin
Introduction	289	(1)
Tabu Search	290	(1)
Parallelization Strategies for Tabu Search	291	(3)
Literature Review	294	(8)
Two Parallel Tabu Search Heuristics for Real-Time Fleet Management	302	(3)
Perspectives and Research Directions	305	(10)
References	306	(9)
Parallel Greedy Randomized Adaptive Search Procedures	315	(32)
Mauricio G. C. Resende
Celso C. Ribeiro
Introduction	315	(2)
Multiple-Walk Independent-Thread Strategies	317	(6)
Multiple-Walk Cooperative-Thread Strategies	323	(4)
Some Parallel GRASP Implementations	327	(13)
Conclusion	340	(7)
References	341	(6)
Parallel Hybrid Metaheuristics	347	(24)
Carlos Cotta
El-Ghazali Talbi
Enrique Alba
Introduction	347	(1)
Historical Notes on Hybrid Metaheuristics	348	(2)
Classifying Hybrid Metaheuristics	350	(5)
Implementing Parallel Hybrid Metaheuristics	355	(3)
Applications of Parallel Hybrid Metaheuristics	358	(1)
Conclusions	359	(12)
References	359	(12)
Parallel Multiobjective Optimization	371	(24)
Antonio J. Nebro
Francisco Luna
El-Ghazali Talbi
Enrique Alba
Introduction	371	(1)
Parallel Metaheuristics for Multiobjective Optimization	372	(5)
Two Parallel Multiobjective Metaheuristics	377	(2)
Experimentation	379	(7)
Conclusions and Future Work	386	(9)
References	387	(8)
Parallel Heterogeneous Metaheuristics	395	(28)
Francisco Luna
Enrique Alba
Antonio J. Nebro
Introduction	395	(2)
Heterogeneous Metaheuristics Survey	397	(3)
Taxonomy of Parallel Heterogeneous Metaheuristics	400	(4)
Frameworks for Heterogeneous Metaheuristics	404	(2)
Concluding Remarks	406	(1)
Annotated Bibliography	407	(16)
References	412	(11)
Part III THEORY AND APPLICATIONS	423	(128)
Theory of Parallel Genetic Algorithms	425	(22)
Erick Cantu-Paz
Introduction	425	(3)
Master-Slave Parallel GAs	428	(2)
Multipopulation Parallel GAs	430	(7)
Cellular Parallel GAs	437	(1)
Conclusions	438	(9)
References	439	(8)
Parallel Metaheuristics Applications	447	(48)
Teodor Gabriel Crainic
Nourredine Hail
Introduction	447	(1)
Parallel Metaheuristics	448	(3)
Graph Coloring	451	(1)
Graph Partitioning	452	(4)
Steiner Tree Problem	456	(1)
Set Partitioning and Covering	457	(2)
Satisfiability Problems	459	(3)
Quadratic Assignment	462	(2)
Location Problems	464	(4)
Network Design	468	(3)
The Traveling Salesman Problem	471	(5)
Vehicle Routing Problems	476	(3)
Summary	479	(16)
References	480	(15)
Parallel Metaheuristics in Telecommunications	495	(22)
Sergio Nesmachnow
Hector Cancela
Enrique Alba
Francisco Chicano
Introduction	495	(1)
Network Design	496	(6)
Network Routing	502	(2)
Network Assignment and Dimensioning	504	(6)
Conclusions	510	(7)
References	510	(7)
Bioinformatics and Parallel Metaheuristics	517	(34)
Oswaldo Trelles
Andres Rodriguez
Introduction	517	(2)
Bioinformatics at a Glance	519	(3)
Parallel Computers	522	(4)
Bioinformatic Applications	526	(8)
Parallel Metaheuristics in Bioinformatics	534	(9)
Conclusions	543	(8)
References	543	(8)
Index	551