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 条

[31] Hyper-heuristic genetic algorithm for vehicle routing problem with soft time windows
Han Y.
Peng Y.
Wei H.
Shi B.
Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, 2019, 25 (10): : 2571 - 2579
[32] A genetic algorithm for the vehicle routing problem
Baker, BM
Ayechew, MA
COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (05) : 787 - 800
[33] Nearly Linear Time Algorithm for Mean Hitting Times of Random Walks on a Graph
Zhang, Zuobai
Xu, Wanyue
Zhang, Zhongzhi
PROCEEDINGS OF THE 13TH INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING (WSDM '20), 2020, : 726 - 734
[34] HITTING TIME FOR BESSEL PROCESSES-WALK ON MOVING SPHERES ALGORITHM (WOMS)
Deaconu, Madalina
Herrmann, Samuel
ANNALS OF APPLIED PROBABILITY, 2013, 23 (06) : 2259 - 2289
[35] The Experimental Analysis of the Efficiency of Genetic Algorithm Based on 3-satisfiability Problem
Zhang, Yu-an
Li, Bingfen
Meng, Qiao
Hu, Qiongqiong
Ma, Qinglian
2015 11TH INTERNATIONAL CONFERENCE ON NATURAL COMPUTATION (ICNC), 2015, : 245 - 249
[36] HITTING TIMES FOR SHAMIR'S PROBLEM
Kahn, Jeff
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2022, 375 (01) : 627 - 668
[37] A genetic algorithm solution to the unit commitment problem
Kazarlis, SA
Bakirtzis, AG
Petridis, V
IEEE TRANSACTIONS ON POWER SYSTEMS, 1996, 11 (01) : 83 - 90
[38] A genetic algorithm approach for the cutting stock problem
Godfrey C. Onwubolu
Michael Mutingi
Journal of Intelligent Manufacturing, 2003, 14 : 209 - 218
[39] Adaptive Genetic Algorithm in the Application of Assignment Problem
Liu Zeshuang
Duan Xiaoliang
PROCEEDINGS OF THE 15TH INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT, VOLS A-C, 2008, : 1642 - 1646
[40] Guided Genetic Algorithm for the Influence Maximization Problem
Kromer, Pavel
Nowakova, Jana
COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 630 - 641

← 1 2 3 4 5 →