ノーフリーランチ定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ノーフリーランチ定理（-ていり、no-free-lunch theorem、NFLT）は、物理学者 David H. Wolpert と William G. Macready が生み出した組合せ最適化の領域の定理である。その定義は以下のようになる。
- ……コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適応した結果を平均すると同じ性能となる。(Wolpert and Macready、1995年)
この定理の名称はロバート・A・ハインラインの『月は無慈悲な夜の女王』に出てくる格言（"There ain't no such thing as a free lunch"、略称 TANSTAAFL）から来ている。数学的にありうべき全ての問題の集合について、どの探索アルゴリズムも同じ平均性能を示すことを説明したものである。これは、探索アルゴリズムに必ず何らかの偏向があるため、そのアルゴリズムが前提としている事が問題に当てはまらないことがあるからである。
右の図はノーフリーランチ定理を視覚化した例である。
一方、この定理は「あらゆる問題で性能の良い汎用最適化戦略は理論上不可能であり、ある戦略が他の戦略より性能がよいのは、現に解こうとしている特定の問題に対して特殊化（専門化）されている場合のみである」ということを立証している（Ho and Pepyne、2002年）。
この定理は、問題領域に関する知識を使わずに遺伝的アルゴリズムや焼きなまし法などの汎用探索アルゴリズムを使うことに反対する論拠として使われる。他の汎用アルゴリズムにも適用されてきたが、一般にノーフリーランチ定理でカバーできない実世界の大きなサブセットを構築することも可能である。ノーフリーランチ定理は全てのコスト関数を対象として成立するものである。このため、コスト関数の真部分集合には適用できない。実際の問題解決への適用には、この点での制限をうける。
工学者や最適化の専門家にとって、この定理は、問題領域の知識を可能な限り使用して最適化すべきだということを示しており、領域を限定して特殊な最適化ルーチンを作成すべきであることを示している。
