進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析

• Item type: SIG Technical Reports(1)
• 公開日: 2012-11-29
• タイトル: 進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析
• タイトル / 言語: en
• タイトル: Analysis of convergence time using Markov chain for OneMax problem in evolutionary computation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 宮崎大学工学研究科
• 著者所属: 宮崎大学工学部
• 著者所属: 宮崎大学農学工学総合研究科
• 著者所属: 宮崎大学工学部
• 著者所属: 宮崎大学工学部
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, University of Miyazaki
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, University of Miyazaki
• 著者所属(英): en
• 著者所属(英): Interdisciplinary Graduate School of Agriculture and Engineering, University of Miyazaki
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, University of Miyazaki
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, University of Miyazaki
• 著者名: 古賀, 仁信; 安永, 和馬; 馬, 青蓮; 坂本, 眞人; 古谷, 博史
• 著者名(英): Kiminobu, Koga; Kazuma, Yasunaga; Qinglian, Ma; Makoto, Sakamoto; Hiroshi, Furutani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 進化計算を実際の問題に適用する場合，その計算時間を予測することは非常に重要である．本論文では， OneMax 問題の収束時間を Markov 連鎖モデルを用いて解析した結果について報告する．最初に， OneMax 問題の進化過程を Markov 連鎖モデルの一つである Wright-Fisher モデルを用いて記述し，その遷移行列を計算する．次に，集団が連鎖平衡にある場合， OneMax 問題が非対称突然変異モデルと同等であることを示す．非対称突然変異モデルは集団遺伝学でよく研究されており，遷移行列の固有値はすでに知られている．我々は，その結果から OneMax 問題における遷移行列の固有値の解析的な形を導いた． Markov 連鎖の定常状態への収束時間は，遷移行列の 2 番目に大きい固有値を用いることで理論的に予測することができる．得られた理論的予測値と平均適応度の収束時間を実験的に比較し，よい一致が得られること示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In applying Evolutionary Computation (EC) to realistic problems, it is very important to estimate their computational times. In this paper, we report the results obtained by Markov chain model for the convergence time of OneMax problem. First, we describe the evolution process of OneMax problem within the framework of Wright-Fisher model, which is a version of Markov chain, and calculate its transition matrix. Next, we show that, if a population is in linkage equilibrium, OneMax problem is equivalent to the asymmetric mutation model. The asymmetric mutation model is well studied in population genetics, and the eigenvalues of its transition matrix were already known. From this result, the analytical form of eigenvalues of transition matrix for OneMax problem can be obtained. In Markov chain theory, the convergence time of Markov chain can be estimated by using the second largest eigenvalue of the transition matrix. We compare this theoretical estimation with the convergence time of average fitness, and show that the agreement is very good.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2012-MPS-91, 号 35, p. 1-6, 発行日 2012-11-29
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会