Algoritmo evolucionário multi-objetivo dinâmico com estratégia de previsão no espaço objetivo

Abstract

Os Algoritmos Evolucionários (EA) têm sido amplamente explorados e aplicados em problemas de otimização. Nos ambientes dinâmicos, a solução ótima se modifica e o algoritmo de otimização deve encontrá-la ao longo do tempo. Nestas situações, se o tempo disponível entre as alterações dos objetivos for relativamente curto, não haverá tempo hábil para a convergência do algoritmo entre as mudanças. Estudos indicam que um algoritmo bem-sucedido deve produzir algum tipo de diversidade para poder escapar de um conjunto de soluções e convergir rapidamente para um novo conjunto, à medida que as mudanças ocorram no ambiente. Diferentes algoritmos foram propostos modificando a maneira como uma mudança é manipulada. Entre eles, os métodos baseados em previsão têm se mostrado promissores em acelerar a convergência dos EA dinâmicos. Eles fornecem orientação para a evolução da população por meio de um mecanismo de previsão que ajuda o EA a responder rapidamente à nova mudança. Com base nessas estratégias, propomos um algoritmo dinâmico baseado na Evolução Diferencial (DE) com Previsão no Espaço Objetivo (Dynamic Non-dominated Sorting Differential Evolution improvement with Prediction in the Objective Space: DOSP-NSDE). DOSP-NSDE é um algoritmo baseado em Pareto e em aprendizagem. A aprendizagem é introduzida no algoritmo a través de uma estratégia de Previsão de Espaço do Objetivo (OSP). O OSP identifica tendências nos movimentos de indivíduos não dominados no espaço objetivo, e então rapidamente encontra regiões promissoras no espaço de busca e gera uma nova população considerando essas regiões. DOSP-NSDE aciona a estratégia OSP quando várias premissas baseadas na métrica Hipervolume Aproximado são alcançadas. Os operadores de variação do DE e a mutação polinomial são usados para produzir a descendência sempre que a condição de OSP não é satisfeita. A proposta usa a estratégia de previsão tanto no processo evolucionário estático (entre mudanças) como no mecanismo de reação à mudança para prever a nova localização da frente ótima. Primeiramente, a eficácia do OSP foi verificada no processo estático. Para isto, foram realizados um conjunto de experimento em 31 funções de múltiplos objetivos bem conhecidas, comparando com algoritmos baseados em EA e outros da inteligência coletiva. Comprovada a eficácia e a eficiência da proposta em ambientes estáticos, foram realizados experimentos em 19 funções de teste multiobjetivas dinâmicas e em um problema do mundo real. As comparações do DOSP-NSDE com diversos algoritmos da literatura considerando três métricas evidenciaram que a proposta é competitiva na maioria dos problemas.