Evolutionary Programming
Naraiel Ferrari
Overview geral
• USA na década de 60
• Lawrence J. Fogel
– “Intelligent behavior is a composite ability to predict one’s environment
coupled with a translation of each prediction into a suitable response in light
of some objective” (Fogel et al., 1966, p. 11)
• Ideia:
Capacidade
de
Adaptação
Inteligência
Prever
Ambiente
Overview geral
• Aplicações:
– Inicialmente: Predição com máquinas de estado
– Estendido: Problemas de otimização (1990)
• Destaques:
– Semelhante ao ES
– Auto adaptação dos parâmetros
– Não há recombinação (crossover)
Máquina De Estado Finito (FSM)
• M = {Q,T,P,S,O}
– Q: Estados
– T: Entrada
– P: Saída
– S: Próximo Estado
– O: Próxima Saída
• Depende apenas do estado inicial e da sua
entrada.
Predição com FSM
• Próxima Entrada?
• Dados:
– Estado Inicial: C
– Estados: C B C A A B
– Entrada: 0 1 1 1 0 1 = 29
• Saída: 110111
• Ideal: 010001 = 30
Técnica Evolutiva
• Uma sequência de símbolos é apresentada a uma
população de máquinas.
• Compara-se a saída com o próxima símbolo de
entrada
• Avalia-se o resultado
• Máquinas filhas são geradas (mutação):
–
–
–
–
–
Mude um símbolo de saída
Mude uma transição de estado
Adicione um estado
Delete um estado
Mude o estado inicial
FSM for Prime Numbers
• Sequencia de entrada: 1,2,3,4,5,7,8,9...
• Símbolos apresentado: 0,1,1,0,1,1,0,0..
• Uma sequência não estacionária foi gerada.
– função custo:
• 1 para cada predição correta
• 0 para cada predição incorreta
• -0.01 vezes a quantidade de estados
• Resultado: Após 202 símbolos de entrada, a
melhor máquina apresentava apenas 1 estado
e sempre previa um não primo.
Otimização de Função Contínuas:
meta-PE
• Representação
–  x1,…,xn, 1,…,n 
• Mutação
– i’ = i (1 + N(0,1))
– x’i = xi + i’Ni(0,1)
• Recombinação
– Não há crossover
• Seleção
– Determinística
– (µ+ µ)
• inicialize m indivíduos do tipo:
v = (x,s) e armazene em P.
Avalie todos os indivíduos
• t 1
• enquanto NOT
condição_de_parada faça,
– mute os indivíduos de P e
armazene em P’
– avalie os indivíduos gerados
em P’ (filhos)
– selecione m indivíduos de
P∪P’ por torneio estocástico
• t¬t+1
• fim enquanto
Função Ackley
• Resultados
– ES: 7.48 × 10−8
– PE: 1.39 × 10−2
• Mutação Gaussiana
– PE: 4.83 × 10−3
• Mutação de Cauchy