遺伝的アルゴリズムにおける最適解出現世代数のマルコフ連鎖による予測

• Item type: SIG Technical Reports(1)
• 公開日: 2009-12-10
• タイトル: 遺伝的アルゴリズムにおける最適解出現世代数のマルコフ連鎖による予測
• タイトル / 言語: en
• タイトル: Estimation of the First Appearing Generation of Optimum Solution in Genetic Algorithm by Markov Chains
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 宮崎大学大学院農学工学総合研究科
• 著者所属: 宮崎大学工学部
• 著者所属: 宮崎大学工学部
• 著者所属: 宮崎大学工学部
• 著者所属(英): 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
• 著者所属(英): Faculty of Engineering, University of Miyazaki
• 著者名: 張, 玉安; 馬, 青蓮; 坂本, 眞人; 古谷, 博史
• 著者名(英): Yu-an, Zhang; Qing, LingMa; Makoto, Sakamoto; Hiroshi, Furutani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 遺伝的アルゴリズム （GA） の計算過程を理論的に解明するためには，計算時間の研究が重要である．GA はマルコフ連鎖を用いて解析できることが知られている．本研究では，集団が連鎖平衡にあることを仮定し，Hunter により提案された mixing time Tm の計算式を用い，集団の分布が定常分布に収束する時間を Wright-Fisher モデルを用いて計算した．また，我々は最近成功確率 S の理論的計算法を提案した．ここで S は定常分布において集団中に少なくとも一つの最適解が存在する確率と定義する．我々は最適解出現世代数の平均値を T としたとき，T ≦ Tm ＋ 1/S の関係があると予測した．この理論的予測と数値実験を比較した結果について報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is important to study the computing time for explaining calculation process of Genetic Algorithm (GA) theoretically. It is usually considered that GA can be analyzed by Markov Chain. In this paper, we assume that the population is in linkage equilibrium, and calculate the time of convergence to stationary distribution by means of Wright-Fisher model, using the formula of mixing time Tm proposed by Hunter. Recently, the calculation of success probability is proposed theoretically. Here, we define the success probability S that there is at least one optimum solution in a population in the stationary distribution. We consider the average generation time of optimum solution T, and propose the prediction method of T with the relation of T ≦ Tm + 1/S: We compared this theoretical prediction with numerical experiments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12055912
• 書誌情報: 研究報告バイオ情報学（BIO）; 巻 2009-BIO-19, 号 10, p. 1-7, 発行日 2009-12-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会