A diversity-driven migration strategy for distributed evolutionary algorithms

The increasing complexity of real-world problems raises new challenges to evolutionary computation. Distributed models have been successfully employed by many evolutionary algorithms (EAs) to deal with these challenges. In particular, distributed models provide a means to enable collaboration between multiple subpopulations, thus allowing the design of strategies to deal with premature convergence and loss of diversity, which are common problems in traditional evolutionary algorithms. Through introducing periodic migrations, many Distributed Evolutionary Algorithms (DEAs) have been proposed to improve the balance between exploration and exploitation. However, most of them focus on performing migrations at fixed or probabilistic intervals. In this work, we present a mechanism to estimate the moment of executing the migrations by assessing the loss of diversity of the subpopulations. Another relevant issue is that most studies choose to migrate the best or a random individual. We report a strategy that identifies a migrant individual capable of generating diversity that helps a given subpopulation explore non-visited regions without harming its health. The proposed approach uses an online clustering algorithm to create clouds of good fitness individuals that have been previously migrated. The solution to be migrated must be extracted from a cloud whose population distribution is sufficiently different from the population distribution of the original subpopulation. We called this approach a Diversity-driven Migration Strategy (DDMS). The efficiency of DDMS is experimentally compared against traditional migration strategies (fixed and probabilistic) on the CEC'2014 test suite. Considering the average error values for the objective function, the proposed approach is specially better in 50D and 100D (dimensional) instances. Regarding the diversity, the proposed strategy is better in 100% and about 96% of the test functions in 50D and 100D scenarios, respectively. In general, we have found the DDMS mechanisms to be of considerable benefit, especially in more complex problems such as the ones based on hybrid and composition objective functions.

Automated summary

The increasing complexity of real-world problems has presented new challenges to evolutionary computation. Distributed models have been utilized by evolutionary algorithms to address these challenges and improve the balance between exploration and exploitation. This study proposes a diversity-driven migration strategy (DDMS) that uses an online clustering algorithm to assess the loss of diversity and migrate individuals capable of generating diversity.