Inteligência Computacional Relatório da Avaliação 1 Corrigido Endrew Barreto

Prévia do material em texto

¹ Acadêmico da Universidade Federal do Oeste do Pará, 8º semestre, matrícula 201200474. 
 
 
UNIVERSIDADE FEDERAL DO OESTE DO PARÁ 
INSTITUTO DE ENGENHARIA E GEOCIÊNCIAS 
PROGRAMA DE CIÊNCIA E TECNOLOGIA 
 
Avaliação 1 (2015/2) 
Endrew Henrique Barreto ¹ 
23 de fevereiro de 2016 
 Consideração 
Todo conteúdo desta avaliação fora desenvolvido no software MATLAB® versão 2015, 
e quanto ao tratamento dos dados de resposta utilizou-se o Microsoft Excel® (versão 2016). 
Respostas 
Questão 1 
 Para a otimização da função de Himmelblau (eq.1), primeiramente implementamo-la 
em um arquivo “.m” do MATLAB, o script pode ser visto no Anexo I. Vale lembrar que o 
nome designado a função (himmelblau) deve ser o mesmo nome do arquivo “.m”. 
Matematicamente a função é da forma: 
𝑓(𝑥, 𝑦) = (𝑥2 + 𝑦 − 11)2 + (𝑥 + 𝑦2 − 7)2 (01) 
Feito isto, podemos utilizar o GA para varrer o espaço de busca da função a procura de 
um valor ótimo. A fim de que o algoritmo seja executado 10 vezes desenvolvemos um script 
com um laço de iteração, o mesmo consta no anexo II. Este deve estar na mesma pasta do 
arquivo “.m” da função de Himmelblau quando for executado. Embora não tenha sido 
requisitado pelo comando da questão, a efeito comparativo decidiu-se executar uma otimização 
da mesma função utilizando a Metaheurística Particle Swarm (PSO). 
Para as configurações padrões dos solvers GA e PSO, a exceção da alteração na 
quantidade de partículas neste último, configurou-se para 50 (como no GA), e na taxa de 
crossover do GA que fora de 0,75. Encontramos os seguintes resultados:
 
 
Tabela 1: Pontos ótimos e valores ótimos (fitness) resultantes da otimização da função de Himmelblau 
com o GA e PSO. 
Ponto ótimo Himmelblau 
GA PSO Fitness 
X Y X Y GA PSO 
3,106073 1,943600 -2,805117 3,131312 0,363157 4,42E-11 
3,605484 -1,870051 3,584429 -1,848127 0,027282 1,98E-11 
3,601745 -1,855694 -2,805118 3,131312 0,015715 1,86E-11 
3,582423 -1,848179 3,584428 -1,848127 0,000211 2,25E-16 
3,041823 1,947932 -2,805118 3,131313 0,067059 2,63E-15 
3,005751 2,062981 3,584428 -1,848127 0,077967 3,42E-12 
-2,671416 3,111104 3,000000 2,000000 0,566214 7,10E-14 
3,000791 1,996658 3,000001 2,000001 0,000160 1,12E-10 
2,896229 2,054282 3,000001 1,999999 0,324420 3,38E-11 
-3,764862 -3,283020 2,999997 2,000003 0,012024 3,45E-10 
 0,145421 5,77E-11 Média 
3,023787 1,945766 3,000000 2,000000 0,047171 1,92E-11 Mediana 
2,744542 2,334139 2,936226 2,150475 0,199435 1,07E-10 
Desvio 
Padrão 
 Para a tabela 1, utilizamos seis casas decimais, junto com este relatório está sendo 
enviado o arquivo em Excel que contêm o valor com todas as casas decimais fornecidas pelo 
MATLAB. Sabemos que esta função (Himmelblau) tem os seguintes mínimos locais: 
𝑓(3.0, 2.0) = 0.0 
𝑓(−2.805118, 3.131312) = 0.0 
𝑓(−3.779310, −3.283186) = 0.0 
𝑓(3.584428, −1.848126) = 0.0 
 
Olhando estes pontos e comparando-os com os da tabela 1, podemos ver que o GA 
encontrou vários mínimos locais, os mais acurados e precisos estão destacados em verde. 
 
