mk:cec04

Summary

No-Free-Lunch theorems and the diversity of algorithms. Mario Köppen. Evolutionary Computation, 2004. CEC2004?. Congress on, 1:235-241 Vol.1, 19-23 June 2004.

Abstract

In this paper, the no-free-lunch theorem is extended to subsets of functions. It is shown that for algorithm a performing better on a set of functions than algorithm b, three has to be another subset of functions on which b performs better in average than a. to achieve a performance evaluation for an algorithm, it is not sufficient to demonstrate its better performance on a given set of functions. Instead of this, the diversity of an algorithm is considered in this paper in more detail. The total number of possible algorithms is computed and compared with the number of algorithms instances that a random search or a population-based algorithm can have. It comes out that the number of different random searches is very small in comparison to the total number of algorithms. On the other hand, population-based algorithms are principally able to cover the set of all possible algorithms. The smaller variance of algorithm performance, measured by the repeated application of the algorithm under different settings on different random sets of functions, comes out to be a value reflecting the higher count of instances.

Bibtex entry

@ARTICLE { mk:cec04,
    ABSTRACT = { In this paper, the no-free-lunch theorem is extended to subsets of functions. It is shown that for algorithm a performing better on a set of functions than algorithm b, three has to be another subset of functions on which b performs better in average than a. to achieve a performance evaluation for an algorithm, it is not sufficient to demonstrate its better performance on a given set of functions. Instead of this, the diversity of an algorithm is considered in this paper in more detail. The total number of possible algorithms is computed and compared with the number of algorithms instances that a random search or a population-based algorithm can have. It comes out that the number of different random searches is very small in comparison to the total number of algorithms. On the other hand, population-based algorithms are principally able to cover the set of all possible algorithms. The smaller variance of algorithm performance, measured by the repeated application of the algorithm under different settings on different random sets of functions, comes out to be a value reflecting the higher count of instances. },
    AUTHOR = { Mario Köppen },
    ADDED = { 2008-02-28 13:50:22 +0900 },
    MODIFIED = { 2008-02-28 13:59:32 +0900 },
    DOI = { 10.1109/CEC.2004.1330862 },
    HASABSTRACT = { Yes },
    JOURNAL = { Evolutionary Computation, 2004. CEC2004?. Congress on },
    KEYWORDS = { optimisation, random processes, search problems algorithm performance evaluation, no-free-lunch theorems, population-based algorithm, random function sets, random search algorithm },
    MONTH = { 19-23 June },
    PAGES = { 235-241 Vol.1 },
    PDF = { cec04.pdf },
    TITLE = { No-Free-Lunch theorems and the diversity of algorithms },
    VOLUME = { 1 },
    YEAR = { 2004 },
    1 = { http://dx.doi.org/10.1109/CEC.2004.1330862 },
}