Addressing Evolutionary-Based Dynamic Problems: A New Methodology for Evaluating Immigrants Strategies in MOGAs

Multi-Objective Genetic Algorithms (MOGAs) have been successfully used to address dynamic problems in a wide variety of domains. In these domains, data changes over time, so a non-static analysis is required to obtain feasible solutions. In this type of environments, MOGAs are often time-consuming and require special adaptation to work properly. A number of different techniques have been proposed to adapt MOGAs to dynamic environments for tackling the previous problems such as hypermutation, memory and immigrant schemes or multi-population methods, among others. In particular, immigrant strategies are one of the most commonly used methods, for that reason, this work proposes a new methodology that allows to make a detailed evaluation of their performance when these strategies are used. The proposed methodology works on two levels, a coarse-grain one and a fine-grain one. In the former, an overall evaluation of the different immigrant strategies is made based on three different dimensions: Quality, Stability and Speed. In the latter, a detailed study of the status of the immigrant individuals during the evolution of the algorithm is carried out. This is a very relevant aspect to take into account in order to evaluate whether an immigrant strategy is working properly or not. To deploy this methodology, a new visualization technique for population mixing analysis is proposed in this work. In order to validate the proposed methodology, a test case in the context of the Dynamic Community Detection problem (DCD) has been selected using a MOGA that applies several different immigrant schemes, showing both how the methodology works and how it could be employed in a particular dynamic problem.

Automated summary

Multi-Objective Genetic Algorithms (MOGAs) have been successfully applied to dynamic problems in various domains, but they often require special adaptation to work properly in such environments. Different techniques, including immigrant strategies, have been proposed to address the challenges of dynamic environments. This work proposes a new methodology that evaluates the performance of immigrant strategies in two levels: coarse-grain evaluation based on quality, stability, and speed, and fine-grain study of the status of immigrant individuals during the algorithm evolution. A visualization technique for population mixing analysis is also proposed. The proposed methodology is validated in the context of the Dynamic Community Detection problem.