Document Type
Report
Date
9-1991
Keywords
Data allocation, data partitioning, load balancing, loosely-synchronous algorithms, natural evolution simulation, parallel genetic algorithms, physical optimization methods, task allocation.
Language
English
Disciplines
Computer Sciences
Description/Abstract
A new coarse grain parallel genetic algorithm (PGA) and a new implementation of a data-parallel GA are presented in this paper. They are based on models of natural evolution in which the population is formed of discontinuous or continuous subpopulations. In addition to simulating natural evolution, the intrinsic parallelism in the two PGA's minimizes the possibility of premature convergence that the implementation of classic GA's often encounters. Intrinsic parallelism also allows the evolution of fit genotypes in a smaller number of generations in the PGA's than in sequential GA's, leading to superlinear speed-ups. The PGA's have been implemented on a hypercube and a Connection Machine, and their operation is demonstrated by applying them to the load balancing problem in parallel computing. The PGA's have found near-optimal solutions which are comparable to the solutions of a simulated annealing algorithm and are better than those produced by a sequential GA and by other load balancing methods. On one hand, The PGA's accentuate the advantage of parallel computers for simulating natural evolution. On the other hand, they represent new techniques for load balancing parallel computations.
Recommended Citation
Mansouri, N. and Fox, Geoffrey C., "Parallel Genetic Algorithms with Application to Load Balancing for Parallel Computing" (1991). Electrical Engineering and Computer Science - Technical Reports. 128.
https://surface.syr.edu/eecs_techreports/128
Source
local
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-48