Otimização de funções utilizando algoritmos genéticos no aplicativo MS
Excel
Miquéias Augusto Ferreira Nantes
Aluno do curso de Matemática – Licenciatura da Universidade Anhanguera – Uniderp CEP: 79003-010 –
Campo Grande, MS
[email protected] m
Celso Correia de Souza1 , José Francisco dos Reis Neto2
1
Professor dos Programas de Mestrados em Meio A mb iente e Desenvolvimento Regional e em Produção e
Gestão Agroindustrial da Universidade Anhanguera – Uniderp. 2 Professor do Curso de Admin istração da
Universidade Anhanguera - Un iderp.
csouza939@g mail.co m; [email protected]
RESUMO
Problemas de otimização de funções são bastante conhecidos e estudados intensivamente em
cursos de graduação, na disciplina de Cálculo Diferencial. Para a aplicação do Cálculo Diferencial na
otimização de uma função, é necessário que a mesma seja definida e derivável no espaço de busca, o
que nem sempre é possível assegurar. Existem vários métodos iterativos na literatura para a
resolução desse problema, mas a maioria deles está atrelado à derivada da função [2].
A técnica dos Algoritmos Genéticos, modelo matemático pertencente às metas-heurísticas, é
eficiente na busca de soluções otimizadas, ou aproximadamente ótimas, numa grande variedade de
problemas, dado que não possuem as diversas das limitações encontradas nos métodos tradicionais
de busca, como a exigência da derivada da função [3].
Algoritmos Genéticos são algoritmos de busca estocásticos que têm desenvolvimento e
funcionamento vinculados à genética, em que todas as novas espécies são produzidas por meio de
uma seleção natural em que o mais aptos sobrevivem, gerando descendentes.
Cada individuo na população representa uma possível solução para um dado problema, o que
o Algoritmo Genético faz é buscar aquela solução que seja muito boa ou a melhor do problema,
analisado através da criação de população de indivíduos cada vez mais aptos, levando à otimização
da função [2].
Cada iteração dos Algoritmos Genéticos corresponde à aplicação de um conjunto de quatro
operações básicas: cálculo de aptidão (avaliar população); seleção; cruzamento e mutação. Ao fim
destas operações cria-se uma nova população, chamada de geração que, espera-se, representa uma
melhor aproximação da solução do problema que a população anterior [1].
Os critérios para a parada podem ser vários, desde o número de gerações já criadas até o grau
de convergência da população (por convergência entende-se o grau de proximidade da avaliação de
cada indivíduo da população). O grau de convergência é característica das populações dos
Algoritmos Genéticos, e diz respeito à diferença entre a média de adaptação da geração atual e
suas anteriores [3].
Este trabalho de pesquisa teve como objetivo otimizar funções sujeitas a restrições em seu
conjunto de busca, com o auxílio dos Algoritmos Genéticos na forma binária, com a utilização do
aplicativo MS Excel.
O problema minimizado foi uma função não-linear de duas variáveis x e y no domínio de
busca considerado (Eq. 1).
2
(Eq. 1)
Min F ( y, x)  x 2  y 2  3x  4 y  26
 0  x  10
.
0  y  20
Sujeita a: 
1103
A entrada de dados (população inicial) constou de 20 indivíduos dispostos em uma planilha
Excel (Quadro 1).
Quadro 1: População inicial em x e y, os seus correspondentes binários e os correspondentes valores
aptidões
das
.
Nas duas primeiras colunas foram geradas duas populações aleatórias para x e para y, em
seguida, na terceira e na quarta coluna, os números decimais foram transformados em códigos
binários, depois os valores das populações de x e de y foram colocados dentro de intervalo para
serem substituídas na função. Como o problema é de mínimo ( Fmin ), calculou-se na última coluna
do Quadro 1 os valores de 1 / F , para a aplicação do algoritmo de maximização, para que fossem
usadas as planilhas já formatadas. Após dezoito iterações, feitas em planilhas MS Excel, o algoritmo
convergiu para o ótimo da função (Eq. 1), obtendo-se x *  3, y *  4 e Fmax  0,0385 . No Quadro 2
estão representados somente 4 elementos após a convergência, mesmo porque todas as 20 linhas são
perfeitamente iguais, caracterizando a convergência.
Legenda: População( X, Y): são as melhores encontradas num espaço de busca entre 0 à 500; Código Binário: as populações foram
transformadas em números binários para aplicação do algoritmo genético; Intervalo: os intervalos de x e de y são os que nos interessa
para serem substituídos na função F( x, y): é o resultado mínimo com os valores do intervalo substituídos na função
Os Algoritmos Genéticos podem ser aplicados em uma série de problemas de difíceis otimizações,
quando não existe nenhuma outra técnica especifica para resolver o problema. Assim, pode-se citar:
otimização de funções numéricas em geral (de uma ou mais variáveis); otimização combinatória tais
como o problema do caixeiro viajante, o problema clássico da mochila e o problema de
empacotamento; alocação de recursos; e aprendizado de máquina
.
Palavra chave: Otimização não linear, Algoritmo Genético, MS Excel
REFERÊNCIAS
[1] Goldbarg, M. C. e PACCA, H. L. L. Otimização Combinatória e Programação Linear: Modelos e
Algoritmos. Rio de Janeiro: Editora Campus, 2000.
[2] R, Linden. “Algoritmos genéticos” Rio de Janeiro: Brasport, 2008.
[3] G. V. R, Viana. “Metas-heuristicas e programação paralela em otimização combinatória”,
Fortaleza: EUFC, 1998.
1104
1105