Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 1 (June 2015), 1-4

Analysis of Asymmetric Mutation Model in Random Local Search
Hiroshi Furutani* and Makoto Sakamoto

Faculty of Engineering, University of Miyazaki, Gakuen Kibanadai-nishi 1-1
Miyazaki City, Miyazaki Prefecture, 889-2192, Japan
Yifei Du

Graduate School of Engineering, University of Miyazaki, Gakuen Kibanadai-nishi 1-1
Miyazaki City, Miyazaki Prefecture, 889-2192, JapanKenji Aoki

Information Technology Center, University of Miyazaki, Gakuen Kibanadai-nishi 1-1
Miyazaki City, Miyazaki Prefecture, 889-2192, JapanE-mail: furutani@cs.miyazaki-u.ac.jp

Abstract
In a standard Evolutionary Algorithms (EAs), one uses the same rate for mutations from bit 1 to bit 0 and its
reverse direction. There are many reports that the asymmetric mutation model is a very powerful strategy in EAs toobtain better solutions more efficiently. In this paper, we report stochastic behaviors of algorithms that areasymmetric mutation models of Random Local Search (RLS). The mathematical structure of asymmetry model canbe derived in terms of a finite Markov chain. We demonstrate some useful results representing the effects ofasymmetric mutation.
Keywords: Random Local Search, Asymmetric mutation, Hitting time, Markov chain

1. Introduction
Theoretical studies of EAs have been performed fromvarious viewpoints. One of the most attractive objects ofthem is the convergence properties of EAs [1]. In theprevious conference, we have reported a randomized
heuristics, which mainly treated the computational
complexity of Random Local Search (RLS) [2]. Our
study used the results obtained in researches on Coupon
Collector Problem (CCP), and made a mathematicalanalysis of hitting time in RLS by extending the originalmodel of CCP.
In this conference, we report another extension ofRLS, an asymmetric mutation model. We apply theasymmetric mutation in evolution of RLS; that is, 𝑝𝑎for mutation 0 → 1 and 𝑝𝑏 for 1 → 0, respectively.

We carry out a theoretical analysis for the evolution ofstrings in the framework of a finite Markov chain [3].
The asymmetric mutation model is a very powerfulstrategy in EAs to obtain better solutions more
efficiently [4]. In biology, spontaneous misreading ofbases during DNA synthesis, mutation, is considered asa major factor contributing to evolution. Wada et al.
showed that double-stranded DNA type strings cansolve the knapsack problem effectively by using theasymmetric machinery of DNA replication [5]. They
used different mutation rates for the leading and lagging
DNA strands.
To analyze the behavior of the evolution processes, itis necessary to take into account of effects due tostochastic fluctuations. During the study of asymmetricmutation model of RLS, we noted mathematical papers

Published by Atlantis Press
Copyright: the authors
1in learning model with reinforcement, which gave theMarkov chain model of learning processes [3]. We
found that results in these papers can be interpreted as amodel of RLS with asymmetric mutation rates, andapply these results in the present study.
In this model, we obtained an explicit form of Markov
chain transition matrix, and furthermore the eigenvaluesof this matrix were calculated by using rather technicalmethods. The largest eigenvalue is naturally 𝜆0 = 1,
and the second largest one is 𝜆1 = 1 − (𝑝𝑎 + 𝑝𝑏 )/𝑙.
Since the most important factor to decide the speed ofconvergence is the second largest eigenvalue, we know
the averaged value of two mutation rates mainly
controls the speed of evolution. We will show in ourreport the behavior of solutions from the aspects ofmathematical analysis and numerical simulations.

Algorithm 3

Lazy RLS

1: Initialize 𝑥 ∈ {0,1}𝑙 uniformly at random.
2: Select one bit 𝑥[𝑗] in 𝑥 at random.
3: Does not change 𝑥[𝑗] with probability 1 − 𝑝𝑎 .
If 𝑥[𝑗] = 0 then 𝑥 ′ [𝑗] = 1 with probability 𝑝𝑎 .
4: If 𝑥[𝑗] is flipped then 𝑥 ≔ 𝑥 ′ .
5: Go to 2 until a termination condition is fulfilled.

