Alba / Nedjah / (Eds.) Parallel Evolutionary Computations

1. Auflage 2006
ISBN: 978-3-540-32839-1
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 22, 247 Seiten

Reihe: Studies in Computational Intelligence

Parallel Evolutionary Computation focuses on the aspects related to the parallelization of evolutionary computations, such as parallel genetic operators, parallel fitness evaluation, distributed genetic algorithms, and parallel hardware implementations, as well as on their impact on several applications.

The book is divided into four parts. The first part deals with a clear software-like and algorithmic vision on parallel evolutionary optimizations. The second part is about hardware implementations of genetic algorithms, a valuable topic which is hard to find in the present literature. The third part treats the problem of distributed evolutionary computation and presents three interesting applications wherein parallel EC new ideas are featured. Finally, the last part deals with the up-to-date field of parallel particle swarm optimization to illustrate the intrinsic similarities and potential extensions to techniques in this domain. The book offers a wide spectrum of sample works developed in leading research throughout the world about parallel implementations of efficient techniques at the heart of computational intelligence. It will be useful both for beginners and experienced researchers in the field of computational intelligence.

Written for:
Researchers, engineers, graduate students in Computational Intelligence, Evolutionary Algorithms

Keywords: Evolutionary Computations

Autoren/Hrsg.

Alba, Enrique

Nedjah, N.

Alba, E.

(Eds.), Brazil

Inhaltsverzeichnis

1;Preface;7
1.1;Part I: Parallel Evolutionary Optimization;8
1.2;Part II: Parallel Hardware for Genetic Algorithms;8
1.3;Part III: Distributed Evolutionary Computation;9
1.4;Part IV: Parallel Particle Swarm Optimization;9
2;Contents;11
3;List of Figures;17
4;List of Tables;21
5;List of Algorithms;23
6;Part I Parallel Evolutionary Optimization;24
6.1;1 A Model for Parallel Operators in Genetic Algorithms;25
6.1.1;1.1 Introduction;25
6.1.2;1.2 Implicit Parallel Operators in Canonical and Conventional Varying Mutation GAs;28
6.1.3;1.3 A Model of Parallel Varying Mutation GA ( GA- SRM);29
6.1.4;1.4 0/1 Multiple Knapsacks Problems;34
6.1.5;1.5 Studying the Structure of the Parallel Varying Mutation GA-SRM;36
6.1.6;1.6 Comparing Conventional and Parallel Varying Mutation Models;40
6.1.7;1.7 Distributed GA with Parallel Varying Mutation;45
6.1.8;1.8 Summary;51
6.1.9;References;51
6.2;2 Parallel Evolutionary Multiobjective Optimization;54
6.2.1;2.1 Introduction;54
6.2.2;2.2 Multiobjective Optimization;56
6.2.3;2.3 A Parallel MOEA: pPAES;64
6.2.4;2.4 Summary;70
6.2.5;Acknowledgments;71
6.2.6;References;71
7;Part II Parallel Hardware for Genetic Algorithms;78
7.1;3 A Reconfigurable Parallel Hardware for Genetic Algorithms;79
7.1.1;3.1 Introduction;79
7.1.2;3.2 Principles of Genetic Algorithms;80
7.1.3;3.3 Overall Architecture for the Hardware Genetic Algorithm;81
7.1.4;3.4 Detailed Component Architectures;81
7.1.5;3.5 Performance Results;87
7.1.6;3.6 Summary;88
7.1.7;References;89
7.2;4 Reconfigurable Computing and Parallelism for Implementing and Accelerating Evolutionary Algorithms;90
7.2.1;4.1 Introduction;90
7.2.2;4.2 Reconfigurable Computing and FPGA;91
7.2.3;4.3 Implementing a Genetic Algorithm for Solving the TSP Using Parallelism and FPGAs;93
7.2.4;4.4 Hardware Acceleration of a Parallel Evolutionary Algorithm;103
7.2.5;4.5 Summary;110
7.2.6;Acknowledgements;110
7.2.7;References;111
8;Part III Distributed Evolutionary Computation;113
8.1;5 Performance of Distributed GAs on DNA Fragment Assembly;114
8.1.1;5.1 Introduction;114
8.1.2;5.2 DNA Fragment Assembly Problem;115
8.1.3;5.3 Distributed Genetic Algorithms;118
8.1.4;5.4 DNA Fragment Assembly Using a Distributed GA;120
8.1.5;5.5 Experimental Results;122
8.1.6;5.6 Summary;130
8.1.7;Acknowledgments;131
8.1.8;References;131
8.2;6 On Parallel Evolutionary Algorithms on the Computational Grid;133
8.2.1;6.1 Introduction;133
8.2.2;6.2 Principles of Evolutionary Algorithms;134
8.2.3;6.3 Parallel EAs on the Computational Grid;135
8.2.4;6.4 Frameworks for Grid-based EAs – The ParadisEO- CMW Case;143
8.2.5;6.5 Conclusion;146
8.2.6;References;147
8.3;7 Parallel Evolutionary Algorithms on Consumer-Level Graphics Processing Unit;149
8.3.1;7.1 Introduction;149
8.3.2;7.2 Parallel and Distributed Evolutionary Algorithms;150
8.3.3;7.3 Graphics Processing Unit;152
8.3.4;7.4 Data Organization;155
8.3.5;7.5 Evolutionary Programming on GPU;156
8.3.6;7.6 Experimental Results and Visualization;162
8.3.7;7.7 Summary;170
8.3.8;Acknowledgment;170
8.3.9;References;170
9;Part IV Parallel Particle Swarm Optimization;172
9.1;8 Intelligent Parallel Particle Swarm Optimization Algorithms;173
9.1.1;8.1 Introduction;173
9.1.2;8.2 Parallel Particle Swarm Optimization;179
9.1.3;8.3 Experimental Results;184
9.1.4;8.4 Conclusions;188
9.1.5;References;188
9.2;9 Parallel Ant Colony Optimization for 3D Protein Structure Prediction using the HP Lattice Model;190
9.2.1;9.1 Introduction;190
9.2.2;9.2 Background;191
9.2.3;9.3 Ant Colony Optimization;196
9.2.4;9.4 ACO Implementation;198
9.2.5;9.5 Results;202
9.2.6;9.6 Conclusion and Future Work;208
9.2.7;References;210
10;Subject Index;212
11;Author Index;214

