IA_Aula07

Prévia do material em texto

*
PUCC
Inteligência Artificial
*
PUCC
Agenda - Aula 06
 Computação Evolutiva
Algoritmos Genéticos
*
PUCC
Computação Evolutiva
Dois enfoques
Otimização de problemas
Resolução de Problemas
Teoria de Evolução de Darwin
Projeção a partir dos anos 70
Ampla utilização na abordagem de diversos problemas devido à sua adaptabilidade e robustez
*
PUCC
Algoritmos Genéticos
Idéia Básica
Analogia com mecanismos de Evolução Natural de Darwin
Capacidade de adaptação a diversos ambientes OTIMIZANDO a chance de sobrevivência
John Holland: tenta copiar os mecanismos dos sistemas naturais e adaptá-los para sistemas artificias 
*
PUCC
Teoria de Darwin
As espécies evoluem através de modificações nos códigos genéticos dos indivíduos – GENÓTIPOS.
Essas modificações são introduzidas pela reprodução sexuada, quando se combinam dois genótipos diferentes ou através de mutações (pequena modificação num genótipo).
Genótipos mais características encontradas no ambiente constroem as características físicas do indivíduo – FENÓTIPO
Os indivíduos cujos genótipos favorecem fenótipos adaptados ao ambiente onde vivem têm mais chances de sobrevivência e reprodução.
*
PUCC
Teoria de Holland
Nova forma de abordar problemas
Um conjunto de soluções é codificado geralmente através de um string
Esse string é chamado de indivíduo ou cromossomo.
Um conjunto de indivíduos é chamado população.
Cada iteração é chamada geração
Em cada geração os indivíduos são submetidos à operações de crossover, mutação, avaliação e seleção
*
PUCC
Codificação do Problema
Descrever as soluções como indivíduos
Definição das variáveis ( gens )
Ideal compacta, completa e estável
Compacta: menor número possível de variáveis para representar uma solução
Completa: capacidade de representar todas as soluções possíveis
Estável: pequenas mudanças no indivíduo leva a pequenas alterações de adaptabilidade
*
PUCC
Seleção
Deve favorecer os bons indivíduos 
Velocidade de convergência deve ser calibrada
Formas de seleção
Seleção por Roleta ponderada
Seleção Linear
Seleção por descendência
*
PUCC
Operações
Crossover
Misturar informações genéticas de dois indivíduos originando um terceiro
Codificação binária – crossover a um ponto
Plan1
		
		
		
		
		
		
		
		
		
		
		
		
																Ponto de Corte
								P1
								1		1		1		1		1		1				Filho
																						1		1		1		1		0		0
								P2
								0		0		0		0		0		0
Plan2
		
Plan3
		
*
PUCC
Operações
Mutação
Leve alteração no cromossomo
Codificação binária mutação a um bit é a mutação por excelência
Plan1
		
		
		
		
		
		
		
		
		
		
		
		
																Ponto de Corte
								P1
								1		1		1		1		1		1				Filho
																						1		1		1		1		0		0
								P2
								0		0		0		0		0		0
		
		
		
																				Mutação
								1		1		1		1		0		0				1		1		0		1		0		0
Plan2
		
Plan3
		
*
PUCC
Fitness
É unicamente através da função de aptidão (fitness) que esse tipo de algoritmo sabe se uma solução é melhor que a outra.
Deve ser calculada de forma eficiente
Numa solução de g gerações e n indivíduos ela será calculada g x n vezes.
*
PUCC
Idéia Básica
Codificação do Problema
Gera Solução Inicial
Seleção
Crossover
Mutação
Avaliação
continua
S
N