Development of the method for estimating calculation efficiency of Genetic Algorithms by means of Markov process theory

利用马尔可夫过程理论估计遗传算法计算效率的方法的发展

• 批准号: 21500219
• 负责人: FURUTANI Hiroshi
• 金额: $ 2.58万
• 依托单位: University of Miyazaki
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500219/
• 关键词: 進化計算; マルコフ過程; 計算効率; 遺伝的アルゴリズム; マルコフ連鎖; スキーマ理論; 収束時間; 非対称突然変異; 成功確率; 最適解出現時間

Recently, it is widely recognized the efficiency of Genetic Algorithms(GAs). However, the theoretical investigation of GA calculation process is still far from satisfactory level. In this study, we carried out mathematical analysis of GA calculation by using Markov process theory. To this end, we divided the GA into sub-problems called schema analysis, and developed methods to estimate the convergence time of GA calculation and probability of obtaining desired solution. We also studied the relations between these quantities and GA parameters such as mutation rate and population size.

近年来，遗传算法的效率得到了广泛的认可。然而，对遗传算法计算过程的理论研究还远远没有达到令人满意的水平。在本研究中，我们利用马尔可夫过程理论对遗传算法进行了数学分析。为此，我们将GA分解为模式分析的子问题，并提出了估计GA计算的收敛时间和获得期望解的概率的方法。我们还研究了这些量与遗传算法参数如变异率和种群大小的关系。

项目成果

Markov chain analysis of Genetic Algorithms for 3-SAT problem

3-SAT 问题遗传算法的马尔可夫链分析

• 发表时间: 2011
• 期刊: Proceedings of 7th International Conference on Natural Computation
• 作者: Q. Ma;Y. Zhang;K. Yamamori;M. Sakamoto;H. Furutani
• 通讯作者: H. Furutani

OneMax問題における収束予測時間の検討

OneMax问题收敛预测时间的考虑

• 发表时间: 2012
• 作者: 古賀仁信;坂本眞人;古谷博史
• 通讯作者: 古谷博史

Stochastic analysis of One-Max problem by using Markovchain

使用马尔可夫链对 One-Max 问题进行随机分析

• 发表时间: 2012
• 期刊: Proceedings of the 17th Int. Symposium on Artificial Life and Robotics
• 作者: Q. Ma;Y. Zhang;K. YamamoriM. Sakamoto and H. Furutani
• 通讯作者: K. YamamoriM. Sakamoto and H. Furutani

OneMax問題と非対称突然変異の関係について

关于OneMax问题和不对称变异的关系

• 发表时间: 2011
• 作者: 古賀仁信;馬青蓮;坂本眞人;古谷博史
• 通讯作者: 古谷博史

Stochastic Analysis of OneMax Problem by Using Markov Chain

利用马尔可夫链随机分析 OneMax 问题

• 发表时间: 2012
• 期刊: Proceedings of the 17th International Symposium on Artificial Life and Robotics
• 作者: Q.Ma;K.Koga;K.Yamamori;M.Sakamoto;H.Furutani
• 通讯作者: H.Furutani