Internationalof Computational
Intelligence
Systems
Journal ofJournal
Robotics,Networking andArtificial Life
Vol.
XX(Z);
Month(Year),
xx–yy
Vol.
6(1); June(2019),
pp.pp.
56–59
DOI: 10.1080/XXXXXXXXXXXXXX; ISSN
online
DOI: https://doi.org/10.2991/jrnal.k.190602.001;
ISSNXXXX–XXXX
2405-9021; eISSN
2352-6386
https://www.atlantis-press.com/journals/ijndc
https://www.atlantis-press.com/journals/jrnal

Research Article

Unified Approach to (1 + 1) Evolutionary Algorithm
on Discrete Linear Functions
Kenji Aoki1,*, Makoto Sakamoto2, Hiroshi Furutani3, Satoru Hiwa4, Tomoyuki Hiroyasu4
Information Technology Center, University of Miyazaki, 1-1 Gakuen-kibanadai-Nishi, Miyazaki 889-2192, Japan
Department of Computer Science and Systems Engineering, Faculty of Engineering, University of Miyazaki, 1-1 Gakuen-kibanadai-Nishi,
Miyazaki 889-2192, Japan
3
Innovative Computing Research Center, Doshisha University, 1-3 Tataramiyakodani, Kyoto 610-0394, Japan
4
Department of Biomedical Information, Faculty of Life and Medical Sciences, Doshisha University, 1-3 Tataramiyakodani, Kyoto 610-0394, Japan
12ARTICLE INFOABSTRACTArticle History

We consider the runtime property of discrete linear functions in (1 + 1) Evolutionary Algorithms (EAs), Partially Orderedmutation (PO-mutation) and Jansen’s model, Partially Ordered Evolutionary Algorithm (PO-EA). We analyze the process ofevolution. 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 showthat the (1 + 1) EA can obtain an optimum solution at a stable hitting time for discrete linear functions. When the mutation rate isweak, on the order of 1/l, most monotonic functions behave similarly and can be approximated well by the PO-mutation model.

Received 13 October 2018
Accepted 24 November 2018
Keywords
Evolutionary algorithm
discrete linear function(1 + 1) EA
PO-mutation
PO-EA© 2019 The Authors. Published by Atlantis Press SARL.
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION
Discrete optimization is a generic term for mathematical programming that minimize or maximize a given function f(x)under the constraint that the solution x belongs to a set feasible
region with discrete properties. It is depending on whether thecondition that defines the set feasible area is a combinational
condition or an integer condition, it may be roughly divided
into combinatorial optimization and integer optimization. In
this research area, there are researchers who try to capture thecharacteristics of the optimization function f(x) to make optimization easy to handle [1]. We are also interested in the propertiesof this optimization function. In the area of discrete optimization, there are many interesting properties that facilitate theoptimization task [2]. One of them is monotony. Monotonic
submodular functions have recently been applied in the field ofmachine learning. This paper focuses on optimization functions
that are monotonic functions.
The Partial Order Evolutionary Algorithm (PO-EA) model introduced by Jansen [3] contributes to the analysis of performance inlinear functions and is expected to simulate the optimization ofmonotonic functions [4,5]. PO-EA is a pessimistic model of thetrue optimization process, which can be used to derive an upperbound on the expected hitting time of monotonic functions.
PO-EA was divided into two parts by Ma et al. [6]. These are called
PO-mutation and ZeroMax models, respectively. In this study,
Corresponding author. Email: aoki@cc.miyazaki-u.ac.jp*

we used a PO-mutation model. The PO-mutation model contains
mutations that increase the fitness of every monotonic function.
In this study, we assumed that the optimum binary string is {1}l,and use typical monotonous discrete linear functions on (1 + 1)
EA, PO-mutation and PO-EA. The optimum hitting time calculated by computer experiments could confirm the contribution of(1 + 1) EA, PO-mutation and PO-EA, and help to understand themechanism of the optimization process of EA.

