Parallel Evolutionary Computations (eBook)

N. Nedjah, E. Alba, L. de Macedo Mourelle, State University of Rio De Janeiro, Brazil (Eds.) (Herausgeber)

eBook Download: PDF

2006 | 1. Auflage
247 Seiten
Springer-Verlag
978-3-540-32839-1 (ISBN)

Infos

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

Inhalt

Preface 7
Part I: Parallel Evolutionary Optimization 8
Part II: Parallel Hardware for Genetic Algorithms 8
Part III: Distributed Evolutionary Computation 9
Part IV: Parallel Particle Swarm Optimization 9
Contents 11
List of Figures 17
List of Tables 21
List of Algorithms 23
Part I Parallel Evolutionary Optimization 24
1 A Model for Parallel Operators in Genetic Algorithms 25
1.1 Introduction 25
1.2 Implicit Parallel Operators in Canonical and Conventional Varying Mutation GAs 28
1.3 A Model of Parallel Varying Mutation GA ( GA- SRM) 29
1.4 0/1 Multiple Knapsacks Problems 34
1.5 Studying the Structure of the Parallel Varying Mutation GA-SRM 36
1.6 Comparing Conventional and Parallel Varying Mutation Models 40
1.7 Distributed GA with Parallel Varying Mutation 45
1.8 Summary 51
References 51
2 Parallel Evolutionary Multiobjective Optimization 54
2.1 Introduction 54
2.2 Multiobjective Optimization 56
2.3 A Parallel MOEA: pPAES 64
2.4 Summary 70
Acknowledgments 71
References 71
Part II Parallel Hardware for Genetic Algorithms 78
3 A Reconfigurable Parallel Hardware for Genetic Algorithms 79
3.1 Introduction 79
3.2 Principles of Genetic Algorithms 80
3.3 Overall Architecture for the Hardware Genetic Algorithm 81
3.4 Detailed Component Architectures 81
3.5 Performance Results 87
3.6 Summary 88
References 89
4 Reconfigurable Computing and Parallelism for Implementing and Accelerating Evolutionary Algorithms 90
4.1 Introduction 90
4.2 Reconfigurable Computing and FPGA 91
4.3 Implementing a Genetic Algorithm for Solving the TSP Using Parallelism and FPGAs 93
4.4 Hardware Acceleration of a Parallel Evolutionary Algorithm 103
4.5 Summary 110
Acknowledgements 110
References 111
Part III Distributed Evolutionary Computation 113
5 Performance of Distributed GAs on DNA Fragment Assembly 114
5.1 Introduction 114
5.2 DNA Fragment Assembly Problem 115
5.3 Distributed Genetic Algorithms 118
5.4 DNA Fragment Assembly Using a Distributed GA 120
5.5 Experimental Results 122
5.6 Summary 130
Acknowledgments 131
References 131
6 On Parallel Evolutionary Algorithms on the Computational Grid 133
6.1 Introduction 133
6.2 Principles of Evolutionary Algorithms 134
6.3 Parallel EAs on the Computational Grid 135
6.4 Frameworks for Grid-based EAs – The ParadisEO- CMW Case 143
6.5 Conclusion 146
References 147
7 Parallel Evolutionary Algorithms on Consumer-Level Graphics Processing Unit 149
7.1 Introduction 149
7.2 Parallel and Distributed Evolutionary Algorithms 150
7.3 Graphics Processing Unit 152
7.4 Data Organization 155
7.5 Evolutionary Programming on GPU 156
7.6 Experimental Results and Visualization 162
7.7 Summary 170
Acknowledgment 170
References 170
Part IV Parallel Particle Swarm Optimization 172
8 Intelligent Parallel Particle Swarm Optimization Algorithms 173
8.1 Introduction 173
8.2 Parallel Particle Swarm Optimization 179
8.3 Experimental Results 184
8.4 Conclusions 188
References 188
9 Parallel Ant Colony Optimization for 3D Protein Structure Prediction using the HP Lattice Model 190
9.1 Introduction 190
9.2 Background 191
9.3 Ant Colony Optimization 196
9.4 ACO Implementation 198
9.5 Results 202
9.6 Conclusion and Future Work 208
References 210
Subject Index 212
Author Index 214

Textauszug

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.

Produkt-Details

• Erscheint lt. Verlag: 1.1.2006
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Technik
• ISBN-10: 3-540-32839-4 / 3540328394
• ISBN-13: 978-3-540-32839-1 / 9783540328391