Journal of Robotics, Networking and Artificial Life

Volume 1, Issue 3, December 2014, Pages 220 - 224

Markov Chain Analyses of Random Local Search and Evolutionary Algorithm

Authors
Hiroshi Furutani, Hiroki Tagami, Makoto Sakamoto, Yifei Du
Corresponding Author
Hiroshi Furutani
Available Online 15 December 2014.
DOI
https://doi.org/10.2991/jrnal.2014.1.3.11How to use a DOI?
Keywords
Evolutionary algorithm, Random Local Search, Coupon collector's problem, Markov chain
Abstract

Theoretical studies of evolutionary algorithms (EAs) have been developed by researchers whose main interests are convergence properties of algorithms. In this paper, we report the computational complexity of an algorithm that is a variant of (1+1) EA, called Random Local Search (RLS). While a standard EA uses a mutation of flipping each bit in a parent string, RLS flips exactly one bit at each step. It has been noted the close resemblance of RLS with the coupon collector problem (CCP). CCP has a long history of probabilistic research, and many interesting results are obtained. This study makes use of such results with some modifications. We also show some useful results representing the evolution process of (1+1) EA.

Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Journal
Journal of Robotics, Networking and Artificial Life
Volume-Issue
1 - 3
Pages
220 - 224
Publication Date
2014/12/15
ISSN (Online)
2352-6386
ISSN (Print)
2405-9021
DOI
https://doi.org/10.2991/jrnal.2014.1.3.11How to use a DOI?
Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - JOUR
AU  - Hiroshi Furutani
AU  - Hiroki Tagami
AU  - Makoto Sakamoto
AU  - Yifei Du
PY  - 2014
DA  - 2014/12/15
TI  - Markov Chain Analyses of Random Local Search and Evolutionary Algorithm
JO  - Journal of Robotics, Networking and Artificial Life
SP  - 220
EP  - 224
VL  - 1
IS  - 3
SN  - 2352-6386
UR  - https://doi.org/10.2991/jrnal.2014.1.3.11
DO  - https://doi.org/10.2991/jrnal.2014.1.3.11
ID  - Furutani2014
ER  -