algoritmos geneticos

Algoritmos Genéticos
Ricardo Prudêncio

Algoritmos Genéticos –
 Estefane Lacerda – Introdução aos Algoritmos
Referência
Básica da Aula
Genéticos. Em Sistemas Inteligentes – Aplicações a
Recursos Hídricos e Ciências Ambientais, 1999
 http://www.dca.ufrn.br/~estefane/metaheuristicas/ index.html Roteiro


Introdução




Algoritmos Genéticos






Otimização
Representação
Seleção
Operadores Geneticos

Aplicação


Caixeiro Viajante

Introdução


Algoritmos Genéticos (AGs), são métodos de otimização inspirados em evolução




J. Holland (1975), D. Goldberg (1989)

Teoria da Evolução




Indivíduos mais adaptados sobrevivem e transmitem suas características para as gerações seguintes Charles Darwin (Origem das Espécies, 1859)

Otimização - Definição


Espaço de Busca




Função Objetivo




Possíveis soluções de um problema

Avalia cada solução com uma nota

Tarefa:


Encontrar a solução que corresponda ao ponto de máximo (ou mínimo) da função objetivo

Otimização - Exemplo


Achar ponto máximo da função


f(x) = xsen(10πx) + 1, -1 ≤ x ≤ 2

Otimização - Dificuldades


Alguns problemas podem ter espaços de busca muito grandes



Muitos algoritmos não são capazes de localizar ótimo global na presença de múltiplos ótimos locais


Ex.: Hill Climbing

Algoritmos Genéticos


Geração de um conjunto inicial de soluções que são iterativamente melhoradas




População de indivíduos (cromossomos)

Busca de soluções seguem um processo evolutivo 

Seleção dos mais aptos +
Transmissão de características

Algoritmos Genéticos


Passo 1: Geração de uma população inicial com indivíduos escolhidos aleatoriamente



Passo 2: Avaliação dos indivíduos


Cálculo da função de fitness (usando função objetivo)



Passo 3: Seleção de indívíduos mais aptos



Passo 4: Geração de uma nova população a partir dos indivíduos selecionados e ir para Passo 2


Operadores de busca (crossover e mutação)

Algoritmos Genéticos

Algoritmos Genéticos


AGs são