Algoritmos Genéticos
Alex F. V. Machado
2
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.
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 BuscasPodemos 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
13
Algoritmo Genético aplicado - Fluxograma
Exemplo: Magic Square
Etapa 1Representação de todas as situações
Exemplo: Magic Square
Etapa 2Definição do tempo limite e do nº de gerações
Tempo Limite (segs.) = 10
N de Gerações = 10
Exemplo: Magic Square
Etapa 3Definição da profundidade (game tree) e da função de
fitnessProfundidade = 15
Exemplo: Magic Square
Etapa 4Definição da taxa de crossover e mutação
Crossover= 50%
Mutacao= 10%
Exemplo: Magic Square
Etapa 5Geração da população inicial de cromossomos
Exemplo: Magic Square
Etapa 6Execuçã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 7Execuçã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 8Cálculo do valor de fitness de cada offspring
Exemplo: Magic Square
Etapa 9Seleção dos melhores candidatos (critério elitista)
Exemplo: Magic Square
Etapa 10Finalização ou repetição da Etapa 6
Solucao= {16, 9, 2 1, 4, 8, 7, 10, 16, 4, 12, 13, 7, 11, 4}