Algoritmos Evolutivos para a Otimização Dinâmica de um Problema Discreto com muitos Objetivos

Abstract

Many real-world optimization problems are dynamic and involve multiple objectives.Different studies using evolutionary algorithms focus on these characteristics individually, but few studies investigate problems that are dynamic and multi-objective at the same time. Recent studies investigate dynamic multi-objective optimization problems (DMOPs), which adds an additional challenge to the convergence of the search. Although widely explored in multi-objective formulations for static problems, evolutionary approaches are still challenged by DMOPs defining a relevant research topic. Some evolutionary strategies for DMOPs emerged from the adaptation of multi-objective algorithms previously created to solve static continuous optimization problems. In this work, we propose new dynamic multiobjective evolutionary algorithms (DMOEAs), namely: D-MEANDS, D-MEANDS-MD, D-MEANDS-II and D-MEANDS-III. These algorithms are based on the MEANDS and MEANDS-II algorithms, originally proposed to solve static and discrete problems, and incorporate dynamic strategies based on memory and diversity to deal with dynamic optimizations. We also investigate new evolutionary mechanisms that aim to work more efficiently with the subpopulations employed in the proposed approaches. A dynamic multiobjective version of the knapsack problem, known as Dynamic Multiobjective Knapsack Problem (DMKP), is used to evaluate the performance of the different algorithms. The DMKP instances are subject to environmental variations throughout the execution of the evolutionary optimization, being subjected to up to 20 environmental changes throughout the evolution. The behavior of such algorithms was evaluated in dynamic instances with up to 8 objectives. Experimental results showed that the proposed algorithms compete with DMOEAs from the literature, achieving superior performance in the evaluated multi-objective metrics, in most of the investigated scenarios.