Genetic Algorithms with Punctuated Equilibria: Parallelization and Analysis

This paper describes the creation of a parallel implementation of a genetic algorithms with punctuated equilibria (GAPE) application for the travelling salesman problem (TSP). It also investigates two aspects of GAPE by using the results from the software. These aspects are the relationship between the number of populations used and the solution quality over time, and the relationship between the number of generations per epoch and the solution quality over time. The analysis of these variables is meant to shed light on their role in GAPE algorithms in general. We believe that a parallel implementation of GAPE run over a large network will provide a significant speedup over sequential implementations. Further, we feel that the results described within indicate that the number of populations have relatively little effect on the solution quality of GAPE, especially for small problem sizes, and that isolating populations for extended periods of time produces better long-term results than those obtained with frequent communication.

Thesis originally deposited on 2011-12-28 in version 1.28 of Libra. This thesis was migrated to Libra2 on 2016-11-30 15:20:02.