Pontifícia Universidade Católica do Paraná
Curso de Especialização em Inteligência Computacional
2004/2005
Computação Evolutiva:
Programação Genética
Luiz Eduardo S. Oliveira, Ph.D.
[email protected]
http://www.ppgia.pucpr.br/~soares
Objetivos

Introduzir os principais conceitos da
programação genética (PG).
Introdução

As três áreas da computação evolutiva
que vimos até agora envolveram
estruturas definidas com strings.
 Binárias
 Reais

PG evolui programas de computador os
quais são representados através de
árvores de sintaxe abstrata.
Introdução

Principais diferenças entre AG e PG:
 Os
membros da população são estruturas
executáveis e não strings.
 A fitness dos indivíduos são conseguidas através da
execução dessas estruturas.

Objetivo
 Aprendizagem
por indução
 Ensinar os computadores a se auto programarem
 Estratégia: Criar-testar-modificar (similar aos
humanos).
Introdução
Representação

Árvore de sintaxe abstrata
 Funções
aparecem nos nós internos e
constantes e variáveis nos nas folhas
3*(x+6)
Implementação

A implementação consiste em:
 Determinar
o conjunto de nós terminais.
 Determinar o conjunto de funções válidas.
 Determinar a medida de fitness.
 Selecionar os parâmetros de controle.
 Determinar as condições de parada.
Implementação

As funções são limitadas pela linguagem
de programação utilizada na construção
dos programas, como por exemplo:
 Funções
matemáticas: seno, cosseno, etc..
 Funções aritméticas: +,-, *, /
 Operadores Booleanos (E, OU, NÃO)
 Operadores condicionais: Se, Então
Implementação
Cada função tem uma determinada
aridade (número de argumentos).
 Duas propriedades desejáveis em uma
aplicação

 Fechamento
 Suficiência
Fechamento




Garantir a viabilidade de árvores de sintaxe
abstrata.
O conjunto de funções válidas deve aceitar,
como argumento, qualquer valor que possa ser
retornado por qualquer função ou terminal.
Garante que a árvore será avaliada
corretamente.
Ex: Divisão: Matematicamente não se pode
dividir um número por zero.
 Solução:
retorna 1
Divisão protegida >> Divisão por zero
Suficiência
O conjunto de funções + o conjunto de
terminais deve ser capaz de representar
uma solução para o problema.
 Deve existir alguma evidência que tais
funções e terminais resolvam o problema

 Caso
contrário, o algoritmo não convergirá.
 Todas as funções possíveis.

Espaço de busca enorme.
Principais Parâmetros
Tamanho da população
 Número máximo de gerações.
 Probabilidade de reprodução e
cruzamento.
 Tamanho máximo do indivíduo.
Profundidade da árvore.

Entendendo a PG

Algoritmo clássico:
1.
2.
3.
4.
5.
Inicializar a população inicial.
Determinar a fitness de cada indivíduo.
Realizar a reprodução de acordo com o valor da
fitness e da probabilidade de reprodução.
Realizar o cruzamento.
Voltar ao passo 2 até que uma condição de parada
seja alcançada.
Criando um indivíduo.
Definir o conjunto de funções F e
terminais T.
 Cada f  F tem associada uma aridade
superior a zero
 O conjunto T é composto pelas variáveis,
constantes e funções de aridade zero.

Criando um indivíduo

Considere por exemplo:
 F  {,,,} e T  {x,3,6}
 Ou
Espaço de
busca
é a livre
combinação
dos
elementos de
FeT
seja, o conjunto das funções válidas é o
conjunto das operações aritméticas com
aridade 2
 Os terminais são compostos por x, 3 e 6.
 Uma expressão que pode ser produzida é
3  ( x  6)
Criando uma População Aleatória




Primeiramente escolhe-se uma função aleatória
de f  F
Para cada elemento de f escolhe-se um
elemento de {F U T}
O processo segue até que se tenha apenas
terminais como nós folha da árvore.
Especifica-se um limite máximo para a
profundidade da árvore para se evitar árvores
muito grandes.
Criando uma População Aleatória

