Programação Genetica

Desafio

• Como os computadores podem aprender a resolver problemas sem ser explicitamente programados??

• Arthur Samuel (1959)

Programação Automatica

• Indução de programas, Sintesis de programas– Descoberta no espaço de possiveis programas,

de um programa de computador que produza a saida que satisfaça o objetivo do problema.

– Se estamos interessados em que computadores resolvam problemas sem ter sido explicitamente programados para tal, a estrutura deve ser um programa (Koza)

Programa

• Parse tree, Program tree• Representação natural, a maoria dos compiladores

traduzem o programa para o parse tree.• Funções e terminais: alfabeto do programa a ser

inducido.• Conjunto de terminais: variaveis e constantes do

programa.• Funções: soma, substração, divisão, ...

Exemplo de criação de programa

• Terminais: T={A,B,C}• Funções: F={+,*,

%,If,Lte}• Começe com + e 2arg• Continue com * e 2arg• Complete com terminais

A,B,C• O resultado é um prog.

Executavel, Closed

+

+

*

+

*

A B

C

Mutuação

• 2 tipos de mutuações são possiveis• Uma função pode substituir uma função ou

um terminal pode substituir outro;• Um subtree pode ser substituido o novo

subtree é gerado aleatoriamente ao igual que a população inicial.

Programa

Programa

Subrotinas Loops Recursão Memória

Entrada Saída

Funções definidas (ADFs)

• Na geração 0, cria-se uma população de programas– Programa principal (RPB)– 1 ou mais funções (ADFs)

• Diferentes ingredientes• O conjunto de terminais de ADFs

– Argumentos mudos ARG0, ARG1• O conjunto de funções de RPB contem ADF0,..• ADFs são privadas e associadas com programas

específicos.

ADFs cont.

• O programa inteiro é executado e avaliado • Operação de reprodução se mantem• Mutuação

– RPB ou ADFs são mudados a partir de um ponto e um novo subtree é gerado.

• Crossover– RPB ou ADFs como pais, pais e filhos do

mesmo tipo

Obs. Sobre ADFs

• ADFs funciona• ADFs produz resultados diferentes que

humanos• O tamanho do programa cresce menos• Eforço computacional diminue• Outras abordagens, modulos Angeline,

1992.

Memória

• Estruturas de dados (Langdon)– Stacks– Filas– Listas– Aneis

Programação Genetica Fortemente Tipada (STGP)

• Limitações de GP: propriedades de closure das funções

• STGP: as variaveis, constantes, argumentos e valores retornados podem ser de qq tipo, desde que definidos pelo usuario

STGP

• Geração da população inicial: deve concordar com as restrições de tipo

• Operador de crossover deve ocorrer entre funções e terminais do mesmo tipo.

• Montana, 1995

Grammar based GP

• Whigham, 1995• Gramaticas livres de contexto como

estrutura de evolução • Não possue os problemas de “closure” de

GP tradicionais• The central role of a function possessing

arguments is taken over by a production rule generating new symbols.

G=(S,,N,P)

• S simbolo inicial, conjunto de simbolos terminais e P o conjunto de regras de produção, S é o conjunto de simbolos não terminais

• Uma regra de produção é uma substituição do tipo X Y onde X N e Y N

Grammar GP

• GP x Grammar GP• S B,• B +BB| - BB| * BB|%BB|T, • Tx| 1• (x – 1)2 + (x – 1)3

Operadores em GGP

• Closure é assegurado• Buscando no pai um nó não terminal do tree e na

mãe o mesmo nó não terminal.• Mutuação envolve selecionar um nó não-terminal

e aplicar uma produção selecionada randomicamente até a profundidade máxima da árvore seja alcançada.

• Wong e Leung introduzem context-sensitive grammars.

Bibliografia

• http://www.smi.stanford.edu/people/koza• http://www.genetic-programming.org• http://www.genetic-programming.com• koza@stanford.edu, Stanford University• Others GP techniques, tutorial

GECCO’2000, Koza.

Trabalho

• CD discipulus• Outro programa• Papers ,Programando GP ???