First Mathematical Runtime Analyses of Evolutionary Multitask Multi-Objective Optimization

To facilitate the solving of complex problems, evolutionary multitask optimization is regarded as a promising technique due to its capacity for cross-task knowledge transfer. In contrast to empirical evidences, no mathematical runtime support exists for this technique within the domain of multi-objective optimization. In this work, we aim to fill this important gap. We analyze how the representative multiobjective multifactorial evolutionary algorithm (MO-MFEA) covers the Pareto fronts of two bi-objective problems simultaneously. For the two-task problem of maximizing the classic bi-objective OMM and the multimodal OJZJ benchmarks, the MO-MFEA requires only an expected runtime of $O(n^2\log n)$—the same as optimizing the simple OMM alone—yet achieves a speedup by a factor of $\mathrm{\Theta }(n^{k-1}\mathrm{/}\log n)$ compared to optimizing OJZJ alone (with gap size $k$). Similarly, for the task pair comprising the classic LOTZ and the multimodal DLTB benchmarks, a speedup of $\mathrm{\Theta }(n)$ is attained over optimizing DLTB alone, while the runtime matches that of optimizing LOTZ alone.