著者

橋谷 祐司 櫻川 貴司

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.3, pp.1-8, 2010-02-26

参考文献数

7

---

本稿では,確率的アルゴリズムを用いた場合における No Free Lunch 定理 (NFL定理) を厳密に証明する.NFL 定理からは 「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」 ということを示唆する定理であり,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている.NFL 定理は 「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」 ということが帰結される定理で,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている.本稿では確率的アルゴリズムを形式的に定義し,いくつかの補題を示した上で確率的アルゴリズムの場合の NFL 定理を確率論によって厳密に証明する.In this paper, a rigorous proof of No Free Lunch Theorem (NFLT) for stochastic algorithms is presented. NFLT shows that there is no algolithm which can solve every optimization problem efficiently. A lot of research papers on optimization problems and search algorithms refer to it. We give a formal definition of stochastic algorithm, prove some lemmas and then complete a regourous proof of NFLT for stochastic algorithms using probability theory.