Diversity-driven migration strategy for distributed evolutionary algorithms applied to large-scale optimization problems

Abstract

Large-Scale Global Optimization (LSGO) Problems usually have thousands of decision variables and can be extremely complicated to solve using traditional metaheuristics. To deal with these problems, distributed models have been successfully employed by many Evolutionary Algorithms (EAs) over the past decade. These models provide means to enable collaboration between multiple islands (subpopulations), thus allowing to design strategies to deal with premature convergence and loss of diversity. Through introducing periodic migrations, many Distributed Evolutionary Algorithms (DEAs) have been proposed to improve the balance between exploration and exploitation. In this work, we present a diversity-based migration mechanism, in which the moment to perform the migrations is determined by assessing the loss of diversityof the islands. We call this strategy Diversity-driven Migration Strategy (DDMS). Focusing on large-scale global optimization problems, we built DDMS into a Cooperative Co-evolutionary (CC) model and used DE/best/1 and SHADE as optimizers. We test DDMS by sending the best individual and call it DDMS-BEST. To compete with the DDMS-BEST, we create a strategy to try to ensure that the migrant individual is capable of generating a diversity that helps a given island to explore new regions without harming its health. For that, we use an online clustering algorithm called TEDA-Cloud to generate clouds of good fitness individuals that have been previously migrated. In this strategy, the individual to be migrated must be extracted from a cloud whose population distribution is sufficiently different from the population distribution of the requesting island. We call it DDMS-TEDA. Using the CEC’2013 large-scale optimization test suite with 1000 decision variables, we compare DDMS against traditional migration strategies, namely, fixed and probabilistic interval migrations. Computational experiments with different scenarios showed that incorporating the DDMS strategy in a Cooperative Co-evolution Distributed Evolutionary Algorithm (CCDEA) led to better results. Considering the average error values, we show that both DDMS-BEST and DDMS-TEDA are better in the vast majority of functions and scenarios tested. Regarding the diversity, we showed that DDMS-TEDA gets better results in 100% of the functions. In Appendix A of this text, we also highlight the promising results of the DDMS-TEDA in scenarios with 50 and 100 variables.