Hitting Time Analysis of OneMax Problem in Genetic Algorithm

被引：0
作者：
Du, Yifei [1 ]
Ma, QinLian [2 ]
Aoki, Kenji [3 ]
Sakamoto, Makoto [4 ]
Furutani, Hiroshi [4 ]
Zhang, Yu-an [5 ]
机构：
[1] Miyazaki Univ, Grad Sch Engn, Gakuen Kibanadai Nishi 1-1, Miyazaki, Miyazaki Prefec 8892192, Japan
[2] Miyazaki Univ, Interdisciplinary Grad Sch Agr & Engn, Miyazaki, Japan
[3] Miyazaki Univ, Informat Technol, Miyazaki, Miyazaki Prefec 8892192, Japan
[4] Miyazaki Univ, Fac Engn, Miyazaki, Miyazaki Prefec 8892192, Japan
[5] Qinghai Univ, Dept Comp Sci & Technol, Xining 810016, Qinghai Provinc, Peoples R China
来源：
JOURNAL OF ROBOTICS NETWORKING AND ARTIFICIAL LIFE | 2015年 / 2卷 / 02期
关键词：
genetic algorithms; OneMax problem; Markov model; convergence time; hitting time;
D O I：
10.2991/jrnal.2015.2.2.14
中图分类号：
TP24 [机器人技术];
学科分类号：
080202 ; 1405 ;
摘要：
Genetic algorithms (GAs) are stochastic optimization techniques, and we have studied the effects of stochastic fluctuation in the process of GA evolution. A mathematical study was carried out for GA on OneMax function within the framework of Markov chain model. We treated the task of estimating convergence time of the Markov chain for OneMax problem. Then, in order to study hitting time, we study the state after convergence.
引用
收藏
页码：131 / 134
页数：4
相关论文
共 50 条
  • [1] Hitting Time Analysis of OneMax Problem in Genetic Algorithm
    Du, Yifei
    Ma, QinLian
    Aoki, Kenji
    Sakamoto, Makoto
    Furutani, Hiroshi
    Zhang, Yu-an
    PROCEEDINGS OF INTERNATIONAL CONFERENCE ON ARTIFICIAL LIFE AND ROBOTICS (ICAROB2015), 2015, : 323 - 326
  • [2] Runtime Analysis of OneMax Problem in Genetic Algorithm
    Du, Yifei
    Ma, QinLian
    Sakamoto, Makoto
    Furutani, Hiroshi
    Zhang, Yu-an
    JOURNAL OF ROBOTICS NETWORKING AND ARTIFICIAL LIFE, 2014, 1 (03): : 225 - 230
  • [3] Runtime Analysis of OneMax Problem in Genetic Algorithm
    To, Ichihi
    Ma, QuinLian
    Sakamoto, Makoto
    Furutani, Hiroshi
    Zhang, Yu-an
    PROCEEDINGS OF INTERNATIONAL CONFERENCE ON ARTIFICIAL LIFE AND ROBOTICS (ICAROB 2014), 2014, : 157 - 161
  • [4] Diffusion model analysis of OneMax problem
    Ma, QingLian
    Koga, Kiminobu
    Yamamori, Kunihito
    Sakamoto, Makoto
    Furutani, Hiroshi
    Zhang, Yu-an
    PROCEEDINGS OF THE EIGHTEENTH INTERNATIONAL SYMPOSIUM ON ARTIFICIAL LIFE AND ROBOTICS (AROB 18TH '13), 2013, : 37 - 40
  • [5] A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
    Doerr, Benjamin
    Doerr, Carola
    GECCO'15: PROCEEDINGS OF THE 2015 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2015, : 1423 - 1430
  • [6] Stochastic analysis of OneMax problem by using Markov chain
    Ma, QingLian
    Zhang, Yu-an
    Koga, Kiminobu
    Yamamori, Kunihito
    Sakamoto, Makoto
    Furutani, Hiroshi
    PROCEEDINGS OF THE SEVENTEENTH INTERNATIONAL SYMPOSIUM ON ARTIFICIAL LIFE AND ROBOTICS (AROB 17TH '12), 2012, : 141 - 145
  • [7] Stochastic analysis of OneMax problem using Markov chain
    Ma, QingLian
    Zhang, Yu-an
    Koga, Kiminobu
    Yamamori, Kunihito
    Sakamoto, Makoto
    Furutani, Hiroshi
    ARTIFICIAL LIFE AND ROBOTICS, 2013, 17 (3-4) : 395 - 399
  • [8] Variable length genetic algorithms with multiple chromosomes on a variant of the onemax problem
    Cavill, Rachel
    Smith, Stephen L.
    Tyrrell, Andy M.
    GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2, 2006, : 1405 - +
  • [9] On the inverse of the first hitting time problem for bidimensional processes
    Lefebvre, M
    JOURNAL OF APPLIED PROBABILITY, 1997, 34 (03) : 610 - 622
  • [10] A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows
    Giselher Pankratz
    OR Spectrum, 2005, 27 : 21 - 41
12345