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

• Item type: Trans(1)
• 公開日: 2013-08-21
• タイトル: 進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析
• タイトル / 言語: en
• タイトル: Analysis of Convergence Time Using Markov Chain for OneMax Problem in Evolutionary Computation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] 進化計算，遺伝的アルゴリズム，マルコフ連鎖，収束時間，OneMax問題
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 宮崎大学大学院工学研究科
• 著者所属: 宮崎大学工学部
• 著者所属: 宮崎大学大学院農学工学総合研究科
• 著者所属: 宮崎大学工学部
• 著者所属: 宮崎大学工学部
• 著者所属: 中国青海大学コンピュータ技術・応用工学科
• 著者所属(英): 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
• 著者所属(英): en
• 著者所属(英): Department of Computer Technology and Applications, Qinghai University
• 著者名: 古賀, 仁信; 安永, 和馬; 馬, 青蓮; 坂本, 眞人; 古谷, 博史; 張, 玉安
• 著者名(英): Kiminobu, Koga; Kazuma, Yasunaga; Qinglian, Ma; Makoto, Sakamoto; Hiroshi, Furutani; Yu-an, Zhang
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 進化計算を実際の問題に適用する場合，その計算時間を予測することは非常に重要である．本論文では，OneMax問題の収束時間をMarkov連鎖モデルを用いて解析した結果について報告する．最初に，OneMax問題の進化過程をMarkov連鎖モデルの1つである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 / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 6, 号 2, p. 16-24, 発行日 2013-08-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会