Massively Parallel Genetic Programming on GPUs

Created by W.Langdon from gp-bibliography.bib Revision:1.8129

@PhdThesis{daSilva:thesis,

• author = "Cleomar Pereira {da Silva}",
• title = "Programacao Genetica Macicamente Paralela em {GPUs}",
• title = "Massively Parallel Genetic Programming on {GPUs}",
• school = "Departamento de Engenharia Eletrica do Centro Tecnico Cientifico da Pontificia Universidade Catolica do Rio de Janeiro",
• year = "2014",
• address = "Brazil",
• month = "11 " # sep,
• keywords = "genetic algorithms, genetic programming, GPU, quantum inspired, graphics processing units, machine code, QILGP, CUBIN",
• URL = "http://doi.org/10.17771/PUCRio.acad.24129",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_1.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_2.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_3.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_4.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_5.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_6.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_7.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_8.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_9.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_10.PDF",
• URL = "http://www.maxwell.vrac.puc-rio.br/24129/24129_11.PDF",
• size = "134 pages",
• abstract = "Genetic Programming enables computers to solve problems automatically, without being programmed to it. Using the inspiration in the Darwin's Principle of natural selection, a population of programs or individuals is maintained, modified based on genetic variation, and evaluated according to a fitness function. Genetic programming has been successfully applied to many different applications such as automatic design, pattern recognition, robotic control, data mining and image analysis. However, the evaluation of the huge amount of individuals requires excessive computational demands, leading to extremely long computational times for large size problems. This work exploits the high computational power of graphics processing units, or GPUs, to accelerate genetic programming and to enable the automatic generation of programs for large problems. We propose two new methodologies to exploit the power of the GPU in genetic programming: intermediate language compilation and individuals creation in machine language. These methodologies have advantages over traditional methods used in the literature. The use of an intermediate language reduces the compilation steps, and works with instructions that are well-documented. The individuals creation in machine language has no compilation step, but requires reverse engineering of the instructions that are not documented at this level. Our methodologies are based on linear genetic programming and are inspired by quantum computing. The use of quantum computing allows rapid convergence, global search capability and inclusion of individuals' past history. The proposed methodologies were compared against existing methodologies and they showed considerable performance gains. It was observed a maximum performance of 2,74 trillion GPops (genetic programming operations per second) for the 20-bit Multiplexer benchmark, and it was possible to extend genetic programming for problems that have databases with up to 7 million samples.",
• abstract = "A Programacao Genetica permite que computadores resolvam problemas automaticamente, sem que eles tenham sido programados para tal. Utilizando a inspiracao no principio da selecao natural de Darwin, uma populacao de programas, ou individuos, e mantida, modificada baseada em variacao genetica, e avaliada de acordo com uma funcao de aptidao (fitness). A programacao genetica tem sido usada com sucesso por uma serie de aplicacoes como projeto automatico, reconhecimento de padroes, controle robotico, mineracao de dados e analise de imagens. Porem, a avaliacao da gigantesca quantidade de individuos gerados requer excessiva quantidade de computacao, levando a um tempo de execucao inviavel para problemas grandes. Este trabalho explora o alto poder computacional de unidades de processamento grafico, ou GPUs, para acelerar a programacao genetica e permitir a geracao automatica de programas para grandes problemas. Propomos duas novas metodologias para se explorar a GPU em programacao genetica: compilacao em linguagem intermediaria e a criacao de individuos em codigo de maquina. Estas metodologias apresentam vantagens em relacao as metodologias tradicionais usadas na literatura. A utilizacao de linguagem intermediaria reduz etapas de compilacao e trabalha com instrucoes que estao bem documentadas. A criacao de individuos em codigo de maquina nao possui nenhuma etapa de compilacao, mas requer engenharia reversa das instrucoes que nao estao documentadas neste nivel. Nossas metodologias sao baseadas em programacao genetica linear e inspiradas em computacao quantica. O uso de computacao quantica permite uma convergencia rapida, capacidade de busca global e inclusao da historia passada dos individuos. As metodologias propostas foram comparadas com as metodologias existentes e apresentaram ganhos consideraveis de desempenho. Foi observado um desempenho maximo de ate 2,74 trilhoes de GPops (operacoes de programacao genetica por segundo) para o benchmark Multiplexador de 20 bits e foi possivel estender a programacao genetica para problemas que apresentam bases de dados de ate 7 milhoes de amostras.",
• notes = "In Portuguese.

  2740000 MGPOPs Supervisor: Marco Aurelio Cavalcanti Pacheco, Co-Orientador: Douglas Mota Dias, Co-Orientador: Cristiana Barbosa Bentes",

}

Genetic Programming entries for Cleomar Pereira da Silva

Citations