Algoritmo genético de chaves aleatórias segundo distribuição de Levy para otimização global

Abstract

A otimização global tem como objetivo encontrar um mínimo ou máximo de uma função em um domínio discreto ou contínuo. Esta técnica possui aplicabilidade em diversas áreas do conhecimento, tais como física, biologia, engenharia, administração, economia, entre outras, que apresentam problemas passíveis de serem representados por meio de modelagens matemáticas. Uma classe de algoritmos utilizada para resolver este tipo de problema são os algoritmos genéticos, que se baseiam nos processos de evolução darwinistas para selecionar as melhores soluções dentro de uma população de soluções candidatas. O Algoritmo Genético de Chaves Aleatórias Viciadas, do inglês Biased Random-Key Genetic Algorithm (BRKGA), proposto por Gonçalves e Resende (2011), é uma variação de algoritmos genéticos que consiste em representar as soluções de um problema como vetores de chaves reais definidas por valores gerados aleatoriamente no intervalo contínuo [0,1) e utiliza um decodificador determinístico para mapear estes vetores em soluções viáveis para o problema. Neste trabalho, foi investigado o impacto da substituição da distribuição uniforme, utilizada na geração de chaves aleatórias do BRKGA tradicional, pela utilização da distribuição de Levy (PAUL, 1937). Esta variação foi inserida no BRKGA tradicional e em uma hibridização do algoritmo com a inserção de um procedimento de busca local, proposto por Silva et al. (2013a). Posteriormente, as versões propostas foram comparadas com as versões da literatura e também com a metaheurística C-GRASP, que já possui resultados satisfatórios para este tipo de problema. Os experimentos foram realizados utilizando-se para tal um conjunto de funções de benchmark de otimização global unimodais e multimodais, utilizadas como funções-base para o IEEE CEC Competition e presentes também em diversos trabalhos da área de pesquisa. Os algoritmos foram comparados em termos de desempenho e qualidade das soluções e a variação proposta conseguiu alcançar resultados bastante competitivos em relação às demais técnicas.