About: ノーフリーランチ定理

ノーフリーランチ定理（ノーフリーランチていり、no-free-lunch theorem、NFLT）は、物理学者 David H. Wolpert と William G. Macready が生み出した組合せ最適化の領域の定理である。その定義は以下のようになる。 ……コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる — Wolpert and Macready、1995年 この定理の名称は、ハインラインのSF小説『月は無慈悲な夜の女王』（1966年）で有名になった格言の"There ain't no such thing as a free lunch."に由来する。 数学的にありうべき全ての問題の集合について、どの探索アルゴリズムも同じ平均性能を示すことを説明したものである。これは、探索アルゴリズムに必ず何らかの偏向があるため、そのアルゴリズムが前提としている事が問題に当てはまらないことがあるからである。 右の図はノーフリーランチ定理を視覚化した例である。 一方、この定理は「あらゆる問題で性能の良い汎用最適化戦略は理論上不可能であり、ある戦略が他の戦略より性能がよいのは、現に解こうとしている特定の問題に対して特殊化（専門化）されている場合のみである」ということを立証している（Ho and Pepyne、2002年）。