G検定 ノーフリーランチ定理

株式会社リュディアです。今回はノーフリーランチ定理についてまとめたいと思います。

ノーフリーランチ、という名の通り「ただ飯はない」という意味ですが、なぜこのような定理が発表されたのでしょうか？これは汎用組合せ最適化手法が流行した時代背景と関係があります。

組合せ最適化問題を直感的に説明すると大域的最適解を求める方法が総当たりのみであるような問題です。有名な問題に巡回セールスマン問題があります。指定されたすべての都市を一度だけ訪問する際に、どのような順序で回るのがよいかを求める問題です。

1990年代後半にメタヒューリスティックスと呼ばれる汎用手法を様々な組み合わせ最適化問題に適用し、最適解では無いにしても十分によい結果が得られることを示す論文が多数発表されました。シミュレーテッドアニーリング、遺伝的アルゴリズム (GA)、タブサーチ、またニューラルネットワークの世界からもホップフィールド型やボルツマンマシンが適用されました。一時はどの方法が最も優れているという議論に終始する論文が多数発表されましたが、結論としては「平均的にはどの方法がよい、という優劣はない」ということが示されました。これがノーフリーランチ定理です。

ただ誤解をしないでいただきたいのは、どの方法を使っても結果は同じというわけではなく、実際には各問題の性質を利用した処理を組み込んだり、解空間を削減するなど工夫を盛り込みます。ノーフリーランチ定理はもう汎用的な最適化手法の優劣を比較するのはやめようという提案であって、問題の性質を理解し適用しやすい方法を選ぶことは計算速度、利用メモリサイズなどの計算機資源の観点からも重要であることは理解してください。

では、ごきげんよう。