GPU: The Paradigm of Parallel Power for Evolutionary Computation

GPU: The Paradigm of Parallel Power for Evolutionary Computation
Ka-Ling Fok

Evolutionary Algorithm (EAs) are inspired by a biological phenomenon: Darwin's theory of evolution. They are effective and robust methods for solving many practical problems such as feature selections, electrical circuit synthesis, and data mining. However, they may take a very long time to find the solutions especially when the problems are large in scale and difficult. This is due to the numerous fitness evaluations and complicated evolutionary operations involved. A promising approach to overcome this limitation is to parallelize these algorithms. In this thesis, we propose a paradigm to implement parallel EAs including Evolutionary Programming (EP), Genetic Algorithm (GA), and Multi-Objective Genetic Algorithm (MOGA) on consumer-level graphics cards. New data structures, as well as novel algorithms, are introduced. We performed intensive experiments to compare our parallel EAs with an ordinary one and demonstrated that our approach is much more effective. The experimental results show that our approach achieves a significant speed-up up to a factor of five. We are the pioneer of using consumer-level graphics cards for Evolutionary Computation. We believe that this thesis provides a guideline for the general scientific computation using graphics processing unit (GPU) by identifying the features and limitations of this newly arising parallel hardware.