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/sup n/) for all objective functions {0,1}/sup n/ /spl rarr/ R/sup 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/sup 3/). Moreover, the runtime is O(n/sup 3/) with an overwhelming probability.

1 Introduction

Randomized search heuristics are applied to optimization problems in situations where problem-specific algorithms are not available. The lack of such algorithms can have various reasons. Problem-specific algorithms might be unknown for the considered problem, there might be not enough time and not enough experts to devise a problem-specific algorithm, or there might be only little knowledge about the structure of the problem. General search heuristics that do not employ problem-specific knowledge are of particular interest in theoretical investigations. In applications, these heuristics are often combined with problem-specific modules. Evolutionary algorithms (EAs) are such randomized search heuristics. They are not only applied to single-objective optimization problems but also to multi-objective optimization problems. Practical knowledge on the design of multi-objective EAs has increased considerably in recent years but theoretical works are rare. A common approach to learn how EAs work is to analyze basic EAs. In this work, we analyze the expected runtime of a very simple but fundamental multi-obiective EA.