Oliver Giel
Abstract. 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(nn) for all objective functions {0,1}n->Rm. 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(n3). Moreover, the runtime is O(n3) with an overwhelming probability. Finally, the function x->(x2, (x-2)2) that serves as a test function in the continuous decision space is adapted to the boolean decision space, and bounds on the runtime are derived.