Olhando para os pontos mínimos, vemos que a precisão do GA se dá em média até a segunda 
casa decimal. Agora, atentando para os resultados do PSO vemos que o algoritmo encontra três 
mínimos locais, e as várias execuções forneceram valores bem acurados. Para este, comparando 
seus resultados com os mínimos conhecidos notamos que sua precisão se dá até a quinta casa 
decimal. 
Quanto a média, não podemos extrair valores coerentes dos pontos, uma vez que há 
diversos mínimos encontrados (relacionado a aleatoriedade dos métodos que vamos citar mais 
a frente). Mas a média dos valores das fitness encontradas nos mostra uma tendência geral das 
performances das execuções, uma vez que todos os mínimos assumem valor nulo para a função 
objetivo, no GA este valor foi de 0,145421, dependendo da magnitude do problema a ser 
resolvido podemos considerar que o mínimo global da função é o valor nulo ou bem próximo 
dele (caso a função não seja conhecida). Já o PSO teve a média das fitness o valor nulo (para as 
casas consideradas), já que nos conhecemos o valor mínimo que a função assume, podemos 
afirmar que a performance deste fora bem melhor que a do GA, e ainda, que ele fornece em 
seus dados uma precisão maior que aquele, podemos confirmar isto verificando o desvio padrão 
das fitness deste, que é nulo até a nona casa decimal. 
Já da mediana, podemos extrair o ponto central dos 10 mínimos encontrados pelos 
algoritmos, ambos tiveram a mediana em torno do ponto 𝑥 = 3.0 e 𝑦 = 2.0, mais uma vez 
podemos ver a diferença de precisão entra ambos se verificarmos a tabela. Assim valida-se a 
existência de um mínimo para a função neste ponto. Perceba também que este é o mínimo global 
encontrados pelo algoritmo (ver fitness na tabela 1). 
Vale lembrar que todos resultados até aqui foram obtidos com as configurações defaults 
do MATLAB, podemos ajudar o GA a encontrar resultados melhores adicionando a este uma 
restrição lateral, vamos definir o espaço de busca para o intervalo em que a função apresenta 
diversos mínimos locais, e para isto escolheremos valores de −5 para o limite inferior e 5 para 
superior (tanto para 𝑥, quanto para 𝑦). Isto se faz incrementando os dois vetores na parte do 
comando abaixo (que pode ser encontrada no script do anexo II): 
[x fval exitflag] = ga(@himmelblau,2,[],[],[],[],[-5 -5],[5 
5],[],[],options) 
 
 Assim, ao executar novamente o script do GA obtemos os seguintes dados: 
 
 
 
Tabela 2: Pontos ótimos e valores ótimos resultantes da otimização da função de Himmelblau com o 
GA com restrição lateral de -5 e 5. 
Ponto ótimo Himmelblau 
GA Fitness 
X Y GA 
2,999994 2,000003 1,11E-10 
-2,805114 3,131316 1,30E-09 
2,999997 1,999998 1,28E-09 
3,584438 -1,848142 5,62E-10 
3,000002 2,000000 7,34E-09 
2,999998 2,000002 1,35E-10 
2,999986 2,000029 1,25E-10 
-3,779300 -3,283181 1,32E-08 
2,999999 2,000003 6,08E-09 
 3,35E-09 Média 
2,999997 2,000002 1,28E-09 Mediana 
2,828423 2,147354 4,59E-09 
Desvio 
Padrão 
 
Observe que agora o GA encontrou todos os quatro mínimos (destacados em verde os 
mais precisos) e que todas as execuções forneceram um valor bem próximo aos conhecidos, a 
precisão média quando se trata dos pontos agora é da ordem da quarta casa decimal. Note que 
o desvio padrão das fitness encontrada é de magnitude nano. Uma melhora significativa se 
compararmos os dados com a tabela 1. 
Outro fator importante a ser lembrado é a moda, perceba que o ponto modal das 10 
execuções em ambos métodos fora o (3.0, 2.0). Como o método do PSO ao contrário do GA 
não gera uma nova população a cada iteração, e seus membros se locomovem no espaço de 
busca sobre influência também de um fator global (gbest) induziria que este ponto é onde se 
encontra o mínimo global da função (caso não tivéssemos conhecimento da função), uma vez 
também que para este obtivemos o menor valor de fitness. 
Perceba que as Metaheurísticas são um bom ferramental para encontrar mínimos locais, 
ao contrário dos métodos determinísticos que inicializam com um ponto e avançam no espaço 
de busca gradativamente utilizando alguma informação secundária da função (derivadas, por 
exemplo), as Metaheurísticas como o GA e o PSO inicializam seus cálculos com uma população 
de pontos, que é gerada aleatoriamente, o que alavanca uma dispersão da busca. Assim os 
 
