The effect of cost distributions on evolutionary optimization algorithms

According to the No-Free-Lunch theorems of Wolpert and Macready, we cannot expect one generic optimization technique to outperform others on average. For every optimization technique there exist ``easy'' and ``hard'' problems. However, only little is known as to what criteria determine the particular difficulty of a problem. In this paper, we address this question from an evolutionary computing point of view. We use cost distributions, i.e., the frequencies of the objective function's values occurring in the search spaces, to devise a classification of optimization problems. We scrutinize the influence of cost distributions on the single algorithmic components of evolutionary computing. Our analysis helps identifying (1) problems where evolutionary algorithms are overhead, (2) problems where evolutionary algorithms are highly suitable optimization algorithms, as well as (3) problems that pose difficulties for evolutionary techniques.