文献

J-GLOBAL ID：202002245481161925   整理番号：20A1863761

ドミノ収束は,線形関数上の山登りを一つすべきか【JST・京大機械翻訳】

Domino convergence why one should hill-climb on linear functions

著者 (1件)： Witt Carsten (DTU Compute, Technical University of Denmark, Denmark)
資料名： ACM Proceedings  (ACM Proceedings)
号： GECCO ’18  ページ： 1539-1546  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 進化的計算の理論コミュニティにおいて,線形擬似ボレア関数は,それらの全てが簡単な不偏アルゴリズムによって期待時間O(nlogn)で最適化できるので,しばしば容易な問題と見なされる。しかし,遺伝的アルゴリズムと推定-分布アルゴリズムの結果は,これらのアルゴリズムが異なる線形関数を異なって処理することを示した。より正確には,「ドーム収束」と呼ばれる効果を文献において記述し,線形関数における大きな重みのビットが,低重みのビットよりも早く最適化されることを意味する。したがって,異なる線形関数は,むしろ異なる予想最適化時間をもたらす。本論文はドミノ収束の研究を行う。厳密なランタイム解析により,ドミノ収束は,主に遺伝的アルゴリズムとEDAの根底にあるクロスオーバーの結果であることを示した。ここでは,異なる線形関数間の次数Ω(n/logn)の性能ギャップを証明した。単純な突然変異のみのEAにおいて,ドミノ収束の影響はそれほど顕著ではなく,典型的な性能ギャップは個体群サイズにおいて対数的であった。個体群サイズ1が使用されるとき,効果は消えて,アルゴリズムは山登りに縮小する。カットとトーナメント選択を含む異なる選択機構を調べ,ドミノ収束に及ぼすそれらの影響を解析した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  最適化 ,  コミュニティ ,  突然変異 ,  線形性 ,  個体群 ,  対数 ,  遺伝的アルゴリズム ,  進化的計算
準シソーラス用語： 実行時間 ,  トーナメント ,  *線形関数 , 【Automatic Indexing@JST】

著者キーワード (4件)： 分布アルゴリズムの推定 ,  遺伝的アルゴリズム ,  実行時間解析 ,  理論

分類 (1件)： システム最適化手法  (IA02050Z)

タイトルに関連する用語 (3件)： 収束 ,  線形関数 ,  山登り