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 条
  • [21] A genetic algorithm for the multidimensional knapsack problem
    Chu, PC
    Beasley, JE
    JOURNAL OF HEURISTICS, 1998, 4 (01) : 63 - 86
  • [22] Genetic algorithm for the job shop problem
    Croce, Federico Della
    Tadei, Roberto
    Volta, Giuseppe
    Computers and Operations Research, 1995, 22 (01): : 15 - 24
  • [23] A genetic algorithm for the project assignment problem
    Harper, PR
    de Senna, V
    Vieira, IT
    Shahani, AK
    COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (05) : 1255 - 1265
  • [24] A Genetic Algorithm for the Multidimensional Knapsack Problem
    P.C. Chu
    J.E. Beasley
    Journal of Heuristics, 1998, 4 : 63 - 86
  • [25] A genetic algorithm for the set covering problem
    Beasley, JE
    Chu, PC
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 94 (02) : 392 - 404
  • [26] A genetic algorithm for the channel assignment problem
    Smith, KA
    GLOBECOM 98: IEEE GLOBECOM 1998 - CONFERENCE RECORD, VOLS 1-6: THE BRIDGE TO GLOBAL INTEGRATION, 1998, : 2013 - 2018
  • [27] An adaptive genetic algorithm for the clustering problem
    Chen, QZ
    He, WX
    Mao, KJ
    PROGRESS IN INTELLIGENCE COMPUTATION & APPLICATIONS, 2005, : 38 - 43
  • [28] Solving Knapsack Problem with Genetic Algorithm
    Uslu, Faruk Sukru
    2015 23RD SIGNAL PROCESSING AND COMMUNICATIONS APPLICATIONS CONFERENCE (SIU), 2015, : 1062 - 1065
  • [29] A Genetic Algorithm for Solving a. Container Storage Problem Using a Residence Time Strategy
    Serban, Cristina
    Carp, Doina
    STUDIES IN INFORMATICS AND CONTROL, 2017, 26 (01): : 59 - 66
  • [30] A hybrid genetic algorithm for the discrete time-cost trade-off problem
    Sonmez, Rifat
    Bettemir, Onder Halis
    EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (13) : 11428 - 11434
12345