Algoritmos Genéticos
Alex F. V. Machado
Heurísticas e Aplicações
• Define soluções para um problema através da otimização
dos resultados gerados
• Tem como objetivo medir ganhos de eficácia e de precisão
para definir os melhores resultados.
• São utilizadas em problemas que possuem uma
complexidade elevada em função do grande número de
soluções possíveis
• Denomina-se 'heurística' a capacidade de um sistema fazer
inovações e desenvolver técnicas de forma imediata e
positiva para um determinado fim.
2
Algoritmos Genéticos (AG)
Aplicações de AG
•
•
•
•
Composição Musical
Prescrição Médica
Controle de Sistemas Dinâmicos
Engenharia em Construções para
otimização discreta de estruturas
• Busca em Base de Dados
• Resolução de Problemas em Jogos
• Otimização de Sistemas Complexos
Componentes de um AG
Componentes de um AG
Árvore de Buscas
(Exemplificação)
Estrutura Game Search Tree (Árvore de Buscas)
Na teoria combinatória dos jogos, representa um
Grafo Direcionado cujos nodos são as posições de um jogo e os
vértices são os movimentos possíveis.
Árvore de Buscas
Podemos definir os seguintes cromossomos
(cada um com dois genes):
A={1,1}, B={1,2}, C={2,2} e D={3,2}.
Representação do Crossover
A={1,3, 3, 2}
B={1, 2, 4, 3}
s1={1,3, 4, 3}
s2={1, 2, 3, 2}
Representação da Mutação
B={1, 2, 4, 3}
s2={1, 2, 3, 3}
Problema!!!
Tabela de Movimentos
Algoritmo Genético aplicado - Fluxograma
13
Exemplo: Magic Square
Etapa 1
Representação de todas as situações
Exemplo: Magic Square
Etapa 2
Definição do tempo limite e do nº de gerações
Tempo Limite (segs.) = 10
N de Gerações = 10
Exemplo: Magic Square
Etapa 3
Definição da profundidade (game tree) e da função de
fitness
Profundidade = 15
Exemplo: Magic Square
Etapa 4
Definição da taxa de crossover e mutação
Crossover= 50%
Mutacao= 10%
Exemplo: Magic Square
Etapa 5
Geração da população inicial de cromossomos
Exemplo: Magic Square
Etapa 6
Execução do crossover
C1= {14, 4, 8, 0, 18, 17, 10, 12, 4, 6, 17, 17, 17, 14, 16}
C2= {10, 0, 1, 6, 3, 2, 2, 0, 5, 0, 8, 15, 12, 2, 2}
OS1= {14, 4, 8, 0, 18, 17, 10, 12, 4, 6, 17, 15, 12, 2, 2}
OS2= {10, 0, 1, 6, 3, 2, 2, 0, 5, 0, 8, 17, 17, 14, 16}
Exemplo: Magic Square
Etapa 7
Execução da mutação
C1= {7, 11, 8, 12, 8, 0, 3, 9, 1, 2, 11, 13, 9, 3, 2}
OS1= {7, 11, 8, 12, 8, 0, 3, 9, 8, 2, 11, 13, 9, 3, 2}
Exemplo: Magic Square
Etapa 8
Cálculo do valor de fitness de cada offspring
Exemplo: Magic Square
Etapa 9
Seleção dos melhores candidatos (critério elitista)
Exemplo: Magic Square
Etapa 10
Finalização ou repetição da Etapa 6
Solucao= {16, 9, 2 1, 4, 8, 7, 10, 16, 4, 12, 13, 7, 11, 4}