PUCPR (2005) Computação Evolutiva 1
Pontifícia Universidade Católica do ParanáCurso de Especialização em Inteligência
Computacional 2004/2005
Luiz Eduardo S. Oliveira, [email protected]://www.ppgia.pucpr.br/~soares
Computação Evolutiva: Programação Evolutiva
Computação Evolutiva 2PUCPR (2005)
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
Computação Evolutiva 3PUCPR (2005)
Introdução
Procedure EC{ t = 0; 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;
}
Não existe cruzamento,somente mutação
Computação Evolutiva 4PUCPR (2005)
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
Computação Evolutiva 5PUCPR (2005)
Introdução
Diferentemente dos AGs, a PE enfatiza os desenvolvimento de modelos comportamentaisModelar o comportamento afim de prever o
que pode acontecer (PREDIÇÃO).Capturar a interação do sistema com seu
ambiente.
Computação Evolutiva 6PUCPR (2005)
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.
Computação Evolutiva 7PUCPR (2005)
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ímbolosGerar 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.
Mercado financeiro, previsão do tempo, etc...
Computação Evolutiva 8PUCPR (2005)
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.
Computação Evolutiva 9PUCPR (2005)
Máquinas de Estado Finito: Um Exemplo
Máquina de três estados S = {A, B, C}
Alfabeto de entrada de dois símbolos:I = {1, 0}
Alfabeto de saída de três símbolos:O = {X, Y, Z}
Computação Evolutiva 10PUCPR (2005)
Máquinas de Estado Finito
Sub-conjunto das máquinas de TuringCapazes de resolver todos os problemas
matemáticos de uma classe definida. Capazes de modelar ou representar um
organismo ou um sistema.
Computação Evolutiva 11PUCPR (2005)
Máquinas de Estado FinitoTarefa: Prever a próxima entrada Medida da Qualidade:
Número de previsões corretas
Estado Inical: C Sequência de Entrada
011101
Sequência de Saida 110111
Qualidade: 3 de 5
S = {A,B,C} I = {0,1} O = {0,1}
Computação Evolutiva 12PUCPR (2005)
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.
Computação Evolutiva 13PUCPR (2005)
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.
Computação Evolutiva 14PUCPR (2005)
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 de tamanho constante.
Computação Evolutiva 15PUCPR (2005)
Seleção
Pais
Mutação
FilhosNova População
Ranking
Computação Evolutiva 16PUCPR (2005)
Critério de Parada
Fazer a predição utilizando o melhor indivíduo da população. Isso pode ocorrer a qualquer instanteSe a fitness for satisfatória (Lei da
Suficiência) o algoritmo pode ser terminado.Fixar um número de gerações.
Computação Evolutiva 17PUCPR (2005)
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 Mutações neutras.
Computação Evolutiva 18PUCPR (2005)
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.
Computação Evolutiva 19PUCPR (2005)
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.
Computação Evolutiva 20PUCPR (2005)
ExemploCada estado pode ser representado por 7 bits
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
1 1 0 1 1 A B 1 0 1 0 1 B C 1 1 0 0 1 A B 0 0 0 0 0 D A
A B C D
Computação Evolutiva 21PUCPR (2005)
Exemplo
Como visto,cada estado pode ser representado por uma string de 7 bits.
Sendo assim, cada indivíduo possui 28 bitsCada um representa uma máquina completa.
1 1 0 1 1 A B 1 0 1 0 1 B C 1 1 0 0 1 A B 0 0 0 0 0 D A
A B C D
Computação Evolutiva 22PUCPR (2005)
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.
Computação Evolutiva 23PUCPR (2005)
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.
Computação Evolutiva 24PUCPR (2005)
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).
Computação Evolutiva 25PUCPR (2005)
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!
Computação Evolutiva 26PUCPR (2005)
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.
Computação Evolutiva 27PUCPR (2005)
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.
Computação Evolutiva 28PUCPR (2005)
Máquina de estado finito para o dilema do prisioneiro [Fogel 95]
C – CooperarD – Desertar
Por exemplo:O rótulo C,D/C na flexa que vai deum estado X para um estado Y significa que o sistema está no estado X e no movimento anteriora máquina cooperou e o oponente desertou. Então coopere e vá parao estado Y.
Computação Evolutiva 29PUCPR (2005)
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.
Computação Evolutiva 30PUCPR (2005)
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 Ação
0.0 – 0.2 Eliminar estado
0.2 – 0.4 Mude o estado inicial
0.4 – 0.6 Mude o símbolo de entrada
0.6 – 0.8 Mude o símbolo de saída
0.8 – 0.1 Ativar estado
Computação Evolutiva 31PUCPR (2005)
Nova População
Avaliar a fitness e manter os melhores 50%, resultando assim uma nova população do tamanho da inicial.