AG_ex1

Prévia do material em texto

Universidade Federal de São João del-Rei 
Departamento de Engenharia Mecânica 
Prof
es
: Lenir Jr. / Scola / Sérgio Cerqueira 
Disciplina de Otimização para Engenharia Mecânica 
 
EXEMPLO DE APLICAÇÃO DE ALGORITMO GENÉTICO 
 
Considere o problema de otimização não linear-convexa 
 
Minimizar 
 
 
 - (função objetivo – f(x1, x2) ) 
Sujeito as restrições 
 
 
[a,b]=[-2,1] 
 
A figura 1 nos destaca o comportamento da função objetivo dentre valores de x1 e x2 [-100,100], e a 
figura 2 nos demonstra o comportamento da f (curvas de nível) e sua devida restrição imposta. 
 
 
Figura 1: Função objetivo 
 
 
Figura 2: Destaque das restrições do problema, dada f(x1,x2) 
 
Conforme a estrutura dos Algoritmos Genéticos (AG) (Figura 3), será resolvido o exercício, tal que o 
primeiro passo é a determinação da População inicial. 
 
 
Figura 3: Estrutura de um AG 
 1° passo – População inicial 
 
Considere a seguinte população inicial, cada linha representa um indivíduo com duas variáveis, os 
primeiros 4 bits para x1 e os 4 últimos para x2 , ou seja, cada linha representa um cromossomo de 8 bits ou o 
genótipo de cada indivíduo (Tabela 1). 
 
Tabela 1: População inicial onde cada indivíduo é representado por um cromossomo de 8 genes (bits) 
Indivíduo 
 genes 
x1 (binário) x2 (binário) 
1 0 1 0 1 0 1 1 1 
2 1 1 1 1 1 1 0 0 
3 1 0 1 0 1 1 0 0 
4 0 1 0 0 0 0 1 1 
5 0 0 0 1 1 0 0 1 
6 0 0 1 0 1 0 1 0 
 
Pede-se: 
(a) Determine o valor das variáveis reais x1 e x2, considerando que apenas 4 bits são 
utilizados para representá-las. 
(b) Determine o valor da função objetivo para cada indivíduo 
(c) Atribua a aptidão a cada indivíduo 
(d) Empregue a roleta, considerando como número aleatório 0,634 
(e) Efetue o cruzamento dos dois indivíduos de maior aptidão, considerando um ponto de 
corte no 3º bit. Determine os valores da função objetivo dos filhos. 
(f) Efetue a mutação dos dois indivíduos de menor aptidão, considerando a alteração no 2° 
bit. Determine os valores da função objetivo dos filhos. Reordene a população. 
(g) Qual a precisão de busca realizada. 
 
RESPOSTAS 
 
(a) x1 e x2? Representados por 4bits. 
 
Visto que é necessário a transformação de base binária para base decimal e por fim a discretização 
em um intervalo real e contínuo [a,b] para o cálculo de x1 e x2, utilizando-se das equações (1) e (2) para 
calcular o fenótipo de cada indivíduo, ou mensurar o valor da característica intrínseca no genótipo de cada 
indivíduo, onde temos n bits e N indivíduos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
No nosso problema o campo de possibilidades, delimitado pelos extremos [a,b], determina a região 
factível de possível soluções ótimas dadas as variáveis x1 e x2. Para este caso temos a=-2 e b=1, assumindo 
mesmos valores para x1 e x2. (Figura 4). 
 
 
Figura 4: Região Factível delimitada pelo conjunto de restrições das variáveis x1 e x2 
 
Portanto, da tabela 2 conseguimos expressar os valores de x1 e x2 conforme equações (1) e (2). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabela 2: Determinação dos valores de x1 e x2. 
Indivíduo 
1 5 7 -1 -3/5 
2 15 12 1 2/5 
3 10 12 0 2/5 
4 4 3 -6/5 -7/5 
5 1 9 -9/5 -1/5 
6 2 10 -8/5 0 
 
(b) f(x1 , x2)? 
-2,5 
-2 
-1,5 
-1 
-0,5 
0 
0,5 
1 
1,5 
-2,5 -2 -1,5 -1 -0,5 0 0,5 1 1,5 
x2 
x1 
 
Figura 5: 2° passo - Avaliação 
 
 
Para avaliação da função objetivo, utilizaremos os valores das variáveis reais x1 e x2 anteriormente 
encontrados e apresentados na tabela 3 a seguir. 
 
Tabela 3: Valores da f(x1, x2) 
Indivíduo f(x1, x2) 
1 -1 -3/5 22,76 
2 1 2/5 6,56 
3 0 2/5 11,56 
4 -6/5 -7/5 29,20 
5 -9/5 -1/5 27,88 
6 -8/5 0 25,16 
 
