Baixe o app para aproveitar ainda mais
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
Compartilhar