Leseproben

4 Reconfigurable Computing and Parallelism for Implementing and Accelerating Evolutionary Algorithms (p. 71-72)

Miguel A. Vega Rodr´ýguez1, Juan A. G´omez Pulido1, Juan M. S´anchez
P´erez1, Jos´e M. Granado Criado1, and Manuel Rubio del Solar2
1 Departamento de Inform´atica,
Escuela Polit´ecnica, Universidad de Extremadura,
Campus Universitario s/n, 10071 C´aceres, Spain
(mavega,jangomez,sanperez,granado)@unex.es, http://arco.unex.es
2 Servicio de Inform´atica, Universidad de Extremadura,
Avda. de Elvas s/n, Badajoz, Spain
[e-mail]

Reconfigurable Computing is a technique for executing algorithms directly on the hardware in order to accelerate and increase their performance. Recon- figurable hardware consists of programmed FPGA chips for working as specific purpose coprocessors. The algorithms to be executed are programmed by means of description hardware languages and implemented in hardware using synthesis tools. Recon.gurable Computing is very useful for processing high computational cost algorithms because the algorithms implemented in a speci .c hardware get greater performance than if they are processed by a general purpose conventional processor. So Recon.gurable Computing and parallel techniques have been applied on a genetic algorithm for solving the salesman problem and on a parallel evolutionary algorithm for time series predictions. The hardware implementation of these two problems allows a wide set of tools and techniques to be shown. In both cases satisfactory experimental performances have been obtained.

4.1 Introduction

The reader will .nd two instances of hardware implementation of evolutionary algorithms in this chapter. Both instances provide distinct points of view on how to apply recon.gurable computing technology to increase algorithm e.ciency. Two cases are considered: a genetic algorithm and a parallel evolutionary algorithm. As a result, many .elds of recon.gurable hardware techniques are covered, such as modeling by means of high-level hardware description languages, implementation on di.erent recon.gurable chips, hierarchical design, etc.

In Section 4.2 a general introductory view about Recon.gurable Computing and Field Programmable Gate Arrays (FPGAs) circuits, programming languages for algorithm modelling and implementing and the recon.gurable prototyped platforms used is o.ered. This will give us an idea about why this technology for the synthesis of the evolutionary algorithms is useful. In Section 4.3 we perform a detailed study on the use of parallelism and FPGAs for implementing Genetic Algorithms (GAs). In particular, we do an experimental study using the Traveling Salesman Problem (TSP). After an overview on the TSP, we explain the GA used for solving it. Then, we study the hardware implementation of this algorithm, detailing 13 di.erent hardware versions. Each new version improves the previous one, and many of these improvements are based on the use of parallelism techniques. In this section we also show and analyse the results found: Parallelism techniques that obtain better results, hardware/software comparisons, resource use, operation frequency, etc. We conclude stating FPGA implementation is better when the problem size increases or when better solutions (nearer to the optimum) must be found.

Finally, in Section 4.4 we show an application of Recon.gurable Computing for accelerating the execution of one of the steps of a parallel evolutionary algorithm. In the proposed algorithm the intermediate results evolve to find the local optimum. The algorithm has been created to increase the precision in the time series behaviour prediction. To do this, a set of processing units works in parallel mode to send its results to an evolutionary unit. This unit must determine an optimum value and generate a new input parameter sequence for the parallel units. The evolutionary unit has been implemented in the hardware in order to study its performance. We have found the algorithm execution is accelerated. This result encourages us to design, in the near future, a specific purpose processor for time series identification.