Runtime Analysis of OneMax Problem in Genetic Algorithm

被引：2

作者：

Du, Yifei ^{[1
]}

Ma, QinLian ^{[2
]}

Sakamoto, Makoto ^{[3
]}

Furutani, Hiroshi ^{[3
]}

Zhang, Yu-an ^{[4
]}

机构：

[1] Univ Miyazaki, Grad Sch Engn, Gakuen Kibanadai Nishi 1-1, Miyazaki, Miyazaki 8892192, Japan

[2] Univ Miyazaki, Interdisciplinary Grad Sch Agr & Engn, Miyazaki, Miyazaki 8892192, Japan

[3] Univ Miyazaki, Fac Engn, Miyazaki, Miyazaki 8892192, Japan

[4] Qinghai Univ, Dept Comp Sci & Technol, Xining, Qinghai, Peoples R China

来源：

JOURNAL OF ROBOTICS NETWORKING AND ARTIFICIAL LIFE | 2014年 / 1卷 / 03期

关键词：

genetic algorithms; schema theory; OneMax problem; Markov model; convergence time;

D O I：

10.2991/jrnal.2014.1.3.12

中图分类号：

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 obtained the steady state solution, which represents a distribution of the first order schema frequency. We treated the task of estimating convergence time of the Markov chain for OneMax problem, and studied the effects of mutation probability and string length on the convergence time.

引用

页码：225 / 230

页数：6

共 8 条

[1] [Anonymous], 2008, MARKOV CHAINS MIXING
[2] The variant call format and VCFtools
Danecek, Petr
Auton, Adam
Abecasis, Goncalo
Albers, Cornelis A.
Banks, Eric
DePristo, Mark A.
Handsaker, Robert E.
Lunter, Gerton
Marth, Gabor T.
Sherry, Stephen T.
McVean, Gilean
Durbin, Richard
[J]. BIOINFORMATICS, 2011, 27 (15) : 2156 - 2158
[3] Ewens J., 2004, MATH POPULATION GENE
[4] Furutani H., 2009, T MATH MODELING ITS, V2, P54
[5] Furutani H., 2003, FDN GENETIC ALGORITH, V7, P9
[6] Stochastic analysis of schema distribution in a multiplicative landscape
Furutani, Hiroshi
Katayama, Susumu
Sakamoto, Makoto
Ito, Takao
[J]. ARTIFICIAL LIFE AND ROBOTICS, 2007, 11 (01) : 101 - 104
[7] Stochastic analysis of OneMax problem using Markov chain
Ma, QingLian
Zhang, Yu-an
Koga, Kiminobu
Yamamori, Kunihito
Sakamoto, Makoto
Furutani, Hiroshi
[J]. ARTIFICIAL LIFE AND ROBOTICS, 2013, 17 (3-4) : 395 - 399
[8] Tan W. Y., 2002, STOCHASTIC MODELS AP

← 1 →