Markov Chain Analyses of Random Local Search and Evolutionary Algorithm
- https://doi.org/10.2991/jrnal.2014.1.3.11How to use a DOI?
- Evolutionary algorithm, Random Local Search, Coupon collector's problem, Markov chain
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.
- © 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 -