O objectivo último deste projecto é construir um Compilador de Genomas (GC) para Programação Genética (PG), e testar a sua performance num conjunto de tarefas.

A PG insere-se no paradigma da Computação Evolutiva, caracterizando-se pelo facto de os indivíduos serem programas. Os indivíduos assumem geralmente a forma de árvores, construídas a partir dum conjunto de funções (f-set) e terminais.

A maioria dos sistemas de PG são implementados em Lisp ou C. As implementações C são cerca de 25 vezes mais rápidas, sendo actualmente as mais populares.

A aplicabilidade da PG a problemas complexos depende da velocidade do algoritmo. Cerca de 99% do tempo é gasto na avaliação dos indivíduos [Nordin, 94]. O problema agrava-se quando estes têm que ser avaliados para um conjunto de casos de fitness.

A avaliação implica percorrer a árvore e chamar, para cada nó, a função apropriada. Usualmente, as operações correspondentes aos nós podem ser implementadas através dum pequeno conjunto de instruções em código de máquina. A maior parte do tempo é gasta em pushs, pops e chamada de funções.

Nordin [94] evita este problema através da evolução directa de programas em código de máquina. Este sistema é, em média, 60 vezes mais rápido do que implementações C standard.

Outra alternativa é compilar os indivíduos online e executar o código resultante, i.e construir um GC. Este tipo de sistema é cerca de 50 vezes mais rápido do que uma implementação em C [Fukunaga, 98].

A principal vantagem relativamente à abordagem de Nordin [94] é a facilidade de implementação pois basta alterar a etapa de interpretação duma das shells de PG já existentes pela de compilação e execução; No entanto só é eficaz quando os indivíduos são avaliados para vários casos de fitness.

Ambas as abordagens possuem a seguinte deficiência: Quando o f-set inclui funções de execução demorada, o incremento de velocidade degrada-se significativamente [Machado, 99]. Adicionalmente, o sistema de Nordin [94] é de difícil configuração, a alteração do f-set obriga, por norma, ao recurso a programação em assembly.

A abordagem aqui proposta pode ser vista como uma extensão dos GC’s actuais, pretendendo-se minimizar a deficiência anteriormente indicada através das seguinte técnicas:

Optimização do código dos indivíduos — Incorporar técnicas de optimização já conhecidas, adaptando-as às particularidades da PG e ao facto da compilação ser feita online.

Detecção e Remoção de introns — A número de introns cresce exponencialmente [Nordin, 94]. Estes nós podem ser desprezados sem que tal afecte os resultados da execução.

T-functions — Apresentada pelos autores desta proposta [Machado, 99] é aplicável quando os indivíduos são avaliados para vários casos de fitness.

Caching de sub-árvores — Apresentada em Machado [99], é útil quando são utilizadas primitivas complexas.

A utilização conjunta destas duas ultimas técnicas permitiu tornar uma abordagem C convencional 15 vezes mais rápida [Machado, 99].

Pretende-se ainda manter a facilidade de utilização, o f-set deverá poder ser facilmente alterado.

O sistema será testado em vários domínios, por forma a determinar as suas vantagens e desvantagens relativamente a outras abordagens.

Numa fase posterior será aplicado em situações concretas (ver ligações a outros projectos), e passará a ser o motor de, pelo menos, uma aplicação — o NEvAr, [Amilcar, 00].

Este projecto serve, assim, dois propósitos:

a) É, per si, um campo interessante de investigação.

b) Os ganhos de performance possibilitam a aplicação de PG a áreas que usualmente estavam vedadas devido a falta de poder computacional.