Pontifícia Universidade Católica do Paraná
Curso de Especialização em Inteligência Computacional
2004/2005
Computação Evolutiva:
Programação Evolutiva
Luiz Eduardo S. Oliveira, Ph.D.
[email protected]
http://www.ppgia.pucpr.br/~soares
PUCPR (2005)
Computação Evolutiva
1
Introdução

A Programação Evolutiva (PE) foi
proposta por Fogel, Owens e Walsh em
meados da década de 60
 “Artificial
Intelligence Through Simulated
Evolution”
 Proposta original:
Predição de comportamento de máquinas de
estado finito.
 Predição

PUCPR (2005)
Computação Evolutiva
2
Introdução
Procedure EC{
Não existe cruzamento,
t = 0;
somente mutação
Initialize P(t);
Evaluate P(t);
While (Not Done)
{
Parents(t) = Select_Parents(P(t));
Offspring(t) = Procreate(Parents(t));
Evaluate(Offspring(t));
P(t+1)= Select_Survivors(P(t),Offspring(t));
t = t + 1;
}
PUCPR (2005)
Computação Evolutiva
3
Introdução
Na PE, cada indivíduo gera um único
descendente através de mutação.
 A melhor metade da população
ascendente e a melhor metade da
população descendente são reunidas
para formar a nova geração

PUCPR (2005)
Computação Evolutiva
4
Introdução

Diferentemente dos AGs, a PE enfatiza os
desenvolvimento de modelos
comportamentais
 Modelar
o comportamento afim de prever o
que pode acontecer (PREDIÇÃO).
 Capturar a interação do sistema com seu
ambiente.
PUCPR (2005)
Computação Evolutiva
5
Maquinas de Estado Finito
Uma maneira comum de se prever uma
ação consiste na análise de ações
passadas.
 No contexto de uma máquina de estado
finito, cada ação pode ser representada
por um símbolo.

 Dado
uma seqüência de símbolos, deve-se
prever qual será o próximo símbolo.
PUCPR (2005)
Computação Evolutiva
6
Máquinas de Estado Finito
Assim como nos AGs, os símbolos devem
pertencer a um alfabeto finito.
 Máquina de Estado Finito:

 Analisar
a seqüência de símbolos
 Gerar uma saída que otimize uma dada
função de fitness, a qual envolve a previsão
do próximo símbolo da seqüência.

PUCPR (2005)
Mercado financeiro, previsão do tempo, etc...
Computação Evolutiva
7
Máquinas de Estado Finito

Podem ser vistas como transdutores:
 Quando
estimulado por um alfabeto finito de
símbolos, responde com um outro alfabeto
finito de símbolos e possui um número finito
de estados.
 Alfabetos de entrada e saída não são
necessariamente idênticos.
PUCPR (2005)
Computação Evolutiva
8
Máquinas de Estado Finito:
Um Exemplo
Alfabeto de entrada de dois símbolos:
I = {1, 0}
Alfabeto de saída de três símbolos:
O = {X, Y, Z}
Máquina de três estados
S = {A, B, C}
PUCPR (2005)
Computação Evolutiva
9
Máquinas de Estado Finito

Sub-conjunto das máquinas de Turing
 Capazes
de resolver todos os problemas
matemáticos de uma classe definida.

Capazes de modelar ou representar um
organismo ou um sistema.
PUCPR (2005)
Computação Evolutiva
10
Máquinas de Estado Finito
Tarefa: Prever a próxima entrada

Medida da Qualidade:



Estado Inical: C
Sequência de Entrada


011101
Sequência de Saida


Número de previsões corretas
110111
Qualidade: 3 de 5
S = {A,B,C} I = {0,1} O = {0,1}
PUCPR (2005)
Computação Evolutiva
11
Operados usados na PE
Diferentemente dos AGs onde o
cruzamento é um importante componente
para a produção de uma nova geração, a
mutação é o ÚNICO operador usado na
PE.
 Cada membro da população sobre
mutação e produz UM filho.

PUCPR (2005)
Computação Evolutiva
12
Mutação

Cinco tipos de mutação podem ocorrer em uma
máquina de estado finitos:
O
estado inicial pode mudar.
 O estado inicial pode ser eliminado.
 Um estado pode ser adicionado.
 Uma transição entre estados pode ser mudada.
 O símbolo de saída para um determinado estado e
símbolo de entrada pode ser mudado.
PUCPR (2005)
Computação Evolutiva
13
Seleção
Uma vez que cada pai gera um filho após
a mutação, a população dobra de
tamanho a cada geração.
 Após o cálculo da fitness, conserva-se a
melhor metade dos pais e a melhor
metade dos filhos.

 População
PUCPR (2005)
de tamanho constante.
Computação Evolutiva
14
Seleção
Pais
Filhos
Nova
População
Mutação
Ranking
PUCPR (2005)
Computação Evolutiva
15
Critério de Parada

Fazer a predição utilizando o melhor
indivíduo da população.
 Isso
pode ocorrer a qualquer instante
 Se a fitness for satisfatória (Lei da
Suficiência) o algoritmo pode ser terminado.
 Fixar um número de gerações.
PUCPR (2005)
Computação Evolutiva
16
Alterando o Tamanho do Indivíduo

Diferentemente de outros paradigmas
evolutivos, na PE a mutação pode mudar
o tamanho do indivíduo.
 Estados
podem ser adicionados ou
eliminados, de acordo com as regras vistas
anteriormente.
 Isso pode causar alguns espaços na tabela

PUCPR (2005)
Mutações neutras.
Computação Evolutiva
17
Alterando o Tamanho do Indivíduo
A mutação ainda pode criar uma transição
que não seja possível, pois um estado
pode ter sido eliminado durante a
mutação.
 Esses problemas devem ser identificados
e corrigidos durante a implementação
 Menos freqüentes em máquina com
bastante estados.

PUCPR (2005)
Computação Evolutiva
18
PE com Indivíduos de Tamanho
Fixo

Embora PE possa ter indivíduos de tamanho
variável, é possível evoluir uma máquina de
estado finitos com PE onde os indivíduos tem
tamanho fixo.
 Definir

um número máximo de estados.
Para exemplificar, vamos considerar a máquina
de predição apresentada anteriormente, a qual
pode ter no máximo 4 estados.
PUCPR (2005)
Computação Evolutiva
19
Exemplo
Cada estado pode ser representado por 7 bits
A
Bit No.
Representação
0
1 ativo; 0 não ativo
1
símbolo de entrada
2
símbolo de entrada
3
símbolo de saída
4
símbolo de saída
5
estado de saída
6
estado de saída
B
C
D
11011AB10101BC11001AB00000DA
PUCPR (2005)
Computação Evolutiva
20
Exemplo

Como visto,cada estado pode ser
representado por uma string de 7 bits.
A
B
C
D
11011AB10101BC11001AB00000DA

Sendo assim, cada indivíduo possui 28
bits
 Cada
PUCPR (2005)
um representa uma máquina completa.
Computação Evolutiva
21
Exemplo II

Máquina de estado finito para jogar o
Dilema do Prisioneiro.
O
prisioneiro tem que tomar uma decisão em
face da decisão do outro.
 Questão de altruísmo ou egoísmo.
PUCPR (2005)
Computação Evolutiva
22
Dilema do Prisioneiro

Dois comparsas são pegos cometendo um
crime. Levados à delegacia e colocados em
salas separadas, lhes é colocada a seguinte
situação com as respectivas opções de decisão:
 Se
ambos ficarem quietos, cada um deles pode ser
condenado a um mês de prisão.
 Se apenas um acusa o outro, o acusador sai livre. O
outro, condenado em 1 ano.
 Se os dois se acusarem, ambos pegam seis meses.
PUCPR (2005)
Computação Evolutiva
23
Dilema do Prisioneiro
As decisões são simultâneas e um não
sabe nada sobre a decisão do outro.
 Esse jogo mostra que, em cada decisão, o
prisioneiro pode satisfazer seu próprio
interesse (desertar) ou atender ao
interesse do grupo (cooperar).

PUCPR (2005)
Computação Evolutiva
24
Dilema do Prisioneiro

Dilema
 Admito
inicialmente que meu colega planeja
cooperar. Se eu cooperar também ambos pegamos 1
mês (nada mau)
 Supondo a cooperação do meu colega, eu posso
acusá-lo e sair livre (melhor situação)
 Porém se eu coopero e ele me acusa, eu pego 1 ano!
 Se eu acusar também, aí eu fico seis meses.

Logo, ele cooperando ou não o melhor a fazer é
desertar!
PUCPR (2005)
Computação Evolutiva
25
Dilema do Prisioneiro



O problema é que seu colega pensa da mesma
maneira, e ambos desertam.
Se ambos cooperassem, haveria um ganho
maior para ambos, mas na otimização dos
resultados não é o que acontece.
Ao invés de ficar um mês presos, ambos ficam 6
meses para evitar o risco de ficar 1 ano.
PUCPR (2005)
Computação Evolutiva
26
Dilema do Prisioneiro




A repetição do jogo, entretanto, muda
radicalmente a forma de pensar.
Dois comparsas de longa data terão uma
tendência muito maior à cooperação.
Com isso formam-se outras opções de
estratégias.
A teoria dos jogos (John Nash) é bastante
utilizada na economia para descrever e prever o
comportamento econômico.
PUCPR (2005)
Computação Evolutiva
27
Máquina de estado finito para o
dilema do prisioneiro [Fogel 95]
Por exemplo:
O rótulo C,D/C na flexa que vai de
um estado X para um estado Y
significa que o sistema está no
estado X e no movimento anterior
a máquina cooperou e o oponente
desertou. Então coopere e vá para
o estado Y.
PUCPR (2005)
C – Cooperar
D Evolutiva
– Desertar
Computação
28
Exercício

Evolua a máquina de estados finitos vista
anteriormente
 Considerar
4 estados no máximo.
 Utilizar a codificação vista anteriormente.
 Considerar 5 indivíduos de 28 bits
 Considerar que somente os indivíduos que tenham
pelo menos dois estados ativos sejam admitidos na
população inicial.
 Para cada indivíduo, construa a máquina e calcule a
qualidade da predição.
PUCPR (2005)
Computação Evolutiva
29
Realizando a Mutação

Para cada indivíduo, gere um número aleatório
entre 0 e 1. Escolha um gene aleatoriamente e
tome uma das seguintes ações.
Valor
PUCPR (2005)
Ação
0.0 – 0.2
0.2 – 0.4
0.4 – 0.6
0.6 – 0.8
Eliminar estado
Mude o estado inicial
Mude o símbolo de entrada
Mude o símbolo de saída
0.8 – 0.1
Ativar estado
Computação Evolutiva
30
Nova População

Avaliar a fitness e manter os melhores
50%, resultando assim uma nova
população do tamanho da inicial.
PUCPR (2005)
Computação Evolutiva
31