Analysis on the Efficiency of Multifactorial Evolutionary Algorithms

摘要

Many experimental studies have demonstrated the superiority of multifactorial evolutionary algorithms (MFEAs) over traditional methods of solving each task independently. In this paper, we investigate this topic from theoretical analysis aspect. We present a runtime analysis of a (4+2) MFEA on several benchmark pseudo-Boolean functions, which include problems with similar tasks and problems with dissimilar tasks. Our analysis results show that, by properly setting the parameter rrrvp (i.e., the random mating probability), for the group of problems with similar tasks, the upper bound of expected runtime of the (4+2) MFEA on the harder task can be improved to be the same as on the easier one. As for the group of problems with dissimilar tasks, the expected upper bound of (4+2) MFEA on each task are the same as that of solving them independently. This study theoretically explains why some existing MFEAs perform better than traditional methods in experimental studies and provides insights into the parameter setting of MFEAs.