algoritmos estão menos propensos a bacias de atração. É pelo padrão estocástico associado ao 
método, que ao executar encontramos resultados diferentes, e com isso também, mínimos 
diferentes. 
Questão 2 
 Essa questão foi desenvolvida com o aplicativo de otimização do MATLAB,com o 
solver “ga-algoritm genetic”, cuja especificações constam no apêndice I. 
 Para a otimização da função de Himmelblau já descrita aqui, experimentamos variar 
alguns parâmetros dos operadores do GA. As seguintes alterações nas configurações padrões 
foram feitas: 
Alteração 1: Aumento no tamanho da população, configurada para conter 100 indivíduos. 
Alteração 2: Mudança na taxa de crossover, configurada para 60 %. 
Alteração 3: Troca da função de mutação, selecionou-se a uniform com probabilidade padrão 
de 0,01. A função de mutação uniform se divide em duas etapas, em primeiro lugar o algoritmo 
seleciona uma porção do vetor de entrada bitstring de cada indivíduo para mutação, sendo que 
cada entrada tem a mesma probabilidade de ser selecionada e sofrer mutação (alternar entre 0 
e 1 no caso da codificação binária), escolheu-se a probabilidade padrão de 1%. No segundo 
passo substitui-se cada entrada selecionada pelo valor “sorteado” (0 ou 1). 
Observação: cada alteração fora feita separadamente, ou seja, os demais parâmetros 
permaneceram nos padrões. 
Resultados obtidos: 
Tabela 3: Dados de saída da otimização da função de Himmelblau com alteração dos parâmetros do 
GA. 
 Solução Ótima da Himmelblau 
Alteração 
GA 
X Y Fitness 
1 2,983000 2,014000 0,009333 
2 3,011000 1,985000 0,005154 
3 2,926000 2,321000 1,736943 
 2,973333 2,106667 0,583810 Média 
 3,011000 2,014000 0,009333 Mediana 
 
 0,103718 0,027514 0,786340 
Desvio 
Padrão 
 
 Nesta questão o algoritmo foi executado até que as três configurações encontrassem o 
mínimo (3.0, 2.0), para melhorar a comparação. Desta forma, a média, mediana e desvio padrão 
estão bem ajustadas. 
 A primeira alteração gerou um bom resultado, com uma população um pouco maior a 
diversidade de informações aumenta, isto pode ser bom quando o aumento é moderado. Além 
do mais, se a população aumenta, as regiões analisadas pelo algoritmo são maiores, inferindo 
indiretamente na precisão dos resultados. Pode-se ver a performance da execução na figura 
abaixo: 
 
Figura 1: Valor da Fitness e Distância Média entre os indivíduos (pontos) para a função de 
Himmelblau a cada geração, com 100 indivíduos cada. 
 Já a segunda alteração está relacionada à aleatoriedade maior, com 60% de crossover a 
quantidade de “características” adaptativas passadas a próxima geração diminui, uma vez que 
agora 40% dos indivíduos sofrem mutação. Ainda assim, um resultado não muito diferente da 
configuração anterior fora alcançado, mas perceba que se a taxa de mutação for alta, o algoritmo 
genético se torna em sua maioria aleatório e provavelmente de difícil convergência. Isto pode 
ser visto no aumento da distância média entre os indivíduos e na quantidade maior de gerações 
ilustradas no gráfico abaixo: 
 
 
Figura 2: Valor da Fitness e Distância Média entre os indivíduos (pontos) para a função de 
Himmelblau a cada geração, com 60% de taxa de crossover. 
A última alteração forneceu o pior resultado, a mutação com probabilidade uniforme e 
baixa (0,01) pode ter influenciado de maneira global na população, de forma que a parte que 
sofre mutação a cada geração não convirja. Ilustra o gráfico abaixo a performance extraída: 
 
 
Figura 3: Valor da Fitness e Distância Média entre os indivíduos (pontos) para a função de 
Himmelblau a cada geração, com função de mutação "uniform" padrão. 
 Apesar disto, os três resultados tiveram um desvio padrão relativamente baixo entre os 