(c) Aptidão? 
 
Torna-se necessário neste passo, reordenarmos a população conforme avaliação realizada e 
atribuir um valor de aptidão (ai) para cada indivíduo. Neste caso foram atribuídos de forma 
decrescente os valores de aptidão para cada indivíduo, variando de N até 1, onde o valor N 
representa a aptidão do indivíduo da população mais apto (adaptável ao meio) e mais provável de se 
reproduzir e transferir sua carga genética às gerações posteriores, e por consequência o indivíduo 
menos apto recebe o valor de aptidão 1 (Tabela 4). 
Conforme equações (3) e (4) é possível determinar as aptidões relativas ( 
 ) e aptidões 
relativas acumuladas ( 
 ) de cada indivíduo da população (Figura 6), respectivamente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabela 4: População reordenada conforme avaliação e 
valores das aptidões de cada indivíduo 
Indivíduo Ordenamento f(x1, x2) ai 
 
 
2 1 6,56 6 0,286 0,286 
3 2 11,56 5 0,238 0,524 
1 3 22,76 4 0,190 0,714 
6 4 25,16 3 0,143 0,857 
5 5 27,88 2 0,095 0,952 
4 6 29,20 1 0,048 1,000 
 
 
Figura 6: Distribuição das aptidões relativas de cada indivíduo 
 
(d) Seleção? Escolha aleatória pelo número 0,634. 
 
 
Figura 7: 3° passo - Seleção 
 
Escolhe-se portanto, um dos pais que será selecionado para ser reprodutor, aquele que tiver seu valor 
de aptidão acumulada imediatamente menor ou igual a 0,634 para o processo de minimização. Para o 
presente caso escolheu-se pelo método da roleta o indivíduo 1. Para os problemas de otimização é 
importante que se escolha sempre um par de pais que poderão através do método posteriormente de 
cruzamento gerar outros 2 filhos e substituídos por estes filhos na população, vistos como indivíduos 
evoluídos ao longo da geração. Caso estes pais não consigam se reproduzir, estes retornarão à população 
sem qualquer modificação. 
 
(e) Cruzamento? 2 indivíduos mais aptos. 3° bit. 
 
1 
0,2861 
0,524 
0,714 
0,857 
0,952 
 
Figura 8: 4° passo – Reprodução - Cruzamento 
 
Os indivíduos 2 e 1 foram os que obtiveram maiores valores de aptidão e sofrerão cruzamento a 
partir do 3° bit, e portanto os 2 filhos sequentes terão cargas genéticas herdadas dos pais. 
 
Tabela 5: Indivíduos mais aptos que sofreram cruzamento. 
Indivíduo 
 genes 
x1 (binário) x2 (binário) 
2 (Pai_1) 1 1 1 1 1 1 0 0 
1 (Pai_2) 0 1 0 1 0 1 1 1 
1
o
 Filho 1 1 1 1 1 1 1 1 
2
o
 Filho 0 1 0 1 0 1 0 0 
 
 
(f) Mutação? 2 indivíduos menos aptos. 2° bit. 
 
 
Figura 9: 5° passo – Reprodução - Mutação 
 
Os indivíduos 4 e 5 foram os que obtiveram maiores valores de aptidão e sofrerão mutação no 2° bit, 
e foram expressos na tabela 6. 
 
Tabela 6: Indivíduos menos aptos que sofreram mutação. 
Indivíduo 
 genes 
x1 (binário) x2 (binário) 
4 0 1 0 0 0 0 1 1 
5 0 0 0 1 1 0 0 1 
4 –mutado 0 1 0 0 0 0 0 1 
5 - mutado 0 0 0 1 1 0 1 1 
 
A parir de agora deve se realizar uma nova avaliação da população e reordená-la. Os novos 
indivíduos da população que iniciará uma nova geração estão destacados na tabela 7 a seguir. 
 
Tabela 7: Indivíduos da População inicial que sofreram o processo de seleção e reprodução e 
formarão a população inicial de uma nova geração. 
Indivíduo 
 genes 
x1 (binário) x2 (binário) 
1 (filho) 0 1 0 1 0 1 0 0 
2 (filho) 1 1 1 1 1 1 1 1 
3 1 0 1 0 1 1 0 0 
4 (mutado) 0 1 0 0 0 0 0 1 
5 (mutado) 0 0 0 1 1 0 1 1 
6 0 0 1 0 1 0 1 0 
 
