Analysis of the Numerical Effects of Parallelism on a Parallel Genetic
                                        Algorithm

                                         William E. Hart
                             Massively Parallel Computing Research Laboratory
                                    Sandia National Laboratories 
                                   Albuquerque, NM 87185-1110 

                               Scott Baden, Richard K. Belew, Scott Kohn 
                              Computer Science end Engineering Department
                                  University of California - San Diego
                                       La Jolla, CA 92093

              In Proceedings of the 10th International Parallel Processing Symposium, 1996. pp. 606-612. 

Abstract: This paper 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) decreased synchronization costs and (2) high 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.