valores dos pontos, e da fitness se deu quase da ordem de uma unidade, cortesia deste último 
resultado, se este não fosse levando em consideração seria da ordem de 0,004. Das medidas de 
tendência central, tanto a mediana como a média estão em torno do ponto mínimo conhecido, 
com precisão da segunda casa decimal. 
 
 
 
 
 
 
 
 
Questão 3 
Para a otimização da função de Rastringinsfcn utilizou-se dos scripts do GA e PSO 
(anexos II e III), alterando apenas a função fornecida como entrada no primeiro argumento do 
comando em ambos os códigos, da seguinte forma: 
... ga(@(x)rastriginsfcn(x/10), .....) 
... particleswarm((@(x)rastriginsfcn(x/10),....) 
Chama-se assim a função como anônima no MATLAB, e atribuo um valor para 5 na 
variável n. 
As execuções forneceram os seguintes resultados: 
Tabela 4:Resultados de otimização da função Rastriginsfcn utilizando os algoritmos GA e PSO. 
Ponto ótimo Rastriginsfcn 
GA PSO Fitness 
X Y X Y GA PSO 
-0,194880 -0,041591 -1,13E-07 -1,97E-08 0,078683 2,84E-14 
-0,072189 -0,015653 -9,62E-09 -2,95E-09 0,010823 0,00E+00 
-0,124224 0,027938 1,46E-06 -7,37E-06 0,032148 1,12E-10 
-0,097408 -0,006588 1,41E-06 2,63E-06 0,018904 1,76E-11 
-0,158796 -0,029108 -4,19E-06 -8,85E-07 0,051667 3,64E-11 
-0,129499 -0,013000 -2,87E-07 -1,13E-06 0,038445 3,32E-11 Média 
-0,124224 -0,015653 -9,62E-09 -1,97E-08 0,032148 1,76E-11 Mediana 
0,048670 0,026462 2,31E-06 3,73E-06 0,027287 4,65E-11 Desvio Padrão 
 É sabido que esta função possui o mínimo global em (0.0,0.0), onde o valor da função 
é nulo. Nos dados do GA podemos ver que cada execução forneceu um resultado em torno deste 
ponto, tanto que a média e mediana apontam este valor, sendo estas são poucos discrepantes 
entre si, além do desvio padrão ser decimal tanto para o valor dos pontos quanto para as fitness. 
O mesmo ocorre com o PSO, contudo perceba que o algoritmo é de uma precisão muito maior, 
como o algoritmo não destrói sua população a cada iteração, a informação do mínimo global é 
conservada a partir do momento que é descoberta e ao decorrer de um tempo acaba atraindo 
todos indivíduos para ela, estes ainda podem se locomover no espaço de busca, e por isto podem 
varrer mais afundo aquela região. 
 
 
APÊNDICES 
APÊNDICE I 
 
Figura 4: Aplicativo de otimização com o solver ga, chamado no console com o comando 
optimtool('ga'). 
Na aba Problem devemos informar a função a ser otimizada e o número de variáveis, 
nos campos Fitness function e Number of variables, respectivamente. Podemos restringir o 
espaço de busca do GA, isto se faz no campo Bounds, em que Lower é o limite inferior para as 
variáveis e Upper o superior para as mesmas, perceba que se tivermos mais de uma variável na 
função a entrada para estes parâmetros é na forma vetorial, por exemplo, [-50 -50] e [50 50] 
para Lower e Upper respectivamente. Desta forma, todo indivíduo gerado nos operadores do 
GA, ao fim do processo estarão dentro desse intervalo. 
Nas opções, podemos especificar a quantidade de indivíduos na população que o GA 
utilizará para varrer os espaço de busca, isto se faz no campo Population size (por padrão, é 
definido 50 indivíduos). No campo Initial range pode-se especificar os limites inferior e 
 
superior para os vetores de entrada dos indivíduos da população inicial, que é criada pelo GA. 
Vale ressaltar que a restrição configurada neste campo se aplicará apenas a população inicial. 
Quanto à reprodução dos indivíduos a cada geração, podemos configurar a taxa de 
crossover e a de mutação na aba Reproduction. Como vemos na figura abaixo, uma extensão 
da figura 1: 
 
 
Figura 5: Aba de opções do aplicativo de Otimização, para o solver ga - Genetic Algorithm. 
 
A taxa de crossover padrão é de 80% (0.8), sendo os 20% (0.2) restantes do operador 
mutação. Estas taxas definirão a quantidade da população que irá passar por crossover e a 
porção que sofrerá mutação. Ou seja, desta forma se configura os operadores genéticos que irão 
operar na reprodução de cada nova geração. Podemos especificar manualmente essas taxas, 
imprimindo no campo crossover fraction a porcentagem desejada (em número fracionado).ANEXOS 
ANEXO I 
function [z] = himmelblau(k) 
 z = (k(1)^2+k(2)-11).^2 +(k(1)+k(2)^2-7).^2; 
end 
 
ANEXO II 
 
%% Universidade Federal do Oeste do Pará % 
% Programa de Ciência e Tecnologia % 
% Inteligência Computacional % 
% Prof. Dr. Anderson Meneses 
% Discente: Endrew Henrique Barreto 
 
%% GA por linha de comando %% 
 
%[x fval exitflag] = ga(@himmelblau,2) % Otimiza a função informada, 
 % vetores/valores de saída da 
 % função: x (ponto ótimo), 
 % fval (valor ótimo). Dados de 
 % entrada: ga(função,número de 
 % variáveis) 
 
 
 
%% Laço de iteração para o GA %% 
 
% Caso queira executar o GA diversas vezes e obter vários valores de 
% fitness, descomenta-se o código abaixo. 
 
n = 10; % números de vezes que o GA será executado; 
 
fitnessga = zeros(n,1); % vetor que armazenará os valores da fitness para 
 % cada geração 
 
pontootimoga = zeros(n,2);% vetor que armazena o valor das 
 % variáveis no ponto ótimo (x,y) 
 
for i = 1:n 
 options = gaoptimset('CrossoverFraction',0.75); 
 [x fval exitflag] = ga(@himmelblau,2,[],[],[],[],[],[],[],[],options) 
 fitnessga(i) = fval; 
 pontootimoga(i,1) = x(1); 
 pontootimoga(i,2) = x(2); 
 
end 
 
 
 
 
 
 
ANEXO III 
 
%% Universidade Federal do Oeste do Pará % 
% Programa de Ciência e Tecnologia % 
% Inteligência Computacional % 
% Prof. Dr. Anderson Meneses 
% Discente: Endrew Henrique Barreto 
 
%% PSO por linha de comando 
%% 
 
% rng default % For reproducibility 
% [x,fval,exitflag] = particleswarm(@himmelblau,2) % Otimiza a função 
informada, 
 % vetores/valores de saída da 
 % função: x (ponto ótimo), 
 % fval (valor ótimo). Dados de 
 % entrada: ga(função,número de 
 % variáveis) 
 
 
%% Laço de iteração para o PSO %% 
 
% Caso queira executar o GA diversas vezes e obter vários valores de 
% fitness, descomenta-se o código abaixo. 
 
n = 10; % números de vezes que o GA será executado; 
 
fitnesspso = zeros(n,1); % vetor que armazenará os valores da fitness para 
 % cada geração 
 
pontootimopso = zeros(n,2); % vetor que armazena o valor das 
 % variáveis no ponto ótimo (x,y) 
for i = 1:n 
 
 options = optimoptions('particleswarm','SwarmSize',50); 
 [x fval exitflag] = particleswarm(@himmelblau, 2, [],[],options) 
 fitnesspso(i) = fval; 
 pontootimopso(i,1) = x(1); 
 pontootimopso(i,2) = x(2); 
end