ALGORITMOS
GENÉTICOS
INTRODUÇÃO
• São métodos adaptativos que podem ser
usados para resolver problemas de busca e
otimização.
• Na natureza a combinação de boas
características provenientes de diferentes
indivíduos ancestrais pode produzir
descendentes “superindivíduos”, cuja
adaptação é muito maior que a de seus
ancestrais.
• Os algoritmos genéticos usam uma analogia
direta com o comportamento natural.
INTRODUÇÃO
• A cada indivíduo se associa um grau de
aptidão, que determina a sua capacidade de
competir com os demais membros da
população.
• Basicamente os algoritmos genéticos tratam
problemas de otimização como um processo
iterativo de busca da melhor solução dentro
do espaço de possíveis respostas para o
problema.
ALGORITMO GENÉTICO SIMPLES
I nício
Gerar população i nicial
Calcular a f unção de
avaliação para os i ndivíduos
novos
Calcular a f unção de aval iação de
c ada i ndivíduo
I ncluir os descendentes na
nova geração
Enquanto não t erminar f aça
I nício
F im
Para ( t amanho da população / 2 )
f aça
S e população c onvergiu e ntão
Terminou - > verdade
I nício
S elecionar dois i ndivíduos
Real izar o c ruzamento
Apl icar mutação nos
descendentes
f im
f im
COMO FUNCIONA
• Inicia com um conjunto aleatório de soluções
iniciais, que constituem a população inicial.
• Combinando os melhores representantes dessa
população, obtém uma nova, que passa a
substituir a anterior, caracterizando-se como a
próxima geração.
• O mecanismo é repetido.
• A cada nova iteração a população é
refinada gerando novas e melhores soluções
para o problema em questão, culminando com
a sua convergência.
ALGORITMO GENÉTICO SIMPLES
• Os indivíduos componentes da população
(possíveis soluções do problema) podem ser
representados como um conjunto de
parâmetros (denominados genes).
• A adaptação de um indivíduo ao problema
depende de seu genótipo.
• A função de adaptação deve ser projetada
para cada problema.
ALGORITMO GENÉTICO SIMPLES
• A função de avalição ou função fitness
associa as características do indivíduo a um
número.
• No caso de binário indicam a presença ou não
de uma determinada característica.
OPERAÇÕES BÁSICAS
• CrossOver (cruzamento): é uma operação
binário que a partir de dois indivíduos produz
outros dois novos indivíduos utilizando uma
recombinação dos cromossomos.
1
0
0
1
0
0
0
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
1
1
1
0
0
1
0
0
1
0
0
0
OPERAÇÕES BÁSICAS
• Mutação: é uma operação unário que altera
um gene de um indivíduo da população.
1
1
0
1
1
0
0
1
1
0
0
1
1
Ponto de
cruzamento
Novo
i ndivíduo
0
0
EXEMPLO
• 1 – Aplique algoritmo genético para encontrar
uma boa solução para otimizar a função.
F(x) = -x2 + 3x + 5
EXEMPLO
• 1º passo: Definir a população inicial.
• como a solução ótima é menor do que 5, vamos
representar no formato binário números maiores que
zero e menores do que 5, portanto números de 3
bits.
• Universo [o,7]
I1
1
1
1
I2
0
0
0
* I 1 e I 2 podem ser escolhidos
aleatoriamente, ou não, na
população.
EXEMPLO
• 2º passo: Escolher a função de avaliação.
Neste caso utilizaremos a função que será
otimizada, pois quanto maior o valor desta
função, mais próximo do máximo locar ela
estará.
EXEMPLO
• 3º passo: Avalição dos indivíduos
I1
1
1
1
= 7 -> f (7) = -49+21+5 = -23
I2
0
0
0
=0 -> f (0) = -0 + 0 + 5 = 5
EXEMPLO
• 4º passo: Cruzamento – seleção do ponto do
cruzamento – neste caso escolheu-se o ponto 1
I3
-> 0
I1
1
1
1
I2
0
0
0 ->
1
I4
1
1
= 3 -> f (3) = -9+9+5 = 5
0
0
= 4 -> f (4) = -16+12+5 = 1
EXEMPLO
• 5º passo: aplicar a mutação em um indivíduo
I3
0
1
1
Ponto de
mutação
I5
-> 0
1
0
= 2 -> f (2) = -4+6+5 = 7
EXEMPLO
• Rank
Rank
I1
-23
I2
5
I3
5
I4
1
I5
7
Rank
I5
7
I2
5
I3
5
I4
1
I1
-23
Como a população não está estável, replicaremos
o algoritmo
EXEMPLO
• 4º passo: Cruzamento – como a população possui
4 elementos, faremos 2 cruzamentos.
I6
-> 0
I5
0
1
0
I2
0
0
0 ->
0
I7
1
0
= 2 -> f (2) = -4+6+5 = 7
0
0
= 0 -> f (0) = -0+0+5 = 5
EXEMPLO
• 4º passo: Cruzamento – como a população possui
4 ou mais elementos, faremos 2 cruzamentos.
I8
-> 0
I5
0
1
0
I3
0
1
1 ->
0
I9
1
1
= 3 -> f (3) = -9+9+5 = 5
1
0
= 2 -> f (2) = -4+6+5 = 7
EXEMPLO
• 5º passo: Mutação, o I 8 foi escolhido
aleatoriamente
I8
0
1
1
Ponto de
mutação
I 10
-> 0 0
1
= 1 -> f (1) = -1+3+5 = 7
EXEMPLO
• Rank após duas gerações
Rank
I1
-23
I2
5
I3
5
I4
1
I5
7
I6
7
I7
5
I8
5
I9
7
I 10
7
Rank
I5
7
I6
7
I9
7
I 10
7
I2
5
I3
5
I7
5
I8
5
I4
1
I1
-23
Entre os quatro melhores, a população se
estabilizou em avaliação 7.
EXEMPLO
• Rank após duas gerações
Rank
I5
7
I6
7
I9
7
I 10
7
I2
5
I3
5
I5
0
1
0
= 2 -> f (2) = -4+6+5 = 7
I 10
0
0
1
= 1 -> f (1) = -1+3+5 = 7
I7
5
I8
5
I4
1
Assim, o ponto ótimo está entre I 5 = 2 e I 10 = 1
[1,2]
I1
-23