| For single-population (“panmictic”) distributed GAs, it is recognized that end-of-generation synchronization effects reduce the efficiency of task distribution. Non-synchronous multi-population methods that address this problem do not provide a satisfactory solution, particularly for heterogeneous distributed computing systems.; The hypothesis of this dissertation is “Task migration is an effective method of load balancing in panmictic distributed genetic algorithms on heterogeneous computing systems with unknown fitness evaluation runtimes.” Task migration is a technique wherein tasks that are assigned to one processor are moved dynamically to another that can better handle the load. For the end-of-generation problem, this approach involves moving tasks away from slower processors as faster processors become idle.; To prove the hypothesis, an algorithm and software system is presented that implements the task-migrating distributed genetic algorithm. The problem domain selected for this research for optimization by the distributed genetic algorithm is artificial neural network architecture selection. This software, along with a task-replicating version to provide statistical control, is tested on multiple distributed computing systems. A diverse set of parametric variations provides a set of over three hundred timings for comparison. The results show that the task-migrating algorithm effectively addresses the end-of-generation synchronization problem. A statistical analysis shows that the task-migrating approach outperforms the alternate task-replicating approach, and allows the dissertation hypothesis to be accepted. |
