Optimization Techniques for Solving Complex Problems

CHAPTER 4

Analyzing Parallel Cellular Genetic Algorithms

G. LUQUE and E. ALBA

Universidad de Málaga, Spain

B. DORRONSORO

Université du Luxembourg, Luxembourg

4.1 INTRODUCTION

Genetic algorithms are population-based metaheuristics that are very suitable for parallelization because their main operations (i.e., crossover, mutation, local search, and function evaluation) can be performed independently on different individuals. As a consequence, the performance of these population-based algorithms is improved especially when run in parallel.

Two parallelizing strategies are especially relevant for population-based algorithms: (1) parallelization of computation, in which the operations commonly applied to each individual are performed in parallel, and (2) parallelization of population, in which the population is split into different parts, each evolving in semi-isolation (individuals can be exchanged between subpopulations). Among the most widely known types of structured GAs, the distributed (dGA) (or coarse-grained) and cellular (cGA) (or fine-grained) algorithms are very popular optimization procedures (see Figure 4.1). The parallelization of the population strategy is especially interesting, since it not only allows speeding up the computation, but also improving the search capabilities of GAs [1,2].

In this chapter we focus on cGAs, which have been demonstrated to be more accurate ...