- author = "Tony Lewis",
- title = "Accelerating Genetic Programming Using Graphics Processing Units",
- school = "Department of Computer Science and Information Systems Birkbeck, University of London",
- year = "2011",
- address = "UK",
- keywords = "genetic algorithms, genetic programming, GPU, GPGPU, TMBL, CUDA, PTX, nVidia, Cartesian Genetic Programming, cyclic CGP, UML",
-
URL = "
http://www.dcs.bbk.ac.uk/research/recentphds.php",
-
URL = "
http://www.dcs.bbk.ac.uk/research/recentphds/tonylewis.pdf",
-
URL = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.298.5163",
- size = "241 pages",
-
abstract = "Evolution through natural selection offers the
possibility of automatically generating functionally
complex solutions to a wide range of problems. Methods
such as Genetic Programming (GP) show the promise of
this approach but tend to stagnate after relatively few
generations. To research this issue, execution speed
must be substantially improved. This thesis presents
work to accelerate the execution of such methods.
The work uses the Graphics Processing Unit (GPU) to target the evaluation of individuals since this is the most time-consuming part of the run. Two models have been emerging for this: dynamically compiling each new generation of individuals for the GPU or using a single GPU interpreter, to which successive groups of individuals can be sent.
Using the latter model, a GPU interpreter is constructed to implement cyclic GP, an advanced form of GP that imposes several challenging implementation issues which are addressed. Accelerating the evaluation using the GPU is only part of the story. The next part of the work interleaves CPU and GPU computation to keep both chips as busy as possible with the tasks to which they are best suited and then to recruit multiple GPUs and CPU cores to further accelerate the run.
Using the former model, a compiling system is constructed and this is used to investigate two methods to overcome the primary difficulty with the approach: long compilation times. That system implements Tweaking Mutation Behaviour Learning (TMBL), a form focused on long term fitness growth and overcoming the previously mentioned stagnation issues. Further work optimises two CPU tasks highlighted by profiling: tournament selection and individual copying.
These techniques are highly effective and permit much shorter run-times. This clears the way for research into stimulating long term fitness growth and hence for tackling new, complex problems.",
- notes = "supervisor, George Magoulas",