This model is also defined as the variation of ARLS byputting 𝑝𝑏 = 0.

3. Markov Chain Model

This section presents the Markov chain approaches tothe EAs. The search space of OneMax function isΩ = {0,1}𝑙 , and we divide Ω into (𝑙 + 1) subsets
Ω = 𝑆0 ∪ 𝑆1 ∪ ⋯ ∪ 𝑆𝑙 , where 𝑓(𝑆𝑖 ) = 𝑖.
3.1. Asymmetric mutation model of RLS

2. Evolutionary Algorithms
As a test function, we adopt OneMax function 𝑓(𝑥)𝑙𝑓(𝑥) = � 𝑥𝑖 , 𝑥𝑖 ∈ {0,1},𝑖=1

where 𝑥 is a binary string of length 𝑙. We consider themaximization of OneMax function. The optimum
solution is 𝑥𝑜𝑝𝑡 = {1}𝑙 , and 𝑓�𝑥𝑜𝑝𝑡 � = 𝑙.
1. The first choice of Evolutionary Algorithm is theRandom Local Search (RLS). We define RLS as
Algorithm 1
Random Local Search
1: Initialize 𝑥 ∈ {0,1}𝑙 uniformly at random.
2: Create 𝑥 ′ by flipping one bit in 𝑥 which is
selected at random.
3: Select if 𝑓(𝑥 ′ ) > 𝑓(𝑥) then 𝑥 ≔ 𝑥 ′ .
4: Go to 2 until a termination condition is fulfilled.
2. The next one is RLS with asymmetric mutation(ARLS). The ARLSis defined asAlgorithm 2
RLS of Asymmetric Mutation
1: Initialize 𝑥 ∈ {0,1}𝑙 uniformly at random.
2: Select one bit 𝑥[𝑗] in 𝑥 at random.
3: With probability 1 − (𝑝𝑎 + 𝑝𝑏 ), 𝑥 ′ [𝑗] = 𝑥[𝑗].
If 𝑥[𝑗] = 0 then 𝑥 ′ [𝑗] = 1 with probability 𝑝𝑎 .
If 𝑥[𝑗] = 1 then 𝑥 ′ [𝑗] = 0 with probability 𝑝𝑏 .
4: If 𝑥[𝑗] is flipped then 𝑥 ≔ 𝑥 ′ .
5: Go to 2 until a termination condition is fulfilled.
3. The third one is a lazy version of RLS, which isdefined as

The transition matrix 𝑃𝑖,𝑗 = 𝑃(𝑗|𝑖) represents theevolution of ARLS.
1. For 𝑗 = 𝑖 + 1, 0 ≤ 𝑖 < 𝑙𝑖
𝑃𝑖,𝑖+1 = 𝑝𝑎 �1 − �.
𝑙
2. For 𝑗 = 𝑖 − 1, 0 < 𝑖 ≤ 𝑙𝑖
𝑃𝑖,𝑖−1 = 𝑝𝑎 .
𝑙
3. For 𝑖 = 𝑗, 0 ≤ 𝑖 ≤ 𝑙𝑖𝑖
𝑃𝑖,𝑖 = 1 − 𝑝𝑎 �1 − � − 𝑝𝑎 .
𝑙𝑙

For example, the transition matrix for 𝑙 = 3 is givenby1 − 𝑝𝑎1⎛ 𝑝𝑏
𝑷=⎜ 3⎜0⎝ 0𝑝𝑎
2
11 − 𝑝𝑎 − 𝑝𝑏
332𝑝3 𝑏002𝑝3 𝑎

121 − 𝑝𝑎 − 𝑝𝑏
33𝑝𝑏00⎞⎟⎟1𝑝3 𝑎
1 − 𝑝𝑏 ⎠The left eigenvectors 𝒖 = (𝑢0 , 𝑢1 , ⋯ , 𝑢𝑙 ) satisfy, inthe case of 𝑙 = 3,
1(1 − 𝑝𝑎 )𝑢0 + 𝑝𝑏 𝑢1 = 𝜆𝑢0 ,32

