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

CNPqA 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.Global optimization aims to find a minimum or maximum of a function in a discrete or continuous domain. This technique has applicability in several areas of knowledge, such as physics, biology, engineering, administration, economics, among others, that present problems that can be represented through mathematical models. One class of algorithms used to solve this type of problem is genetic algorithms, which rely on Darwinian evolutionary processes to select the best solutions within a population of candidate solutions. Biased Random-Key Genetic Algorithm (BRKGA), proposed by Gonçalves e Resende (2011), is a variation of genetic algorithms that consists of representing the solutions of a problem as real-key vectors defined by randomly generated values in the continuous interval [0 , 1) and uses a deterministic decoder to map these vectors into feasible solutions to the problem. In this work, was investigated the impact of the substitution of the uniform distribution, used in the generation of traditional BRKGA random keys, by the use of the Levy distribution (PAUL, 1937). This variation was inserted in the traditional BRKGA and in a hybridization of the algorithm with the insertion of a local search procedure, proposed by Silva et al. (2013a). Subsequently, the proposed versions were compared with the literature versions and also with the C-GRASP metaheuristic, which already presents satisfactory results for this type of problem. The experiments were performed using a set of unimodal and multimodal global optimization benchmark functions, used as base functions for the IEEE CEC Competition and also present in several works of the research area. The algorithms were compared in terms of performance and quality of the solutions and the proposed variation managed to achieve very competitive results in relation to the other techniques