Leonardo Tadeu Ribeiro Pereira
Resumo
O algoritmo Evolução Diferencial (DE) é um método computacional incluído na classe dos Algoritmos Evolutivos (EA), proposto em 1996 para resolver problemas de otimização complexos, em espaços reais contínuos. A partir de 2005, muitas variantes do DE estiveram entre os três principais algoritmos nas competições IEEE CEC em anos sucessivos. Este sucesso do DE deveu-se em grande parte à popularidade das estratégias auto-adaptativas e algumas hibridizações, como foi o caso do JADE/EIG, a combinação de um novo DE auto-adaptativo (JADE) com um novo operador de cruzamento, este baseado nas direções principais da matriz de covariância da população (EIG). O JADE/EIG resolve rapidamente, em poucas gerações, os problemas unimodais presentes no benchmark do CEC 2014. No entanto, para alguns problemas multimodais, o método fica estagnado, revelando assim a fragilidade de sua exploração. Dificuldade esta não demonstrada pelo IPOP-CMAES, vencedor do CEC na antiga edição de 2005, quando usado para solucionar o mesmo grupo de funções do CEC 2014. Inspirado então na capacidade exploratória do IPOP-CMAES, uma técnica de reinício controlado do DE foi incorporada ao JADE/EIG. Este procedimento identifica a estagnação do DE e reinicia aleatoriamente toda a população, sem alterar seu tamanho. O algoritmo híbrido resultante foi denominado neste trabalho como CR-JADE/EIG. Testes mostram que o método proposto encontrou os melhores resultados para todos os problemas do benchmark do CEC 2014 em que o critério de reinício foi acionado, em comparação com os resultados do JADE/EIG. Fica o desafio de criar critérios que identifiquem estagnações do DE para um maior número de problemas.
Abstract
The Differential Evolution (DE) algorithm is a computational method included in the class of Evolutionary Algorithms (EA), proposed in 1996 to solve complex optimization problems in continuous real spaces. DE is one of the most popular, successful and studied EAs for over two decades. Since 2005, many DE variants were among the top three algorithms in IEEE CEC competitions in successive years. This DE success was due in large part to the popularity of self-adaptive strategies and some hybridizations, as was the case with JADE/EIG, the combination of a new self-adaptive DE (JADE) with a new crossover operator, based on the main directions of the population covariance matrix (EIG). JADE/EIG quickly finds the minimum of the unimodal CEC 2014 competition functions, in a few generations of the algorithm run. However, for some multimodal problems, the algorithm stagnates, thus revealing the fragility of its exploitation. Nevertheless, the 2005 CEC competition winner IPOP-CMAES algorithm didn’t show any stagnation when solving the 2014 CEC functions. Inspired then by the exploratory capacity of the IPOP-CMAES, a controlled restart technique of DE was incorporated into JADE/EIG. This procedure identifies DE stagnation and randomly restarts the entire population, without changing its size. The resulting hybrid algorithm was named in this work CR-JADE/EIG. Tests showed that the proposed method found consistently better solutions if compared to JADE/EIG ones for all CEC 2014 functions where the restart criterion was triggered. The challenge remains to identify further stagnation criteria to cope with a greater number of problems.