A multiset model of multi-species evolution to solve big deceptive problems
This work addresses optimization of big deceptive problems for evolutionary computation researchers, representing a strong incremental improvement over existing symbiotic algorithms.
The authors tackled the challenge of optimizing large deceptive problems by integrating symbiogenesis with a multiset genetic algorithm, resulting in SMuGA, which achieved results one order of magnitude better than state-of-the-art symbiotic algorithms and demonstrated linear scaling in iterations to reach the optimum.
This chapter presents SMuGA, an integration of symbiogenesis with the Multiset Genetic Algorithm (MuGA). The symbiogenetic approach used here is based on the host-parasite model with the novelty of varying the length of parasites along the evolutionary process. Additionally, it models collaborations between multiple parasites and a single host. To improve efficiency, we introduced proxy evaluation of parasites, which saves fitness function calls and exponentially reduces the symbiotic collaborations produced. Another novel feature consists of breaking the evolutionary cycle into two phases: a symbiotic phase and a phase of independent evolution of both hosts and parasites. SMuGA was tested in optimization of a variety of deceptive functions, with results one order of magnitude better than state of the art symbiotic algorithms. This allowed to optimize deceptive problems with large sizes, and showed a linear scaling in the number of iterations to attain the optimum.