Analysis of the numerical effects of parallelism on a parallel genetic algorithm

Author

Hart, William E. ; Baden, Scott ; Belew, Richard K. ; Kohn, Scott

Author_Institution

Sandia Nat. Labs., Albuquerque, NM, USA

fYear

1996

fDate

15-19 Apr 1996

Firstpage

606

Lastpage

612

Abstract

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

Keywords

genetic algorithms; numerical analysis; parallel algorithms; software performance evaluation; synchronisation; asynchronous versions; coarse-grain geographically structured parallel genetic algorithm; function evaluations; numerical effects; numerical efficiency; parallel efficiency; parallel performance measures; parallelism; relaxed synchronization; run-time; synchronization costs; Algorithm design and analysis; Chemistry; Computer science; Cost function; Genetic algorithms; Hardware; Parallel processing; Performance analysis; Runtime; Stochastic processes; Time measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International

Conference_Location

Honolulu, HI

Print_ISBN

0-8186-7255-2

Type

conf

DOI

10.1109/IPPS.1996.508119

Filename

508119