Coevolutionary strategies at the collective level for improved generalism

In many complex practical optimization cases, the dominant characteristics of the problem are often not known prior. Therefore, there is a need to develop general solvers as it is not always possible to tailor a specialized approach to each application. The previously developed multilevel selection genetic algorithm (MLSGA) already shows good performance on a range of problems due to its diversity-first approach, which is rare among evolutionary algorithms. To increase the generality of its performance, this paper proposes utilization of multiple distinct evolutionary strategies simultaneously, similarly to algorithm selection, but with coevolutionary mechanisms between the subpopulations. This distinctive approach to coevolution provides less regular communication between subpopulations with competition between collectives rather than individuals. This encourages the collectives to act more independently creating a unique subregional search, leading to the development of coevolutionary MLSGA (cMLSGA). To test this methodology, nine genetic algorithms are selected to generate several variants of cMLSGA, which incorporates these approaches at the individual level. The mechanisms are tested on 100 different functions and benchmarked against the 9 state-of-the-art competitors to evaluate the generality of each approach. The results show that the diversity divergence in the principles of working of the selected coevolutionary approaches is more important than their individual performances. The proposed methodology has the most uniform performance on the divergent problem types, from across the tested state of the art, leading to an algorithm more likely to solve complex problems with limited knowledge about the search space, but is outperformed by more specialized solvers on simpler benchmarking studies.

Automated summary

This study proposes a new coevolutionary multilevel selection genetic algorithm (cMLSGA) that incorporates multiple distinct evolutionary strategies simultaneously. The results show that diversity divergence in the selected coevolutionary approaches is more important than their individual performances.