Otimização de Funções Contínuas
via Algoritmos Genéticos
Adaptado do trabalho realizado por:
Frederico Heitor
Mônica do Amaral
Problema
Dada uma função contínua, diferenciável ou não, encontrar seu valor
máximo dentro de um certo intervalo [a, b].
Exemplo:
Determinar o máximo da função:
ƒ(x) = 0.4 + sinc (4x) + 1.1 sinc (4x + 2) + 0.8 sinc (6x – 2)
+ 0.7 sinc (6x – 4)
para x  [-2 , 2]
onde:
1
, x=0
sinc (x) =
sen (л x) / (л x) , x ≠ 0
ƒ(x) = 0.4 + sinc (4x) + 1.1 sinc (4x + 2) +
0.8 sinc (6x – 2) + 0.7 sinc (6x – 4)
Método Utilizado
Algoritmos Genéticos com os seguintes mecanismos:
- Seleção
Escolha dos pais utilizando-se Roleta Russa
- Crossover
Escolha aleatória do ponto de corte do cromossomo
- Mutação
Escolha aleatória do bit a ser trocado
- Sobrevivência pelo mecanismo da roleta russa
Modelagem
- Cada indivíduo é representado por um vetor binário de n posições, que
corresponde a um ponto contido no intervalo [a, b] de definição da
função.
-O valor de n é determinado pela aplicação da fórmula:
 ba
ln1 

 

n
ln(2)
Cada valor real x da função f é determinado aplicando-se a
fórmula:
x = a + [ b - a] . B/R
onde:
B = valor decimal correspondente ao vetor binário v[i]
R = valor decimal correspondente ao máximo valor decimal que
um vetor binário de n posições pode assumir.
Modelagem
- No problema em questão, cada indivíduo é representado por
um vetor binário de 16 posições, que corresponde a um ponto
contido no intervalo [-2, 2] de definição da função
- Para calcular o valor da função objetivo de um determinado
indivíduo representado na forma binária com 16 posições,
calcula-se inicialmente o valor real x pela fórmula:
x=-2 +
4B
65535
onde B é o número decimal que corresponde à seqüência
binária de um indivíduo qualquer
A seguir, aplica-se a função f
Modelagem - Reprodução
Nesta etapa, dois indivíduos da população são escolhidos por
meio do mecanismo da Roleta Russa. Aqueles que possuirem
maior aptidão têm maior probabilidade de serem
selecionados.
O casal escolhido tem uma probabilidade pcrossover de gerar
filhos. Em caso positivo, cada casal gera dois filhos
Modelagem - Crossover
Um número aleatório entre 1 e o número de bits determina a
posição onde será efetuado o corte no vetor (cromossomo).
Exemplo:
Número Sorteado: 4
Pai 1: X X X X X X X X X
Pai 2: Y Y Y Y Y Y Y Y Y
Posição do Corte
Filho 1: X X X X Y Y Y Y Y
Filho 2: Y Y Y Y X X X X X
Modelagem - Mutação
Um número aleatório entre 1 e o número de bits determina o
bit a sofrer mutação.
Exemplo:
Número Sorteado: 9
I =[0110110001101011]
Após a mutação:
I =[0110110011101011]
Implementação
Parâmetros utilizados:
- Tamanho da população inicial = 30
- Probabilidade de Crossover = 0,80
- Probabilidade de Mutação = 0,01
- Critério de parada = 50 gerações
Resultados Encontrados
N.° Teste
1
2
3
4
5
6
7
8
9
10
Valor máximo de f(x)
1,495005
1,500772
1,500772
1,495005
1,500772
1,495005
1,495005
1,500772
1,500772
1,500772
Melhor solução encontrada = 1,500772
Média das soluções = 1,4984652
Desvio das soluções = 0,15%
Vantagens
- Encontra-se ótimos de funções mesmo em intervalos
não diferenciáveis.
- Fácil implementação.