No Free Lunch Theoremの別証明と解釈

• Item type: SIG Technical Reports(1)
• 公開日: 2005-03-17
• タイトル: No Free Lunch Theoremの別証明と解釈
• タイトル / 言語: en
• タイトル: Simple Proof and Interpretation of No Free Lunch Theorem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院新領域創成科学研究科基盤情報学専攻
• 著者所属: 東京大学大学院新領域創成科学研究科基盤情報学専攻
• 著者所属(英): en
• 著者所属(英): Dept. of Frontier Infomatics Graduate School of Frontier Sciences The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Dept. of Frontier Infomatics Graduate School of Frontier Sciences The University of Tokyo
• 著者名: 柳井, 孝介; 伊庭, 斉志
• 著者名(英): Kohsuke, Yanai; Hitoshi, Iba
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿ではNo Free Lunch Treorem （NFL）の別証明を与える．NFL は「どんな問題に対しても平均的に効率良く解けるような探索アルゴリズムは存在しない」ということを主張する定理であり，探索アルゴリズムあるいは最適化法の研究に大きな影響を与えた．本稿では，より簡潔でかつ直観的な証明を与える．我々は評価関数の空間を部分集合に分割し，それぞれの部分集合ごとにパフォーマンスが得られる確率を合計する．関数空間の分割により，定理のより深い理解が可能となり，またアルゴリズムと問題の関係が明確となる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, a simple proof of No Free Lunch Theorem (NFL) is presented. NFL asserts that no search algorithm exists which can solve every problem efficiently. This theorem has serious implications for the study of search algorithms and optimization. The proof given in this paper is simpler and more intuitive than the original one. In the proof, we divide the fitness function space into a set of subsets, and calculate the sum of probabilities in each subset. The division of the function space helps us to understand the theorem more clearly and highlights the relationship between algorithms and problems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 26(2004-AL-100), p. 1-8, 発行日 2005-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会