12𝑝𝑎 𝑢0 + �1 − 𝑝𝑎 − 𝑝𝑏 � 𝑢1 + 𝑝𝑏 𝑢2 = 𝜆𝑢1 ,3332
12𝑝𝑎 𝑢1 + �1 − 𝑝𝑎 − 𝑝𝑏 � 𝑢2 + 𝑝𝑏 𝑢3 = 𝜆𝑢2 ,3331𝑝𝑎 𝑢2 + (1 − 𝑝𝑏 )𝑢3 = 𝜆𝑢3 .
3We define the 𝑙th order polynomial function

Published by Atlantis Press
Copyright: the authors223𝑙𝑓(𝑧) = 𝑢0 + 𝑢1 𝑧 + 𝑢2 𝑧 + 𝑢3 𝑧 + ⋯ + 𝑢𝑙 𝑧 .

Multiplying eigenvalue equations with 1, 𝑧, 𝑧 2 , … , 𝑧 𝑙 ,respectively, and summing them up, we have𝑙(𝑝𝑎 𝑧 + 1 − 𝑝𝑎 − 𝜆)𝑓(𝑧) − (𝑧 − 1)(𝑝𝑎 𝑧 + 𝑝𝑏 )𝑓 ′ (𝑧) = 0.
Considering this as a differential equation of 𝑓, wehave
𝑘𝑓(𝑧) = 𝐶(𝑧 − 1) (𝑝𝑎 𝑧 + 𝑝𝑏 )𝑙−𝑘,𝑙(1 − 𝜆)𝑘=,𝑝𝑎 + 𝑝𝑏
where 𝐶 is an arbitrary constant. Since 𝑓(𝑧) is apolynomial of 𝑙 th order, 𝑘 must be an integer of{0,1, … , 𝑙}. Then the eigenvalues are given by𝑘
𝜆𝑘 = 1 − (𝑝𝑎 + 𝑝𝑏 ),𝑘 = 0,1, … , 𝑙.
⑴
𝑙The largest eigenvalue is 𝜆0 = 1 , and the second
largest one
is 𝜆1 = 1 − (𝑝𝑎 + 𝑝𝑏 )/𝑙 , which
determines the convergence speed of the chain.
The eigenvector corresponding to the largest
eigenvalue 𝜆0 = 1 presents the distribution of thestationary state. In this case of 𝑘 = 0, we have𝑙𝑙𝑓(𝑧) = (𝑝𝑎 𝑧 + 𝑝𝑏 )𝑙 = � � � 𝑝𝑎 𝑖 𝑝𝑏 𝑙−𝑖 𝑧 𝑖 ,𝑖𝑖=0thus the components of eigenvector with normalization
are given by𝑙𝑢𝑖 = � � 𝑝𝑎 𝑖 𝑝𝑏 𝑙−𝑖 /(𝑝𝑎 + 𝑝𝑏 )𝑙 , (0 ≤ 𝑖 ≤ 𝑙).
⑵𝑖

From this, we can obtain the average number of bit
ones,
𝑝𝑎
𝑖=𝑙.
𝑝𝑎 + 𝑝𝑏
Similarly, we have the variance𝑝𝑎 ∙ 𝑝𝑏
𝑉(𝑖) = 𝑙.
(𝑝𝑎 + 𝑝𝑏 )2

Both quantities depend on the ratio of two mutation
rates 𝑝𝑏 /𝑝𝑎 .

𝑸 𝑹
�
⑶
𝟒 𝑰
The 𝑙 × 𝑙 submatrix 𝑸 shows transition probabilities
among transient states 𝑆0 , 𝑆1 , ⋯ , 𝑆𝑙−1 . Since there is
only one absorbing state, the unit matrix 𝑰 is a scalar 1.
For the calculation of the hitting time of the optimum
solution, we use the fundamental matrix
𝑵 = (𝑰 − 𝑸)−1 .
⑷
𝑷=�

After some calculations, we have𝑁𝑖,𝑗 = 0,(𝑖 > 𝑗)𝑙(𝑖 ≤ 𝑗).
,(𝑙 − 𝑗)𝑝𝑎
The expected step 𝐸𝑖 (𝑡) to enter into the absorbing
state from the initial state 𝑖 is given by the vector 𝒎of (𝑙 × 1) [3]𝒎 = 𝑵𝟏,=

