Greedy Versus Curious Parent Selection for Multi-objective Evolutionary Algorithms

From the literature we know that simple evolutionary multi-objective algorithms can optimize the classic two-objective test functions OneMinMax and CountingOnesCountingZeroes in \(O(n^2\log n)\) expected time. We extend this result to any pair of generalized OneMax functions and show that, if the optima of the two functions are d apart, then (G)SEMO has an expected optimization time of \(O(dn \log (n) )\) . In an attempt to achieve better optimization times, some algorithms consider parent selection. We show that parent selection based on the curiosity-based novelty search can improve the optimization time to \(O(n^2)\) on OneMinMax. By contrast, we show that greedy parent selection schemes can be trapped with an incomplete Pareto front for superpolynomial time. Finally, we provide experimental results on the two-objective optimization of linear functions.