  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.
