確率的アルゴリズムの場合のNo Free Lunch定理の厳密な証明
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,確率的アルゴリズムを用いた場合における No Free Lunch 定理 (NFL定理) を厳密に証明する.NFL 定理からは 「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」 ということを示唆する定理であり,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている.NFL 定理は 「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」 ということが帰結される定理で,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている.本稿では確率的アルゴリズムを形式的に定義し,いくつかの補題を示した上で確率的アルゴリズムの場合の NFL 定理を確率論によって厳密に証明する.
- 2010-02-26