A partir de agora será realizado uma nova avaliação para verificar se houve alguma modificação no 
melhor indivíduo encontrado na população. Avaliará se houve uma melhora ou piora após os procedimentos 
de seleção e reprodução (Figura 10). 
 
Figura 10: 4° passo – Reprodução - Cruzamento 
 
Após avaliação ao final da 1ª geração (Tabelas 8 e 9), foi constatado queo indivíduo 2 ainda é 
considerado como o melhor indivíduo, no entanto a sua nova geração, ou seja, filhos herdaram esta 
característica e se tornaram mais aptos e possivelmente esteja bem próximo do que seria o mínimo restrito 
desta função objetivo, conforme pode ser observado através do gráfico das curvas de nível da função 
objetivo (Figura 2). 
 
Tabela 8: Avaliação dos indivíduos da população inicial 
após processos de seleção e reprodução. 
Indivíduo f(x1, x2) 
1 5 4 -1 -6/5 26,24 
2 15 15 1 1 5,00 
3 10 12 0 2/5 11,56 
4 4 1 -6/5 -9/5 32,08 
5 1 11 -9/5 1/5 26,28 
6 2 10 -8/5 0 25,16 
 
Tabela 9: Resultados após a 1ª geração. 
Ordenamento 
Mais aptos 
Indivíduos 
1ª 
avaliação 
f(x1, x2) 
1ª 
avaliação 
Indivíduos 
2ª 
avaliação 
f(x1, x2) 
2ª 
avaliação 
1 2 6,56 2 5,00 
2 3 11,56 3 11,56 
3 1 22,76 6 25,16 
4 6 25,16 1 26,24 
5 5 27,88 5 26,28 
6 4 29,20 4 32,08 
 
(g) Precisão? 
 
Conforme a quantidade de bits utilizada para representar as variáveis x1 e x2 em estudo, pode-se 
determinar a precisão da busca realizada (Δ), que poderá ser utilizada como condição ou critério de parada, 
conforme resultado da f(x1, x2) dentro do intervalo de restrições [a,b] dado, e expresso pela equação 5. 
 
 
 
 
 
 
 
 
 
 
 
Para este caso o valor de delta encontrado foi de 0,2. 
 
Vamos explanar um pouco sobre o procedimento de critério de parada, para darmos fim a estrutura 
de um algoritmo genético. 
 
 
Figura 11: 4° passo – Reprodução - Cruzamento 
 
 
Uma forma de condição ou critério de parada pode ser escolhida devido a um dado erro máximo 
admissível (erromax) entre os melhores indivíduos encontrados, não avanço no valor da função objetivo e 
ainda um numero máximo de gerações (maxgen) estipuladas. Um valor de incremento usual tanto para 
variáveis quanto para função objetivo é 10
-3
. 
 
Uso de um AG codificação binária para avaliação do Exercício 
 
Com uso do software Matlab
@
, foi possível a implementação de um AG e cálculo do possível valor 
de mínimo da função objetivo deste exercício conforme restrições e critérios impostos. 
 
Os parâmetros utilizados foram os seguintes: 
 
N=40; (tamanho da população inicial) 
n=8; (quantidade de bits utilizados para representar cada indvíduo) 
restrições = [-2,1;-2,1]; (região factível delimitada pelas variáveis x1 e x2). 
maxgen= 100; (número máximo de gerações aceita) 
erromax=10
-3
 (erro máximo admissível) 
maxt=1:1:maxgen; (gerações avaliadas) 
 
Os resultados encontrados do AG são os seguintes: 
 
Minimo valor da função objetivo: 5 
Encontrado o melhor indivíduo na geração (maxt): 14 
Melhor indivíduo encontrado: x1=1 e x2= 1 
A iteração parou na geração 20 
Tempo decorrido foi de 0.743segundos. 
 
Ao observarmos a figura 12 o melhor indivíduo encontrado na geração 14 não obteve mais nenhuma 
melhora nas gerações seguintes, fazendo com que o AG decida por ele como um mínimo restrito. Ao 
observamos o comportamento da função, dada a região de restrição, já era esperado que os valores das 
variáveis x1=1 e x2= 1 fossem encontradas, visto que é o vértice da região factível, podendo ser facilmente 
observado na figura 2. AG’s são fundamentais quando temos funções objetivo não muito bem comportadas, 
difíceis de serem avaliadas apenas graficamente, ou quando a quantidade de variáveis sejam maiores ou 
iguais a 3, com um menor custo computacional e maior eficiência nos resultados, quando comparados a 
métodos analíticos que venham ser extremamente complexos e dispendiosos. 
 
 
Figura 12: Convergência do melhor indivíduo por geração.