Algoritmos Genéticos Rômulo Ferreira Douro. Estrutura da apresentação Introdução –...

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}

34

2

15

- 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 localEsquema 2-opt

Caminho inicial

Aplica a inversão Resultado final

0

1

2

34

5

6Comparação para troca

0

1

2

34

5

6

0

1

2

34

5

6 0

4

3

21

5

6

- 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