2. MATHEMATICAL MODELS OF EAs
An EA is a generic term for a search model or algorithm for searchingfor an optimal solution by imitating the process of inheritance or evolution of an organism. This method evolves a group of solutions andobtains an optimal solution by repeating generational change basedon change and selection on a problem. We can apply to various problems as long as we can represent gene numbers and set fitness evaluation functions. However, even in the case where a single search can be
performed in a short time, a problem in which the number of all solutions is enormous may take too much time for the calculation itself andmay not reach an effective solution. EA can be classified into genetic­algorithm, evolutionary strategy, and evolutionary programming.
In this study, we use the simplest (1 + 1) EA, in which both thenumber of parent and offspring genes are one [7]. Genes are represented by binary string. A gene of length i can be written as(x1, x2, ..., xi) (where xi = 0 or 1). In addition, gene mutation meansthat the value of each xi is inverted according to the probability pm.

K. Aoki et al. / Journal of Robotics, Networking and Artificial Life 6(1) 56–59

We called it mutation probability. If the function f(x) is defined in
an interval [a, b] and f(x) ≤ f(x′) for any x, x′ (x < x′) in the interval,f(x) is said to be a monotonically increasing function in the interval[a, b]. If f(x) ≥ f(x′), then f(x) is said to be a monotonically decreasing function in the interval [a, b]. These are generically called
monotonic function.
In the past research, Furutani et al. [8] analyzed the expected hitting times of EAs and Random Local Search by applying Markov
chain. They showed that using pm = 1/l, the runtime of the Markov
chain is approximately given by l log(l), where l is the length of thegene and l is large enough. In this study, we also set pm = 1/l.

3. EVOLUTIONARY ALGORITHMS
3.1. (1 + 1) Evolutionary Algorithm(m + l) Evolutionary algorithm came from Evolutionary Strategy
developed by Rechenberg and Schwefel, where m and l are numbers of parent and offspring solutions, respectively. We set m = 1and l = 1. These are the simplest combinations, and representedby (1 + 1) EA. It is too simple for an analysis, it has following
properties [2].
(1) It is efficient for many problems.
(2) It cannot get stuck in a local optimum.
(3) The analysis of it reveals many tools that can be used in morepractical algorithms.
The algorithm of (1 + 1) EA is given by Algorithm 1. In this algorithm, x are binary strings and f(x) are optimization functions.
Algorithm 1 | (1 + 1) EA

1: Initialize x ∈ {0, 1}l uniformly at random.
2: Create x′ by flipping one each bit in x with probability pm.
3: Select if f(x′) ≥ f(x) then x := x′.
4: Go to 2 until a termination condition is fulfilled.

57

In the comparison x and x′, (x′ > x) means that every bit changes
were only from 0 to 1, (x′ < x) means that every bit changes wereonly from 1 to 0, and (x ¢  x) means that both bit changes weremixed.
We assumed that {1}l is the optimum string in the step 3 Selection
process of Algorithm 2. PO-mutation model is used to investigate
PO-EA convergence properties, so this model cannot be used tothe problems whose the optimum string is not known.

3.3. Partial Order Evolutionary Algorithm
Jansen introduced the PO-EA model [3]. The algorithm of PO-EA
is given by Algorithm 3.
Algorithm 3 | PO-EA

1: Initialize x ∈ {0, 1}l uniformly at random.
2: Create x′ by flipping one each bit in x with probability pm.

