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.11
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 ALife Robotics Corp. Ltd.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).