A No Free Lunch theorem for multi-objective optimization

被引：49

作者：

Service, Travis C. ^{[1
]}

机构：

[1] Vanderbilt Univ, Nashville, TN 37240 USA

来源：

INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 21期

关键词：

Analysis of algorithms; Combinatorial optimization; No Free Lunch; Multi-objective optimization;

D O I：

10.1016/j.ipl.2010.07.026

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The No Free Lunch theorem (Schumacher et al., 2001; Wolpert and Macready, 1997 [8,10]) is a foundational impossibility result in black-box optimization stating that no optimization technique has performance superior to any other over any set of functions closed under permutation. This paper considers situations in which there is some form of structure on the set of objective values other than the typical total ordering (e.g., Pareto dominance in multi-objective optimization). It is shown that in such cases, when attention is restricted to natural measures of performance and optimization algorithms that measure performance and optimize with respect to this structure, that a No Free Lunch result holds for any class of problems which is structurally closed under permutation. This generalizes the Sharpened No Free Lunch theorem of Schumacher et al. (2001) [8] to non-totally ordered objective spaces. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：917 / 923

页数：7

共 12 条

[1]

[Anonymous], 2001, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-2001

[2]

Corne D, 2003, IEEE C EVOL COMPUTAT, P2506

[3]

Corne DW, 2003, LECT NOTES COMPUT SC, V2632, P327

[4] A fast and elitist multiobjective genetic algorithm: NSGA-II [J].