x ¢  x)x AND (f(x′) ≤ f(x))} then x := x′.
3: Select if (x′ ≥ x) OR {(x′4: Go to 2 until a termination condition is fulfilled.
The difference of three algorithms are Selection in the step 3.

4. NUMERICAL EXPERIMENTAs an optimization function, we apply discrete linear function f(x)f (x ) = a1x1 + a2 x2 +  + ai xil		f (x ) = åai xi ,i =1ai = (1 + s)i ,xi Î {0,1}, (1)0 £ s £ 1,

where x is a binary string of length l. We consider the maximization problem of this function. The optimum solution is xopt = {1}l. If
ls = 0, then a = 1 and f (x ) = åxi . That is to say OneMax function.
i =1

3.2. PO-mutation Algorithm

If s = 1, then ai = 2i, i.e. binary number.

Colin et al. [5] have shown that PO-EA can be divided into twoparts. Ma et al. [6] have named it PO-mutation and ZeroMax
models. They treated two selection conditions, (x′ ≥ x) and{(x′  x ) AND (f(x′) ≤ f(x))}, separately. They called the first condition as PO-mutation model, and the second condition as ZeroMax
model, respectively. PO-mutation has a role of driving force forapproaching the optimum solution. In contrast, ZeroMax model
works as a resistance against the approaching to the optimum
solution. ZeroMax model’s power is smaller than OneMax model
because it has a condition (x¢  x ). The algorithm of PO-mutation
is given by Algorithm 2.

In this section, we compare the first hitting time of the numericalexperiments of (1 + 1) EA, PO-mutation and PO-EA with s = 0.0,1.0 and 0.5. We used the mutation rate pm = 1/l. The length of thestring is l = 100, and we performed 10,000 runs for each parameter
set, and averaged over them.

Algorithm 2 | PO-mutation

1: Initialize x ∈ {0, 1}l uniformly at random.
2: Create x′ by flipping one each bit in x with probability pm.
3: Select if x′ ≥ x then x := x′.
4: Go to 2 until a termination condition is fulfilled.

Since many studies suggested that the mutation probability ofpm = 1/l may be the best choice, we carried out our analysis using
this value.

Figure 1 shows the time dependence of the probability of the firsthitting time of optimum solution in (1 + 1) EA, PO-mutation
and PO-EA with s = 0.0. These lines are the results of numerical calculation. The result is moving averaged with window
size of 30. The red line is the result of PO-mutation calculation.
The green line is the result of PO-EA calculation. In Figure 1,
the waveforms of (1 + 1) EA and PO-mutation are similar, but
PO-EA is behind the other. The mean of the first fitting times in(1 + 1) EA, PO-mutation and PO-EA are 1069, 1014 and 1976,respectively.

58

K. Aoki et al. / Journal of Robotics, Networking and Artificial Life 6(1) 56–59

Figure 2 shows the time dependence of the probability of the firsthitting time of optimum solution in (1 + 1) EA, PO-mutation and
PO-EA with s = 1.0. The red line is the result of PO-mutation
calculation. The green line is the result of PO-EA calculation. In
Figure 2, the peak of the first hitting time is delayed in order ofPO-mutation, (1 + 1) EA and PO-EA. The mean of the first fitting
times in (1 + 1) EA, PO-mutation and PO-EA are 1136, 1008 and1295, respectively.
Figure 3 shows the time dependence of the probability of the firsthitting time of optimum solution in (1 + 1) EA, PO-mutation

Figure 3 | The distribution of the first hitting time of optimum
solution in (1 + 1) EA, PO-mutation and PO-EA with s = 0.5. The blueline is the result of (1 + 1) EA calculation. The red line is the resultof PO-mutation calculation. The green line is the result of PO-EA
calculation.

Figure 1 | The distribution of the first hitting time of optimum solutionin (1 + 1) EA, PO-mutation and PO-EA with s = 0.0. The blue line is theresult of (1 + 1) EA calculation. The red line is the result of PO-mutation
calculation. The green line is the result of PO-EA calculation.

and PO-EA with s = 0.5. The red line is the result of PO-mutation
calculation. The green line is the result of PO-EA calculation.
In Figure 3, as in Figure 1, the waveforms of (1 + 1) EA andPO-mutation are similar. PO-EA is behind the other, but it is notas late as Figure 1. The mean of the first fitting times in (1 + 1) EA,PO-mutation and PO-EA are 1050, 1018 and 1280, respectively.

5. SUMMARY
In this paper, we studied time behavior of (1 + 1) EA, PO-mutation
and PO-EA to understand how evolutionary computation works
for discrete linear functions. We demonstrate that the (1 + 1) EA
can obtain an optimum solution at a stable hitting time for discretelinear functions. When the mutation rate is weak, on the order of1/l, most monotonic functions behave similarly and can be approximated well by the PO-mutation model. These studies can help tounderstand the working mechanism of EA, and give some suggestions to design algorithms for other problems.

CONFLICTS OF INTEREST
There is no conflicts of interest.

REFERENCES[1]
Figure 2 | The distribution of the first hitting time of optimum solutionin (1 + 1) EA, PO-mutation and PO-EA with s = 1.0. The blue line is theresult of (1 + 1) EA calculation. The red line is the result of PO-mutation
calculation. The green line is the result of PO-EA calculation.

[2]
[3]

S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge
University Press, Cambridge, 2004.
S. Fujishige, Submodular Functions and Optimization, second
ed., Elsevier, Amsterdam, 2005.
T. Jansen, On the brittleness of evolutionary algorithms, in:
C.R. Stephens, M. Toussaint, D. Whitley, P.F. Stadler, (Eds.),

K. Aoki et al. / Journal of Robotics, Networking and Artificial Life 6(1) 56–59

[4]
[5]

Foundations of Genetic Algorithms, (FOGA 2007), Lecture
Notes in Computer Science, Vol. 4436, Springer, Heidelberg,
2007, pp. 54–69.
B. Doerr, T. Jansen, D. Sudholt, C. Winzen, C. Zarges, Mutation rate
matters even when optimizing monotonic functions, Evol. Comput.
21 (2013), 1–27.
S. Colin, B. Doerr, G. Férey, Monotonic functions in EC:
anything but monotone!, Proceedings of the 2014 Annual
Conference on Genetic and Evolutionary Computation,
Vancouver, BC, Canada, 2014, pp. 753–760.

[6]
[7]

[8]

59

Q.L. Ma, Y-a. Zhang, K. Yamamori, H. Furutani, S. Hiwa, T.
Hiroyasu, Markov chain analysis of evolutionary algorithms formonotonic functions, Artif. Life Robot. 24 (2019), 82–87.
P.S. Oliveto, X. Yao, Runtime analysis of evolutionary algorithms for discrete optimization, Chapter 2, Theory of Rando­
mized Search Heuristics, World Scientific, Singapore, 2011,
pp. 21–52.
H. Furutani, H. Tagami, M. Sakamoto, Y. Du, Markov chain analyses of random local search and evolutionary algorithm. J. Robot.
Netw. Artif. Life. 1 (2014), 220–224.

Authors Introduction
Dr. Kenji Aoki

Dr. Satoru Hiwa
He received his PhD of Engineering fromKagoshima University in 2010. He is currently working in Information TechnologyCenter at University of Miyazaki as
Associate Professor, since 2010. His
research interests include bio-informatics,
evolutionary computation, information
system and Intelligent systems. He is amember of IPSJ and JSET.

He received his PhD in Engineeringfrom Doshisha University. He is currently working in Faculty of Lifeand Medical Sciences at Doshisha
University, Kyoto, Japan, as an AssociateProfessor. His current research interests
include human brain mapping, noninvasive neuroimaging and computational intelligence.

Dr. Makoto Sakamoto

Dr. Tomoyuki Hiroyasu

He received his PhD degree in computer science and systems engineeringfrom Yamaguchi University in 1999. Heis presently an associate professor in
the Faculty of Engineering, Universityof Miyazaki. His first interests lay inhydrodynamics and time series analysis, especially the directional wavespectrum. He is a theoretical computerscientist, and his current main researchinterests are automata theory, languages and computation. His
articles have appeared in journals such as Information Sciences,
Pattern Recognition and Artificial Intelligence, WSEAS, AROB,ICAROB, SJI, IEEE and IEICE (Japan), and proceedings of conferences such as Parallel Image Processing and Analysis, SCI,WSEAS, AROB and ICAROB.

He received his doctor of Engineeringfrom Waseda University in 1998. He
has been a Professor of Life and MedicalSciences, Doshisha University, since2008. His research interests include
the development of novel evolutionary
algorithms, medical image processing,
medical information systems, parallel
computing, Grid, web systems, and Intelligent systems. He is amember of IEEE, JSME, JSCES, IPSJ, SICE, and IEICE.

Dr. Hiroshi Furutani
He received his PhD of Science fromKyoto University in 1981. He is currently
working in Innovative Computing
Research Center at Doshisha University
as researcher. His research interest
includes bio-informatics, evolutionary
computation and quantum computing.