Algoritmos Genéticos
Rômulo Ferreira Douro
Estrutura da apresentação
• Introdução – heurísticas
• Algoritmos genéticos
– Ideias e considerações
– Conceitos básicos: representação, geração inicial,
fitness, seleção, reprodução, mutação, parâmetros
– Procedimento de execução
– Refinamento: busca local
– AG’s paralelos
• Exemplos de aplicações
- Introdução –
Heurísticas
• Alcançar uma boa solução
• Tempo computacional aceitável
• Algoritmos evolucionários
– Aspectos biológicos
– Soluções computacionais
• Algoritmos Genéticos, Programação Genética,
Programação Evolucionária
- Algoritmos Genéticos Ideias e considerações
• História: Concebidos por John Holland (1975)
• Analogia com sistemas naturais
Natureza
Algoritmo Genético
Cromossomo
Binário, String, vetor
Gene
Característica do problema
Genótipo
Estrutura
Fenótipo
Estrutura submetida ao problema
Indivíduo
Solução
Geração
Ciclo da evolução
- Algoritmos Genéticos Conceitos básicos
• Representação
• Dependente da necessidade do problema
– Cadeia de bits (função)
– Vetor (Caixeiro Viajante)
- Algoritmos Genéticos Conceitos básicos
• Representação – Cadeia de bits (função)
• f(x) = 1024-(x-32)2
- Algoritmos Genéticos Conceitos básicos
• Representação – Vetor (Caixeiro Viajante)
• C = {3, 4, 2, 1, 5}
3
4
2
5
1
- Algoritmos Genéticos Conceitos básicos
• Geração inicial
• População gerada aleatoriamente
• Utilização de outra heurística
– Geralmente depende do problema
– Exemplo GRASP
- Algoritmos Genéticos Conceitos básicos
•
•
•
•
Fitnnes
Também chamado de aptidão
Geralmente se usa a própria função objetivo
Pode ser agregado de penalidades
- Algoritmos Genéticos Conceitos básicos
• Seleção
• Comumente usado o método da roleta
- Algoritmos Genéticos Conceitos básicos
0
100
3
4
1
2
- Algoritmos Genéticos Conceitos básicos
• Reprodução
• Um conjunto é selecionado e trocado entre
indivíduos
- Algoritmos Genéticos Conceitos básicos
• Reprodução
• Aplicado ao PCV
{2,3,5,1,4}
{1,5,2,4,3}
{1,5,3,2,4}
{2,3,1,4,5}
- Algoritmos Genéticos Conceitos básicos
• Mutação
• Altera um ou mais genes = gera material
genético diversificado
{2,3,5,1,4}
{2,3,4,1,5}
- Algoritmos Genéticos Conceitos básicos
• Parâmetros
– Tamanho da população
– Taxa de cruzamento
– Taxa de mutação
– Taxa de substituição
- Algoritmos Genéticos Conceitos básicos
• Tamanho da população
• Se pequeno
– Executa rápido
– Baixa qualidade
• Se grande
– Boa qualidade
– Custo computacional
- Algoritmos Genéticos Conceitos básicos
• Taxa de cruzamento
• Se pequeno
– Convergência demorada
• Se grande
– Perda de material genético
- Algoritmos Genéticos Conceitos básicos
• Taxa de mutação
• Previne a permanência em espaço de busca
limitado
– Máximos locais
• Se muito elevado
– Busca aleatória (ruim)
- Algoritmos Genéticos Conceitos básicos
• Taxa de substituição
• Quantidade de indivíduos a ser descartada
– Bons sobrevivem
– Menos aptos são excluídos
– Material genético desconsiderado
- Algoritmos Genéticos Procedimento da execução
• Esquema de execução
- Algoritmos Genéticos Refinamento
• Busca local
Esquema 2-opt
Caminho inicial
6
0
5
Comparação para troca
6
0
1
5
2
4
1
3
3
Aplica a inversão
6
0
5
Resultado final
6
0
1
2
4
3
2
4
5
4
3
1
2
- Algoritmos Genéticos AG paralelo
• Principal motivo
– Elevar o tamanho populacional
• Algoritmo Genético Insular
– Populações evoluem de forma independente
– Política de migração
• Cuidado para não inserir indivíduos muito aptos e
passíveis de conquistar uma população
- Algoritmos Genéticos AG paralelo
• Mestre X Escravos
- Algoritmos Genéticos AG paralelo
• População Global com Paralelismo
– Um processador contém a população e outros
efetuam a avaliação do indivíduo
– Função de avaliação muito custosa
• Algoritmo Genético Celular
– Para cada processador é fixada a tarefa de um
indivíduo e as iterações entre eles é feita entre
processadores vizinhos
Exemplos de aplicações
• Robótica de combate a acidentes ambientais
• Dobramento de proteínas
• Configuração temporal para mercado
financeiro
• Just-in-time Scheduling
• Sequênciamento com penalidades