23
Programação Genetica

Programação Genetica

  • Upload
    hollis

  • View
    40

  • Download
    0

Embed Size (px)

DESCRIPTION

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 - PowerPoint PPT Presentation

Citation preview

Page 1: Programação Genetica

Programação Genetica

Page 2: Programação Genetica

Desafio

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

• Arthur Samuel (1959)

Page 3: Programação Genetica

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)

Page 4: Programação Genetica
Page 5: Programação Genetica

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, ...

Page 6: Programação Genetica

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

Page 7: Programação Genetica
Page 8: Programação Genetica
Page 9: Programação Genetica

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.

Page 10: Programação Genetica
Page 11: Programação Genetica

Programa

Programa

Subrotinas Loops Recursão Memória

Entrada Saída

Page 12: Programação Genetica

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.

Page 13: Programação Genetica

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

Page 14: Programação Genetica

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.

Page 15: Programação Genetica

Memória

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

Page 16: Programação Genetica

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

Page 17: Programação Genetica

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

Page 18: Programação Genetica

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.

Page 19: Programação Genetica

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

Page 20: Programação Genetica

Grammar GP

• GP x Grammar GP

• S B,

• B +BB| - BB| * BB|%BB|T,

• Tx| 1

• (x – 1)2 + (x – 1)3

Page 21: Programação Genetica

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.

Page 22: Programação Genetica

Bibliografia

• http://www.smi.stanford.edu/people/koza

• http://www.genetic-programming.org

• http://www.genetic-programming.com

[email protected], Stanford University

• Others GP techniques, tutorial GECCO’2000, Koza.

Page 23: Programação Genetica

Trabalho

• CD discipulus

• Outro programa

• Papers ,Programando GP ???