[pt] A Programação Genética permite que computadores resolvam problemas
automaticamente, sem que eles tenham sido programados para tal. Utilizando
a inspiração no princípio da seleção natural de Darwin, uma população
de programas, ou indivíduos, é mantida, modificada baseada em variação
genética, e avaliada de acordo com uma função de aptidão (fitness). A
programação genética tem sido usada com sucesso por uma série de aplicações
como projeto automático, reconhecimento de padrões, controle robótico,
mineração de dados e análise de imagens. Porém, a avaliação da gigantesca
quantidade de indivíduos gerados requer excessiva quantidade de computação,
levando a um tempo de execução inviável para problemas grandes. Este
trabalho explora o alto poder computacional de unidades de processamento
gráfico, ou GPUs, para acelerar a programação genética e permitir a geração
automática de programas para grandes problemas. Propomos duas novas
metodologias para se explorar a GPU em programação genética: compilação em
linguagem intermediária e a criação de indivíduos em código de máquina. Estas
metodologias apresentam vantagens em relação às metodologias tradicionais
usadas na literatura. A utilização de linguagem intermediária reduz etapas de
compilação e trabalha com instruções que estão bem documentadas. A criação
de indivíduos em código de máquina não possui nenhuma etapa de compilação,
mas requer engenharia reversa das instruções que não estão documentadas
neste nível. Nossas metodologias são baseadas em programação genética
linear e inspiradas em computação quântica. O uso de computação quântica
permite uma convergência rápida, capacidade de busca global e inclusão da
história passada dos indivíduos. As metodologias propostas foram comparadas
com as metodologias existentes e apresentaram ganhos consideráveis de
desempenho. Foi observado um desempenho máximo de até 2,74 trilhões de
GPops (operações de programação genética por segundo) para o benchmark
Multiplexador de 20 bits e foi possível estender a programação genética para
problemas que apresentam bases de dados de até 7 milhões de amostras. / [en] 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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:24129 |
| Date | 25 February 2015 |
| Creators | CLEOMAR PEREIRA DA SILVA |
| Contributors | MARCO AURELIO CAVALCANTI PACHECO, MARCO AURELIO CAVALCANTI PACHECO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0021 seconds