Hugo Martires
580 California St., Suite 400
San Francisco, CA, 94104
An Architecture for Massive Parallelization of the Compact Genetic Algorithm
2004, Springer eBooks
visibility
…
description
2 pages
Sign up for access to the world's latest research
checkGet notified about relevant papers
checkSave papers to use in your research
checkJoin the discussion with peers
checkTrack your impact
Abstract
This paper presents an architecture which is suitable for a massive parallelization of the compact genetic algorithm. The approach is scalable, has low synchronization costs, and is fault tolerant. The paper argues that the benefits that can be obtained with the proposed methodology is potentially higher than those obtained with traditional parallel genetic algorithms.
Related papers
A survey of parallel distributed genetic algorithms
Complexity, 1999
In this work we review the most important existing developments and future trends in the class of Parallel Genetic Algorithms (PGAs). PGAs are mainly subdivided into coarse and fine grain PGAs, the coarse grain models being the most popular ones. An exceptional characteristic of PGAs is that they are not just the parallel version of a sequential algorithm intended to provide speed gains. Instead, they represent a new kind of meta-heuristics of higher efficiency and efficacy thanks to their structured population and parallel execution. The good robustness of these algorithms on problems of high complexity has led to an increasing number of applications in the fields of artificial intelligence, numeric and combinatorial optimization, business, engineering, etc. We make a formalization of these algorithms, and present a timely and topic survey of their most important traditional and recent technical issues. Besides that, useful summaries on their main applications plus Internet pointers to important web sites are included in order to help new researchers to access this growing area.
Massively Parallel Genetic Algorithms
Massively Parallel Processing Applications and Development, 1994
Heuristic algorithms are usually employed to find an optimal solution to NP-Complete problems. Genetic algorithms are among such algorithms and they are search algorithms based on the mechanics of natural selection and genetics. Since genetic algorithms work with a set of candidate solutions, parallelisation based on the SIMD paradigm seems to be the natural way to obtain a speed up. In this approach, the population of strings is distributed among the processing elements. Each of the strings is then processed independently of the other. The performance gain for this approach comes from the parallel execution of the strings, and hence, it is heavily dependent on the population size. The approach is favoured for genetic algorithms' applications where the parameter set for a particular run is well-known in advance, and where such applications require a big population size to solve the problem. DDAP fits nicely into the above requirements. The aim of the parallelisation is two-fold: the first one is to speedup the allocation process in DDAP which usually consists of thousands of documents and has to use a big population size, and second, it can be seen as an attempt to port the genetic algorithm's processes into SIMD machines.
The compact genetic algorithm
IEEE Transactions on Evolutionary Computation, 1999
This paper introduces the compact genetic algorithm (cGA) which represents the population as a probability distribution over the set of solutions and is operationally equivalent to the order-one behavior of the simple GA with uniform crossover. It processes each gene independently and requires less memory than the simple GA. The development of the compact GA is guided by a proper understanding of the role of the GA's parameters and operators. The paper clearly illustrates the mapping of the simple GA's parameters into those of an equivalent compact GA. Computer simulations compare both algorithms in terms of solution quality and speed.
Analysis of the Numerical Effects of Parallelism on a Parallel Genetic Algorithm
1996
Examines the effects of relaxed synchronization on both the numerical and parallel efficiency of parallel genetic algorithms (GAs). We describe a coarse-grain geographically structured parallel genetic algorithm. Our experiments provide preliminary evidence that asynchronous versions of these algorithms have a lower run-time than synchronous GAs. Our analysis shows that this improvement is due to (1) reduced synchronization costs and (2) higher numerical efficiency (e.g. fewer function evaluations) for the asynchronous GAs. This analysis includes a critique of the utility of traditional parallel performance measures for parallel GAs
Review of Parallel Genetic Algorithm Based on Computing Paradigm and Diversity in Search Space
ICTACT Journal on Soft Computing, 2013
Genetic Algorithm (GA), a stochastic optimization technique, doesn't ensure optimal solution every time. Nowadays there is a need to improve the performance of each and every application so that the time required for obtaining quality solution can be minimized. This paper gives a brief overview of theoretical advances and computing trends, particularly population diversity in PGA (Parallel GA) and provides information about how various authors, researchers, scientists have parallelized GA over various parallel computing paradigms viz. Cluster, MPP (Massively Parallel Processing), GPGPU (General purpose Graphics Processing Units), Grid, Cloud, Multicore/HPC to ensure more optimal solution every time with efficacy and efficiency.
Strategies for Parallel Genetic Computation of Optimization Problems
Biotechnology & Biotechnological Equipment, 2007
This paper explores the effi ciency of various strategies for parallel genetic computation of optimization problems on multicomputer platforms. The strategies for designing parallel genetic algorithms on multicomputer platforms are investigated considering the correlations of the algorithmic and the architectural spaces. Two parallel genetic computational models are considered based on the manager/workers and Single Program Multiple Data parallel paradigms. Parallelism profi ling and analysis of parallel system performance have been made for the different parallel computational models in respect to the scalability of the application and the scalability of the parallel machine size.
Adaptive Parallel Genetic Algorithm
2014
We propose a parallel genetic algorithm architecture which parameters are adapted automatically during the search process. The parameters of the search algorithm as selection pressure, mutation rate and mutation step size (or even others) are not fixed during the search process, but they are adapted in time. For their determination a simple, but effective method is used. The algorithm is able to adjust its properties according the currently solved problem, which allows also an unexperienced user to use parallel genetic algorithms without the need to set up its configuration a-priori for solving particular (specific) problems.
On the Accelerated Convergence of Genetic Algorithm Using GPU Parallel Operations
International Journal of Software Innovation, 2015
The genetic algorithm plays a very important role in many areas of applications. In this research, the authors propose to accelerate the evolution speed of the genetic algorithm by parallel computing, and optimize parallel genetic algorithms by methods such as the island model. The authors find that when the amount of population increases, the genetic algorithm tends to converge more rapidly into the global optimal solution; however, it also consumes greater amount of computation resources. To solve this problem, the authors take advantage of the many cores of GPUs to enhance computation efficiency and develop a parallel genetic algorithm for GPUs. Different from the usual genetic algorithm that uses one thread for computation of each chromosome, the parallel genetic algorithm using GPUs evokes large amount of threads simultaneously and allows the population to scale greatly. The large amount of the next generation population of chromosomes can be divided by a block method; and afte...
Improving flexibility and efficiency by adding parallelism to genetic algorithms
Statistics and computing, 2002
In this paper we develop a study on several types of parallel genetic algorithms (PGAs). Our motivation is to bring some uniformity to the proposal, comparison, and knowledge exchange among the traditionally opposite kinds of serial and parallel GAs. We comparatively analyze the properties of steady-state, generational, and cellular genetic algorithms. Afterwards, this study is extended to consider a distributed model consisting in a ring of GA islands. The analyzed features are the time complexity, selection pressure, schema processing rates, efficacy in finding an optimum, efficiency, speedup, and resistance to scalability. Besides that, we briefly discuss how the migration policy affects the search. Also, some of the search properties of cellular GAs are investigated. The selected benchmark is a representative subset of problems containing real world difficulties. We often conclude that parallel GAs are numerically better and faster than equivalent sequential GAs. Our aim is to shed some light on the advantages and drawbacks of various sequential and parallel GAs to help researchers using them in the very diverse application fields of the evolutionary computation.
The Parallel Genetic Algorithm Embedded with Downhill
Algorithms and Architectures for Parallel Processing - Proceedings of the 4th International Conference, 2000
Alogrithm (PGA) embedded with Downhill which is applied to the optimization of continuous functions. The strategy goes this way: Subpopulation tries to locate good local minima by PGA. When a subpopulation does not progress after a certain number of generations, downhill is taken into account. Alternative downhill method (depth first or width first) is to be used depending on the properties of different problems. At certain generation, local optima of each nodes are transmitted to each other with the support of MPI environment. Selection of genetic factors is discussed and comparison with traditional GA is made to illustrate the effectiveness of the algorithm. On the whole, the hybrid algorithm strives to gain breakthrough in the field of large scale computation and as a matter of fact it turns out to be quite successful.
An architecture for massive parallelization of the
compact genetic algorithm
Fernando G. Lobo, Cláudio F. Lima, and Hugo Mártires
ADEEC-FCT, Universidade do Algarve
Campus de Gambelas, 8000 Faro, Portugal.
{flobo,clima}@ualg.pt, [email protected]
Abstract. This paper presents an architecture which is suitable for a
massive parallelization of the compact genetic algorithm. The approach
is scalable, has low synchronization costs, and is fault tolerant. The pa-
per argues that the benefits that can be obtained with the proposed
methodology is potentially higher than those obtained with traditional
parallel genetic algorithms.
1 Introduction
With a traditional parallel genetic algorithm (GA) implementation, population
members need to be sent over a computer network, and that imposes a limit
on how fast they can be [1]. In this paper, we investigate the parallelization of
the compact genetic algorithm (cGA) [2], and take advantage of its compact
representation of the population do develop a parallelization scheme which sig-
nificantly reduces the communication overhead.
The cGA uses a probability vector as a model to represent the population.
The vector can be stored with ` × log2 (N + 1) bits (` is the chromosome length,
N is the population size), a different order of magnitude than the ` × N bits
needed to represent a population in a regular GA. Since communication costs can
be drastically reduced, it makes sense to clone the probability vector to several
computers, and let each computer work independently on solving the problem
by running a separate cGA. Then, the different probability vectors need to be
consolidated (or mixed) once in a while.
2 Massive parallelization of the compact GA
We have developed an asynchronous parallelization scheme which consists of a
manager processor, and an arbitrary number of worker processors. Initially, the
manager starts with a probability vector with 0.5 in all positions, just like in a
regular cGA. After that, it sends the vector to all workers who are willing to
contribute with CPU time.
Each worker processor runs a cGA on its own based on a local copy of the
probability vector. Workers do their job independently and only interrupt the
2
manager once in a while, after a predefined number of m fitness function evalu-
ations have elapsed.
During the interruption period, a worker sends the accumulated results of
the last m function evaluations as a vector of probability fluxes with respect to
the original probability vector. Subsequently, the manager adds the probability
fluxes to its own probability vector, and resends the resulting vector back to the
worker. Meanwhile, other worker processors can continue doing their job non-
stop, even though some of them are working with a slightly outdated vector.
Each worker processor can start and finish at any given point in time making
the whole system fault tolerant. When a worker starts, it receives a copy of the
manager’s probability vector, which already contains the accumulated results of
the other cGA workers. On the other hand, when a worker quits, we simply loose
a maximum of m function evaluations, which is not a big problem.
We have conducted computer simulations to validate the proposed approach
and observed a linear speedup with a growing number of processors (see Fig-
ure 1). Additional details of the simulations and a longer description of this work
can be found elsewhere [3].
7 6
10 10
m=8 m=8
m = 80 m = 80
m = 800 5 m = 800
m = 8000 10
m = 8000
communication steps per processor
m = 80000 m = 80000
function evaluations per processor
6
10 4
10
3
10
5
10
2
10
1
4
10
10
0
10
3 −1
10 10
1 2 4 8 16 32 64 128 256 512 1024 1 2 4 8 16 32 64 128 256 512 1024
number of processors number of processors
Fig. 1. On the left, we see the average number of function evaluations per processor.
On the right, we see the average number of communication steps per processor.
Acknowledgements This work was sponsored by FCT/MCES under grants
POSI/SRI/42065/2001 and POCTI/MGS/37970/2001.
References
1. Cantú-Paz, E.: Efficient and accurate parallel genetic algorithms. Kluwer Academic
Publishers, Boston, MA (2000)
2. Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE
Transactions on Evolutionary Computation 3 (1999) 287–297
3. Lobo, F.G., Lima, C.F., Mártires, H.: An architecture for massive parallelization of
the compact genetic algorithm. arXiv Report cs.NE/0402049 (2004) (Available at
http://arxiv.org/abs/cs.NE/0402049).
References (3)
- Cantú-Paz, E.: Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers, Boston, MA (2000)
- Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE Transactions on Evolutionary Computation 3 (1999) 287-297
- Lobo, F.G., Lima, C.F., Mártires, H.: An architecture for massive parallelization of the compact genetic algorithm. arXiv Report cs.NE/0402049 (2004) (Available at http://arxiv.org/abs/cs.NE/0402049).