O sucesso da PG depende bastante da
qualidade da população inicial.
 Variedade
na composição dos programas
 Permitindo assim que a recombinação leve à
convergência.
Fitness
Cada programa de computador é avaliado
em termos de quão bem ele realiza (ou
executa) sua tarefa em um ambiente
particular de um problema.
 Por exemplo, executando-se o programa e
verificando-se o erro produzido no
resultado. Quanto mais próximo de zero,
melhor é o programa.

Operadores Genéticos
Reprodução
 Cruzamento
 Mutação
 Permutação
 Edição
 Encapsulamento
 Destruição

Reprodução
Um indivíduo da população é selecionado
de acordo com algum método baseado na
fitness (Roleta, por exemplo)
 O indivíduo é copiado sem qualquer
alteração para a próxima geração

Cruzamento
Dois programas são selecionados e são
recombinados para gerar outros dois
programas.
 Um ponto aleatório de cruzamento é
escolhido em cada programa pai e as
árvores abaixo destes pontos são
trocadas.

Cruzamento
Cruzamento AG X GP

Cruzamento em AG:
 Se
os pais são idênticos, ambos os filhos
serão idênticos.

Cruzamento em GP
 Como
a chance de gerar pontos de corte
idênticos é pequena, logo a probabilidade de
gerar filhos iguais é pequena.
Mutação
Seleciona-se um ramo aleatório na árvore
e cria-se um novo ramo aleatório no lugar.
 Inserir diversidade.

Permutação
Escolhe-se um ponto interno de uma
expressão
 Escolha aleatória do ramo a ser
permutado.

Permutação

Quando a permutação não tem influência
nenhuma?
 Operação
comutativa.
Edição

Proporciona um meio para editar e
simplificar expressões
Edição

Pode ser utilizada de duas maneiras
 Externo
a execução
 Durante a execução


Consome bastante tempo
Controlada por parâmetro
– Aplica-se em todas as gerações
 0 – Não é aplicada
 > 1 – Freqüência de aplicação
1
Edição

Tornar a expressão menos vulnerável ao
cruzamento
 (NOT(NOT(NOT(NOT(X)))))

X
Reduz a variedade de estruturas
disponíveis para o cruzamento.
Encapsulamento
Forma de identificar sub-árvores
potencialmente úteis e dar a elas um
nome para que sejam referenciadas e
usadas posteriormente.
 Seleciona-se um ponto interno de uma
árvore com boa fitness.

Encapsulamento
Remove-se a sub-árvore localizada no
ponto selecionado.
 Uma nova função é definida para
referenciar esta sub-arvore.

Encapsulamento
A nova função não tem argumentos.
 O conjunto das funções é acrescido desta
nova função.
 A função encapsulada é fator potencial
para interromper o efeito do cruzamento,
pois a função torna-se um ponto
indivisível.

Destruição
Operação assexuada
 Forma de reduzir o número de indivíduos
medíocres nas primeiras gerações.
 Utiliza-se a fitness para realizar esta
operação
 Utilizada em outras estratégias evolutivas
também.

Critério de Parada
Máximo de gerações ou ponto ótimo
 Designação do resultado:

 Melhor
indivíduo que apareceu em qualquer
geração da população.
Exemplo de Aplicação

Regressão
 Encontrar
uma expressão matemática que
melhor se ajuste a uma amostra de dados.
idade
Reta da regressão
y=-1.57+1.41x
Modelo que pode ser
utilizado para fazer
previsão.
Cuidado na extrapolação
dos limites da base
de aprendizagem.
tamanho
Exemplo

Encontrar o relacionamento entre o raio e
o período de órbita de um planeta em
torno do sol.

Dados fornecidos:
Exercício

Considere as duas árvores. Faça uma operação
de cruzamento e mutação e avalie a fitness com
base na tabela anterior. Compare o seu
resultado com o período fornecido.
X
X
^
d
X
X
r
r
2
r
r
d