Algoritmos Geneticos

Analogias

Inteligência Artificial
Prof. Rômulo Nunes de Oliveira

Darwin (Inspiração)

Algoritmos Genéticos

Meio ambiente
Indivíduos

Algoritmos Genéticos

O domínio do problema em questão soluções válidas para o problema

Atributos ou valores a serem considerados na características dos avaliação da solução em questão. indivíduos Os mais aptos soluções com alto grau de qualidade, eficácia ou completude.
Cruzamentos
soluções combinadas umas com as outras. Mutação
Solução com algum atributo alterado aleatoriamente após o cruzamento.

Introdução

Algoritmo Geral
População
Inicial

Nova
População

Cálculo da
Aptidão

Reprodução e Mutação

Inspirado na teoria da Seleção Natural de Darwin...
É um método utilizado pelos Algoritmos Evolutivos, onde é criada uma população de indivíduos representados por cromossomos. Os indivíduos passam por um processo de simulado de evolução, seleção e reprodução, gerando uma nova população.
Sim

“Os mais aptos sobrevivem !”

Onde usar?

Atingiu o critério de parada? Não

Ilustração do Algoritmo Geral
P0

Em problemas onde não é possível testar todas as possíveis soluções (alto custo computacional – problemas np-difícil);

Cálculo de aptidão e seleção dos melhores Pais da nova geração P1

Não se deseja encontrar a melhor solução possível, mas apenas uma das melhores soluções.
Quando é possível criar por meios matemáticos uma função de avaliação da qualidade das soluções para o problema. Quando é possível criar mecanicamente respostas para o problema (respeitando alguma heurística ou não)

“Seleção
Natural”

Espaço que representa o universo de possíveis soluções para o problema.
Os Indivíduos da população inicial são criados aleatoriamente.

Filhos obtidos por cruzamento e mutação

P2

Cálculo de aptidão e seleção dos melhores Pais da nova geração (...)

Filhos obtidos por cruzamento e mutação

Cálculo de aptidão