2024-03-28T17:20:08Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000948252020-10-27T05:02:56Z00934:00989:07128:07246
進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析Analysis of Convergence Time Using Markov Chain for OneMax Problem in Evolutionary Computationjpn[オリジナル論文] 進化計算,遺伝的アルゴリズム,マルコフ連鎖,収束時間,OneMax問題http://id.nii.ac.jp/1001/00094806/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=94825&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan宮崎大学大学院工学研究科宮崎大学工学部宮崎大学大学院農学工学総合研究科宮崎大学工学部宮崎大学工学部中国青海大学コンピュータ技術・応用工学科古賀, 仁信安永, 和馬馬, 青蓮坂本, 眞人古谷, 博史張, 玉安進化計算を実際の問題に適用する場合,その計算時間を予測することは非常に重要である.本論文では,OneMax問題の収束時間をMarkov連鎖モデルを用いて解析した結果について報告する.最初に,OneMax問題の進化過程をMarkov連鎖モデルの1つであるWright-Fisherモデルを用いて記述し,その遷移行列を計算する.次に,集団が連鎖平衡にある場合,OneMax問題が非対称突然変異モデルと同等であることを示す.非対称突然変異モデルは集団遺伝学でよく研究されており,遷移行列の固有値はすでに知られている.我々は,その結果からOneMax問題における遷移行列の固有値の解析的な形を導いた.Markov連鎖の定常状態への収束時間は,遷移行列の2番目に大きい固有値を用いることで理論的に予測することができる.得られた理論的予測値と平均適応度の収束時間を実験的に比較し,良い一致が得られること示す.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.AA11464803情報処理学会論文誌数理モデル化と応用(TOM)6216242013-08-211882-77802013-08-15