A convergence model for asynchronous parallel genetic algorithms

We describe and verify a convergence model that allows the islands in a parallel genetic algorithm to run at different speeds, and to simulate the effects of communication or machine failure. The model extends on present theory of parallel genetic algorithms and furthermore it provides insight into the design of asynchronous parallel genetic algorithms that work efficiently on volatile and heterogeneous networks, such as cycle-stealing applications working over the Internet. The model is adequate for comparing migration parameter settings in terms of convergence and fault tolerance, and a series of experiments show how the convergence is affected by varying the failure rate and the migration topology, migration rate, and migration interval. Experiments conducted show that while very sparse topologies are inefficient and failure-prone, even small increases in topology order result in more robust models with convergence rates that approach the ones found in fully-connected topologies.