ノーフリーランチ定理とは? わかりやすく解説

Weblio 辞書 > 固有名詞の種類 > 方式・規則 > 理論・法則 > 定理・公理 > 定理 > ノーフリーランチ定理の意味・解説 

ノーフリーランチ定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/05 23:45 UTC 版)

ノーフリーランチ定理(ノーフリーランチていり、no-free-lunch theoremNFL)は、物理学者 David H. Wolpert と William G. Macready が生み出した組合せ最適化の領域の定理である。その定義は以下のようになる。

……コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる — Wolpert and Macready、1995年

解説

この定理の名称は、ハインラインのSF小説『月は無慈悲な夜の女王』(1966年)で有名になった格言"There ain't no such thing as a free lunch."に由来する。かつて酒場で「飲みに来た客には昼食を無料で振る舞う」という宣伝が行われたが、「無料の昼食」の代金は酒代に含まれていて実際には「無料の昼食」なんてものは有る訳がないだろう、という意味である。格言自体はハインラインの創作ではなく、1949年には既に用例がある。TANSTAAFL(タンスターフルと発音)というアクロニムも同作品で広まったが、これも表現自体は以前からある[1]

この定理は数学的にありうべき全ての問題の集合について、どの探索アルゴリズムも同じ平均性能を示すことを説明したものである。これは、探索アルゴリズムに必ず何らかの偏向があるため、そのアルゴリズムが前提としている事が問題に当てはまらないことがあるからである。

ノーフリーランチ定理の概念図。高度に最適化された特殊アルゴリズム(赤)と汎用アルゴリズム(青)。どちらも平均すれば同程度の性能となることに注意。

右の図はノーフリーランチ定理を視覚化した例である。

一方、この定理は「あらゆる問題で性能の良い汎用最適化戦略は理論上不可能であり、ある戦略が他の戦略より性能がよいのは、現に解こうとしている特定の問題に対して特殊化(専門化)されている場合のみである」ということを立証している(Ho and Pepyne、2002年)。

この定理は、問題領域に関する知識を使わずに遺伝的アルゴリズム焼きなまし法などの汎用探索アルゴリズムを使うことに反対する論拠として使われる。他の汎用アルゴリズムにも適用されてきたが、一般にノーフリーランチ定理でカバーできない実世界の大きなサブセットを構築することも可能である。ノーフリーランチ定理は全てのコスト関数を対象として成立するものである。このため、コスト関数の真部分集合には適用できない。実際の問題解決への適用には、この点での制限をうける。

工学者や最適化の専門家にとって、この定理は、問題領域の知識を可能な限り使用して最適化すべきだということを示しており、領域を限定して特殊な最適化ルーチンを作成すべきであることを示している。

脚注

  1. ^ 参考文献:
    Martin, Gary (1996–2009). “There's no such thing as a free lunch” (英語). The Phrase Finder. 2009年6月2日閲覧。
    Wilton, Dave (2009年). “free lunch” (英語). Wordorigins.org. 2009年6月2日閲覧。

外部リンク


ノーフリーランチ定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/12/10 02:26 UTC 版)

メタヒューリスティクス」の記事における「ノーフリーランチ定理」の解説

ノーフリーランチ定理によって平均的にはどの探索手法も同じ性能であることが示され以来、「最も優れたメタヒューリスティクス」を求めることは無意味であることが示されている。この定理はしばしば「万能探索アルゴリズム存在しない」と表現されることがあり、メタヒューリスティクス対すアンチテーゼとして用いられる。 しかしノーフリーランチ定理はあくまで「全ての問題対す平均」であり問題空間ある程度まで限定した時の性能善し悪し論ずることはできない。また実際にメタヒューリスティックス実装する場合は、探索効率上げるためその問題事前知識をさらに組み込んだりする例が多くある。それゆえ、この定理のみによってメタヒューリスティクスそのもの不要論投げかけることはできない

※この「ノーフリーランチ定理」の解説は、「メタヒューリスティクス」の解説の一部です。
「ノーフリーランチ定理」を含む「メタヒューリスティクス」の記事については、「メタヒューリスティクス」の概要を参照ください。

ウィキペディア小見出し辞書の「ノーフリーランチ定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ノーフリーランチ定理」の関連用語

ノーフリーランチ定理のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ノーフリーランチ定理のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのノーフリーランチ定理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのメタヒューリスティクス (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS