Unified Approach to (1 + 1) Evolutionary Algorithm on Discrete Linear Functions

Authors
Kenji Aoki1, *, Makoto Sakamoto2, Hiroshi Furutani3, Satoru Hiwa4, Tomoyuki Hiroyasu4
1Information Technology Center, University of Miyazaki, 1-1 Gakuen-kibanadai-Nishi, Miyazaki 889-2192, Japan
2Department of Computer Science and Systems Engineering, Faculty of Engineering, University of Miyazaki, 1-1 Gakuen-kibanadai-Nishi, Miyazaki 889-2192, Japan
3Innovative Computing Research Center, Doshisha University, 1-3 Tataramiyakodani, Kyoto 610-0394, Japan
4Department of Biomedical Information, Faculty of Life and Medical Sciences, Doshisha University, 1-3 Tataramiyakodani, Kyoto 610-0394, Japan
*Corresponding author. Email: [email protected]
Corresponding Author
Kenji Aoki
Received 13 October 2018, Accepted 24 November 2018, Available Online 25 June 2019.
DOI
https://doi.org/10.2991/jrnal.k.190602.001How to use a DOI?
Keywords
Evolutionary algorithm; discrete linear function; (1 + 1) EA; PO-mutation; PO-EA
Abstract
We consider the runtime property of discrete linear functions in (1 + 1) Evolutionary Algorithms (EAs), Partially Ordered mutation (PO-mutation) and Jansen’s model, Partially Ordered Evolutionary Algorithm (PO-EA). We analyze the process of evolution. This study was motivated by the paper of Jansen treating the runtime property of (1 + 1) EA on monotonic functions by means of probabilistic theory. As linear functions are special cases of monotonic function, we analyze their behavior. We show that the (1 + 1) EA can obtain an optimum solution at a stable hitting time for discrete linear functions. When the mutation rate is weak, on the order of 1/l, most monotonic functions behave similarly and can be approximated well by the PO-mutation model.
Copyright
© 2019 The Authors. Published by ALife Robotics Corp. Ltd.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).