where 𝑚𝑖 is the expected step from ith state, and 𝟏 isa column vector whose all entries are 1.
The variance of 𝑡 is given by
𝑉(𝑡) = (2𝑵 − 𝑰)𝒎 − 𝒎2 ,where 𝒎2 is a column vector whose elements are 𝑚𝑖 2 .

4. Numerical Experiment

In this section, we demonstrate theoretical predictions
and results of numerical calculations for comparison.
We performed 10000 runs for each calculation, andobtained statistical quantities from them.
Figure 1 shows the stationary distribution of theasymmetric mutation model. The string length 𝒍 = 𝟒𝟒,
𝒑𝒂 = 𝟒. 𝟒𝟎 and 𝒑𝒃 = 𝟒. 𝟒𝟎. The crosses are the resultof numerical calculation. The solid line is the theoreticalprediction obtained by eq.⑵.
Figure 2 shows the distribution of the first hitting timeof the optimum solution in Lazy RLS. The string length𝒍 = 𝟎𝟒 and mutation rate 𝑝𝑎 = 𝟒. 𝟎. The initial state isa bit string of all zeros. Dots are the numerical results.
The solid line is the theoretical prediction obtained byusing Markov chain transition matrix.

3.2. Lazy RLS

The transition matrix for the lazy RLS shows that theMarkov chain is absorbing one, and there are 𝑙transient and one absorbing states, respectively. For
absorbing Markov chains, the transition matrix isrepresented as

Published by Atlantis Press
Copyright: the authors
3Fig. 1. Distribution of the stationary state inasymmetric mutation model of RLS with 𝒍 = 𝟒𝟒.
Mutation rates are 𝒑𝒂 = 𝟎. 𝟎𝟎 and 𝒑𝒃 = 𝟎. 𝟎𝟎 ,respectively.

Fig. 3. Mutation rate dependence of the average
hitting time and its standard deviation in Lazy RLS
with 𝒍 = 𝟐𝟐.

5 SummaryIn this paper, we considered the behavior of theasymmetric mutation in the solving the optimization ofOneMax function. This problem can be solved
analytically in terms of a finite Markov chain [3]. We
derived the eigenvalues and eigenvectors.
In genetic biology, it has been suggested by manystatistical studies that asymmetric directional mutationpressures are commonly observed. It is interesting tostudy the phenomena using our theoretical approach.
References

Fig. 2. Distribution of the first hitting time in Lazy
RLS with 𝒍 = 𝟐𝟐 and 𝒑𝒂 = 𝟎. 𝟑. The initial state isa bit string of all zeros. Dots are RLS calculations,and the solid line is the theoretical prediction.
Figure 3 shows the dependence of the average hitting
time and its standard deviation (SD) on mutation rate
𝑝𝑎 in Lazy RLS. The string length 𝑙 is 20. The initialstate is a bit string of all zeros. The thin solid line is thetheoretical prediction of the average hitting time, andthe thick solid line represents the theoretical SD. Circles
and crosses are numerical results.

1. P. S. Oliveto and X. Yao (2011), Runtime analysis ofevolutionary algorithms for discrete optimization, in
Theory of Randomized Search Heuristics, A. Auger andB. Doerr (eds), World Scientific, Singapore, pp.21--52.
2. H. Furutani, H. Tagami, Y. Du, and M. Sakamoto (2014),
Markov chain analyses of Random Local Search andEvolutionary Algorithm, in Proceedings of theICAROB2014.
3. M. Iosifescu (1980), Finite Markov chain processes andtheir applications, John Wiley & Sons, New York.
4. B. Doerr, N. Hebbinghaus and F. Neumann (2007),
Speeding up Evolutionary Algorithms throughasymmetricmutation
operator,
Evolutionary
Computation 15, pp.401--410.
5. K. Wada, H. Doi, S. Tanaka, Y. Wada and M. Furusawa(1993), A neo-Darwinian algorithm: Asymmetricalmutation due to semiconservative DNA-type replication
promote evolution, Proceedings of National Academy ofScience, USA 90, pp.11934--11938.

Published by Atlantis Press
Copyright: the authors
4