Programação genética e algoritmos de estimação de distribuição

Abstract

Resumo: Esse trabalho desenvolve um estudo sobre a Programação Genética e os Algoritmos de Estimação de Distribuição, visando integrar os beneficios de ambas as técnicas. Como resultado desse estudo, foi proposta a Programação Automática Bayesiana (PAB). A PAB é uma ferramenta para a programação automática que usa uma gramática livre de contexto e uma distribuição de probabilidade estimada de um conjunto de soluções promissoras para guiar uma busca por uma solução ótima para um problema. Uma rede Bayesiana é usada para modelar a estimação de distribuição de probabilidade. De modo a manter a diversidade populacional, uma operação genética que usa um conceito de similaridade entre um indivíduo e a população como critério de ativação é também proposta. Para validar a ferramenta, ela foi aplicada em três problemas, e seu desempenho comparado com a Programação Genética tradicional.

Abstract: This work develops a study on Genetic Programming and Estimation Distribution Algorithm aiming to profit from both technics. As result of this study, it has been proposed the Bayesian Automatic Programming (BAP). BAP is an automatic programming technic which employs a context free grammar and a probability distribution of a set of promising solutions to guide a search for an optimal solution for a problem. This probability distribution estimated is modeled through a Bayesian network.To keep the population diversity, it has been proposed a genetic operation employing a metric of similarity between an individual and a population, as criteria of activation. To validate the tool, it has been applied to tree problems and its performance compared with the performance of the traditional Genetic Programming.