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.