O Problema

A Programação Genética (GP) é um ramo da computação evolutiva. A grande diferença entre algoritmos genéticos e GP é ao nível da representação. Em GP os indivíduos são programas, pelo que o objectivo é evoluir programas que resolvam um determinado problema. Para avaliarmos a qualidade de um indivíduo (programa) teremos que o executar. A GP é uma tarefa computacionalmente pesada. Na grande maioria das aplicações a maior parte do tempo é gasta na execução dos indivíduos. Assim é desejável que este passo seja tão eficiente quanto possível.

Em GP standard os indivíduos são representados através de árvores. Ex:

Para avaliar a árvore teremos que a percorrer (através duma função recursiva) e chamar as funções correspondentes a cada nó. A maioria dos nós envolve funções muito simples que podem ser avaliadas através duma única instrução em código. A maioria do tempo é gasta em passagem de argumentos e chamadas a funções!

A Solução

Existem, neste momento, várias soluções para colmatar este problema. Em 1994, Nordin & Banzhaf propuseram que se evoluíssem, "directamente", os programas em código de máquina, o que proporciona aumentos de velocidade de cerca de 100 vezes. Apesar da eficiência desta abordagem, ela obriga o programador a escrever em código de máquina todas as primitivas para os nós, desenvolver operadores de mutação e recombinação específicos, alterar a representação standard, etc. Em 1998, Alex Fukunaga propôs a utilização de um Compilador de Genótipos. Um Compilador de genotipos percorre a árvore correspondente a cada indivíduo traduzindo-a para código de maquina. Esse código é executado aquando da avaliação do indivíduo. Os testes experimentais mostram que: a) A performance do compilador de genótipos é comparável à dos sistemas alternativos mais rápidos. b) O tempo adicional necessário para compilar os indivíduos é negligenciável!