Expected runtimes of a simple multi-objective evolutionary algorithm

The expected runtime of a simple multi-objective evolutionary algorithm for the Boolean decision space is analyzed. The algorithm uses independent bit flips as mutation operator and, therefore, searches globally. It is proved that the expected runtime is O(nⁿ) for all objective functions {0,1}ⁿ → R^m. This worst-case bound is tight and matches the worst-case bounds for fundamental evolutionary algorithms working in the scenario of single-objective optimization. For the bicriteria problem LOTZ (leading ones trailing zeroes), it is shown that the expected runtime is O(n³). Moreover, the runtime is O(n³) with an overwhelming probability.