# An Allele Real-Coded Quantum Evolutionary Algorithm Based on Hybrid Updating Strategy

Authors: Yu-Xian Zhang; Xiao-Yi Qian; Hui-Deng Peng; Jian-Hui Wang
Journal: Computational Intelligence and Neuroscience
 (2016)

---

## Abstract

For improving convergence rate and preventing prematurity in quantum evolutionary algorithm, an allele real-coded quantum evolutionary algorithm based on hybrid updating strategy is presented. The real variables are coded with probability superposition of allele. A hybrid updating strategy balancing the global search and local search is presented in which the superior allele is defined. On the basis of superior allele and inferior allele, a guided evolutionary process as well as updating allele with variable scale contraction is adopted. AndHε gate is introduced to prevent prematurity. Furthermore, the global convergence of proposed algorithm is proved byMarkov chain. Finally, the proposed algorithm is compared with genetic algorithm, quantum evolutionary algorithm, and double chains quantum genetic algorithm in solving continuous optimization problem, and the experimental results verify the advantages on convergence rate and search accuracy.


---

## Body

## 1. Introduction

Quantum computing is a new class of computing algorithms based on the concepts and principles of quantum theory, such as superposition of quantum states, entanglement, and intervention. Quantum evolutionary algorithm (QEA) is proposed by combining quantum theory with evolutionary theory. It is a kind of evolutionary algorithm with the form of quantum chromosome; the random observation which simulates the quantum collapse can bring diverse individuals [1]. In QEA, the quantum bits (Q-bits) and quantum gate (Q-gate) have been used to update the individuals to realize evolutionary search. QEA has advantages, including the diversity of population, global search performance, and convergence rate, compared with other evolutionary algorithms due to Q-bits coding and the updating of rotation gate. Since then, QEA were developed, including different operators [2–5] and novel update strategy for Q-gates [6–9]. QEA has been applied in many optimization problems [10, 11]. However, frequent encoding and decoding in QEA will slow down convergence rate. In addition, the magnitude and the direction of the rotational angle of quantum rotation gates cannot be determined during optimization.Recently, numerous literatures on QEA have been reported. Han and Kim [12] proposed a quantum-inspired evolutionary algorithm with Hε gate in which the probability amplitudes of rotation gate converge to ε and 1-ε. Chen et al. [13] proposed a rotation gate with chaos in QEA. It applied generated chaotic sequence beforehand at the updating of rotation gate to improve the computational speed. Yang et al. [14] proposed a rotation gate based on arithmetic guidance. In the proposed algorithm, the current optimal individuals transfer to next generation. S. Y. Li and P. C. Li [15] proposed the double chains quantum genetic algorithm (DCQGA) which mapped the real variables to the probability amplitude on Q-bit by transforming the solution space; in particular, a real Q-bit encoding can be used to avoid binary coding. da Cruz et al. [16] proposed a real-coded quantum evolutionary algorithm in which the solution space is expressed by rectangular region. Its outstanding performance in solving high dimensional continuous optimization problems was verified. P. Li and S. Li [17] proposed a Bloch spherical coding for QEA which can avoid local optimization in solving continuous optimization problems. Gao et al. [18] proposed a real-coded quantum evolutionary algorithm based on triploid coding. Zhang et al. [19] proposed four-chain quantum-inspired evolutionary algorithm in which a chromosome contains four gene chains. The above quantum evolutionary algorithms introduce Q-bit encoding and increase diversity of population but spend much time on encoding and decoding; meanwhile, the search process may fall into local minimum and prematurity. So it is very important for us to employ a novel updating strategy in order to improve convergence rate and prevent the premature.In this paper, we presented an allele real-coded quantum evolutionary algorithm (ARQEA) based on hybrid updating strategy. The proposed algorithm employs a real-coding to maintain the diversity of allele and introduces a hybrid updating strategy to balance performance between global search and local search in order to improve the convergence rate. The convergence of ARQEA is verified byMarkov chain. The numerical examples verify the advantages of ARQEA on convergence rate and search accuracy.The remainder of this paper is organized as follows: in Section2, an allele real-coded quantum evolutionary algorithm is proposed in which the real coding as well as hybrid update strategy is presented; in Section 3, the global convergence of proposed algorithm is verified byMarkov chain. Finally, the numerical experiments are demonstrated and the advantages are verified in Section 4.


## 2. An Allele Real-Coded Quantum Evolutionary Algorithm

In ARQEA, the real variables are coding with probability superposition of allele. A hybrid evolutionary strategy balancing the global search and local search is presented in which the superior allele is defined. The supervised evolution as well as variable scale contraction is adopted, andHε gate is introduced to prevent the premature convergence.


### 2.1. Real Coding for Allele

We present an allele real coding which will generate two continuous variablesxi and xi′ (xi and xi′ are defined as the ith alleles) to replace 0 and 1 gene of Q-bit coding in QEA. The real coding is(1)x1x2⋯xi⋯xnx1′x2′⋯xi′⋯xn′,where n is the number of variables.The probability amplitudes of allele are expressed as trigonometric functionscosθi and sinθi:(2)cos⁡θ1cos⁡θ2⋯cos⁡θi⋯cos⁡θnsin⁡θ1sin⁡θ2⋯sin⁡θi⋯sin⁡θn,where cosθi and sinθi are the probability amplitudes of xi and xi′; the initial value of θi is π/4, i=,1,…,n.Then the observed probability ofxi and xi′ is cos2⁡θi and sin2⁡θi, respectively. So(3)cos2⁡θi+sin2⁡θi=1.We employ the probability superposition to maintain the diversity for individual in real coding. And the proposed real coding prevents overlong chromosome length and saves time spent on encoding and decoding.


### 2.2. Hybrid Updating Strategy

In ARQEA, we adopt hybrid updating strategy to update allele and its probability amplitudes.


#### 2.2.1. Updating Alleles

Firstly, we encode initial population on the basis of allele real coding scheme, compute the fitness of chromosomes, and recode the superior individualxi∗. Then we compare the distances between the ith alleles xi and xi′ and define the allele corresponding to the shorter distance with xi∗ as “superior allele,” the other one as “inferior allele.” Figure 1 shows the superior and inferior alleles, in which xi and xi′ are the ith alleles of chromosome, xi∗ is the ith allele of the current optimal individual, and then we define xi as the superior allele and xi′ as the inferior allele.Figure 1
The superior and inferior alleles.Next, we will update the alleles. The updating strategy is described as follows:(a) For the superior allele, we employ the updating strategy, such as reasonable choice of the initial step length and dynamic adjustment of the search step length, to guide superior allele to search optimal solution.In the early search stage, the updating strategy is accelerated by directing the search direction(4)xi+1=xi+sign⁡xi∗-xi·Δd1,where xi is a superior allele, xi+1 is the updated allele, Δd1=λ·xi∗-xi is the search step length, usually λ=0.5, and sign is a sign function; it decides the search direction of superior allele.Whenxi∗-xi/(xmax-xmin) is less than η, we adopt a variable scale contraction to search the optimal solution(5)xi+1=xi+U-1,1·1-arctanrg4·Δd2,where r is the number of current generation, g is the number of max generation, U(-1,1) is a random distribution between −1 and 1, (1-arctan(r/g))4 is a change from 1 to 0 with the number of generation r, and Δd is the range of contraction. When U(-1,1) is a negative number, Δd2=xi-xmin.In this search stage, the superior allele will randomly search the optimal solution in a certain region, and the searching scale will change with the number of generationr.(b) For the inferior allelexi′, the allele xi will be substituted to xi′ in (4) and (5) and alternate operation every two generations using (4) and (5).However, considering the randomness of the evolutionary algorithm, the inferior allele has the ability to escape from local optimum and approach the global optimum in the evolution stage.


#### 2.2.2. Updating Probability Amplitudes

After updating the allele,Hε gate is used to update the corresponding probability amplitudes [20, 21]. We employ Hε gate operation to prevent the premature convergence. The rotation angle of Hε gate is(6)θi+1=θi±1-arctan⁡rg4Δt,where Δt is the range of θi and its direction depends on the superior allele.If the superior allele corresponds tocosθi, then (6) is subtracting. Instead, it is adding. The Hε gate operation will increase the observed probability for the superior allele and decrease the observed probability for the inferior allele.The operation rule ofHε gate is the following:(a)
ifαi′2≤ε and βi′2≥1-ε, then αi′′βi′′T=ε1-εT;(b)
ifαi′2≥1-ε and βi′2≤ε, then αi′′βi′′T=1-εεT;(c)
elseαi′′βi′′T=αi′βi′T,where ε is a real number between 0 and 1, αi′βi′ are the probability amplitudes after the Hε gate operation, and αi′′βi′′ are the probability amplitudes after the Hε gate operation.The steps of hybrid evolutionary strategy are described as follows.Step 1.
Judge the relative superior allele.Step 2.
For the superior allele, adopt supervised evolution by (4) to find current optimal allele xi∗, and employ variable scale contraction by (5) approach to local search when xi∗-xi/(xmax-xmin) is less than η.Step 3.
For the inferior allele, search alternately by (4) and (5) in every two generations.Step 4.
Update the probability amplitudes of alleles by (6).In hybrid updating strategy, we employ different evolutionary mode for superior and inferior allele in order to balance global search and local search. The superior allele affects local search stage, and inferior allele plays important role in global search by the variable scale contraction to search unknown space and maintain the diversity of population. As generation goes on, superior allele and inferior allele exchange position in next generation dynamically. The hybrid updating strategy proposed has two mechanisms for superior and inferior allele to maintain diversity of population. In addition, the hybrid updating strategy in ARQEA balances the global search and local search by dynamic updating strategy of alleles.


### 2.3. Process of ARQEA

ARQEA employs allele real coding with probability superposition which generates a random numberri between 0 and 1 and compares ri with the probability amplitudes for each allele and adopts hybrid updating strategy to balance global search and local search. At the early search stage, the scale of mutation is large, the step size in search is long, and the algorithm approaches to the global search. With the increasing of generations, the scale of mutation becomes smaller and the performance of local search is strengthened. The process of ARQEA is shown in Figure 2.Figure 2
The flowchart of ARQEA.


## 2.1. Real Coding for Allele

We present an allele real coding which will generate two continuous variablesxi and xi′ (xi and xi′ are defined as the ith alleles) to replace 0 and 1 gene of Q-bit coding in QEA. The real coding is(1)x1x2⋯xi⋯xnx1′x2′⋯xi′⋯xn′,where n is the number of variables.The probability amplitudes of allele are expressed as trigonometric functionscosθi and sinθi:(2)cos⁡θ1cos⁡θ2⋯cos⁡θi⋯cos⁡θnsin⁡θ1sin⁡θ2⋯sin⁡θi⋯sin⁡θn,where cosθi and sinθi are the probability amplitudes of xi and xi′; the initial value of θi is π/4, i=,1,…,n.Then the observed probability ofxi and xi′ is cos2⁡θi and sin2⁡θi, respectively. So(3)cos2⁡θi+sin2⁡θi=1.We employ the probability superposition to maintain the diversity for individual in real coding. And the proposed real coding prevents overlong chromosome length and saves time spent on encoding and decoding.


## 2.2. Hybrid Updating Strategy

In ARQEA, we adopt hybrid updating strategy to update allele and its probability amplitudes.


### 2.2.1. Updating Alleles

Firstly, we encode initial population on the basis of allele real coding scheme, compute the fitness of chromosomes, and recode the superior individualxi∗. Then we compare the distances between the ith alleles xi and xi′ and define the allele corresponding to the shorter distance with xi∗ as “superior allele,” the other one as “inferior allele.” Figure 1 shows the superior and inferior alleles, in which xi and xi′ are the ith alleles of chromosome, xi∗ is the ith allele of the current optimal individual, and then we define xi as the superior allele and xi′ as the inferior allele.Figure 1
The superior and inferior alleles.Next, we will update the alleles. The updating strategy is described as follows:(a) For the superior allele, we employ the updating strategy, such as reasonable choice of the initial step length and dynamic adjustment of the search step length, to guide superior allele to search optimal solution.In the early search stage, the updating strategy is accelerated by directing the search direction(4)xi+1=xi+sign⁡xi∗-xi·Δd1,where xi is a superior allele, xi+1 is the updated allele, Δd1=λ·xi∗-xi is the search step length, usually λ=0.5, and sign is a sign function; it decides the search direction of superior allele.Whenxi∗-xi/(xmax-xmin) is less than η, we adopt a variable scale contraction to search the optimal solution(5)xi+1=xi+U-1,1·1-arctanrg4·Δd2,where r is the number of current generation, g is the number of max generation, U(-1,1) is a random distribution between −1 and 1, (1-arctan(r/g))4 is a change from 1 to 0 with the number of generation r, and Δd is the range of contraction. When U(-1,1) is a negative number, Δd2=xi-xmin.In this search stage, the superior allele will randomly search the optimal solution in a certain region, and the searching scale will change with the number of generationr.(b) For the inferior allelexi′, the allele xi will be substituted to xi′ in (4) and (5) and alternate operation every two generations using (4) and (5).However, considering the randomness of the evolutionary algorithm, the inferior allele has the ability to escape from local optimum and approach the global optimum in the evolution stage.


### 2.2.2. Updating Probability Amplitudes

After updating the allele,Hε gate is used to update the corresponding probability amplitudes [20, 21]. We employ Hε gate operation to prevent the premature convergence. The rotation angle of Hε gate is(6)θi+1=θi±1-arctan⁡rg4Δt,where Δt is the range of θi and its direction depends on the superior allele.If the superior allele corresponds tocosθi, then (6) is subtracting. Instead, it is adding. The Hε gate operation will increase the observed probability for the superior allele and decrease the observed probability for the inferior allele.The operation rule ofHε gate is the following:(a)
ifαi′2≤ε and βi′2≥1-ε, then αi′′βi′′T=ε1-εT;(b)
ifαi′2≥1-ε and βi′2≤ε, then αi′′βi′′T=1-εεT;(c)
elseαi′′βi′′T=αi′βi′T,where ε is a real number between 0 and 1, αi′βi′ are the probability amplitudes after the Hε gate operation, and αi′′βi′′ are the probability amplitudes after the Hε gate operation.The steps of hybrid evolutionary strategy are described as follows.Step 1.
Judge the relative superior allele.Step 2.
For the superior allele, adopt supervised evolution by (4) to find current optimal allele xi∗, and employ variable scale contraction by (5) approach to local search when xi∗-xi/(xmax-xmin) is less than η.Step 3.
For the inferior allele, search alternately by (4) and (5) in every two generations.Step 4.
Update the probability amplitudes of alleles by (6).In hybrid updating strategy, we employ different evolutionary mode for superior and inferior allele in order to balance global search and local search. The superior allele affects local search stage, and inferior allele plays important role in global search by the variable scale contraction to search unknown space and maintain the diversity of population. As generation goes on, superior allele and inferior allele exchange position in next generation dynamically. The hybrid updating strategy proposed has two mechanisms for superior and inferior allele to maintain diversity of population. In addition, the hybrid updating strategy in ARQEA balances the global search and local search by dynamic updating strategy of alleles.


## 2.2.1. Updating Alleles

Firstly, we encode initial population on the basis of allele real coding scheme, compute the fitness of chromosomes, and recode the superior individualxi∗. Then we compare the distances between the ith alleles xi and xi′ and define the allele corresponding to the shorter distance with xi∗ as “superior allele,” the other one as “inferior allele.” Figure 1 shows the superior and inferior alleles, in which xi and xi′ are the ith alleles of chromosome, xi∗ is the ith allele of the current optimal individual, and then we define xi as the superior allele and xi′ as the inferior allele.Figure 1
The superior and inferior alleles.Next, we will update the alleles. The updating strategy is described as follows:(a) For the superior allele, we employ the updating strategy, such as reasonable choice of the initial step length and dynamic adjustment of the search step length, to guide superior allele to search optimal solution.In the early search stage, the updating strategy is accelerated by directing the search direction(4)xi+1=xi+sign⁡xi∗-xi·Δd1,where xi is a superior allele, xi+1 is the updated allele, Δd1=λ·xi∗-xi is the search step length, usually λ=0.5, and sign is a sign function; it decides the search direction of superior allele.Whenxi∗-xi/(xmax-xmin) is less than η, we adopt a variable scale contraction to search the optimal solution(5)xi+1=xi+U-1,1·1-arctanrg4·Δd2,where r is the number of current generation, g is the number of max generation, U(-1,1) is a random distribution between −1 and 1, (1-arctan(r/g))4 is a change from 1 to 0 with the number of generation r, and Δd is the range of contraction. When U(-1,1) is a negative number, Δd2=xi-xmin.In this search stage, the superior allele will randomly search the optimal solution in a certain region, and the searching scale will change with the number of generationr.(b) For the inferior allelexi′, the allele xi will be substituted to xi′ in (4) and (5) and alternate operation every two generations using (4) and (5).However, considering the randomness of the evolutionary algorithm, the inferior allele has the ability to escape from local optimum and approach the global optimum in the evolution stage.


## 2.2.2. Updating Probability Amplitudes

After updating the allele,Hε gate is used to update the corresponding probability amplitudes [20, 21]. We employ Hε gate operation to prevent the premature convergence. The rotation angle of Hε gate is(6)θi+1=θi±1-arctan⁡rg4Δt,where Δt is the range of θi and its direction depends on the superior allele.If the superior allele corresponds tocosθi, then (6) is subtracting. Instead, it is adding. The Hε gate operation will increase the observed probability for the superior allele and decrease the observed probability for the inferior allele.The operation rule ofHε gate is the following:(a)
ifαi′2≤ε and βi′2≥1-ε, then αi′′βi′′T=ε1-εT;(b)
ifαi′2≥1-ε and βi′2≤ε, then αi′′βi′′T=1-εεT;(c)
elseαi′′βi′′T=αi′βi′T,where ε is a real number between 0 and 1, αi′βi′ are the probability amplitudes after the Hε gate operation, and αi′′βi′′ are the probability amplitudes after the Hε gate operation.The steps of hybrid evolutionary strategy are described as follows.Step 1.
Judge the relative superior allele.Step 2.
For the superior allele, adopt supervised evolution by (4) to find current optimal allele xi∗, and employ variable scale contraction by (5) approach to local search when xi∗-xi/(xmax-xmin) is less than η.Step 3.
For the inferior allele, search alternately by (4) and (5) in every two generations.Step 4.
Update the probability amplitudes of alleles by (6).In hybrid updating strategy, we employ different evolutionary mode for superior and inferior allele in order to balance global search and local search. The superior allele affects local search stage, and inferior allele plays important role in global search by the variable scale contraction to search unknown space and maintain the diversity of population. As generation goes on, superior allele and inferior allele exchange position in next generation dynamically. The hybrid updating strategy proposed has two mechanisms for superior and inferior allele to maintain diversity of population. In addition, the hybrid updating strategy in ARQEA balances the global search and local search by dynamic updating strategy of alleles.


## 2.3. Process of ARQEA

ARQEA employs allele real coding with probability superposition which generates a random numberri between 0 and 1 and compares ri with the probability amplitudes for each allele and adopts hybrid updating strategy to balance global search and local search. At the early search stage, the scale of mutation is large, the step size in search is long, and the algorithm approaches to the global search. With the increasing of generations, the scale of mutation becomes smaller and the performance of local search is strengthened. The process of ARQEA is shown in Figure 2.Figure 2
The flowchart of ARQEA.


## 3. Convergence Analyses

In this section, we analyze the global convergence of ARQEA byMarkov chain. The ARQEA is described as follows.Consider ARQEA:(7)Ω,G,D,P,n,X0,X′t,X′′t,Xt,Fmin,Xbest,Fbest,ε,where Ω is search space, G is the evolutionary operator of superior allele, D is the evolutionary operator of inferior allele, P is the operator of probability selection, n is the dimension of Ω, X(0) is initial population, X′(t), X′′(t), and X(t) are the superior allele, the inferior allele, and the observed allele in tth generation, respectively, Fmin is the fitness function, Xbest is the optimal solution and Fbest is optimal value of the fitness function, and ε is the termination criterion.According to the hybrid update strategy, the population sequence of ARQEA can be expressed as follows:(8)Xt+1=PGX′t+1-PDX′′t.In (8), X(t+1) relates to the state of generations t.Then, the state space of ARQEA can be expressed as(9)Ω=Ω1,Ω2,…,Ωmax,where max=∏i=1nXiu-Xid/ε; Xiu and Xid are the upper bound and lower bound of the ith variable. So ARQEA can be regarded as a finiteMarkov process.Then the state spaceΩ is divided into two search spaces according to the termination criteria:(a)
S1={Ωi∣Fsi-Fbest<ε};(b)
S2={Ωi∣Fsi-Fbest≥ε}.We definep1→1 as the transition probability from S1 to S1, p2→1 as the transition probability from S2 to S1, and p2→2 as the transition probability from S2 to S2. And p1→1=1.Lemma A (see [22]).
AssumeA1,A2,… are the event sequence in probability space, and let pk=p{Ak}; if ∑k=1∞pk<∞, then p{⋂i=1∞⋃k≥iAk}=0; if ∑k=1∞pk=∞ and all Ak are mutually independent, then p{⋂i=1∞⋃k≥iAk}=1.Theorem A.
∃
φ
∈
(
0,1
), make p2→2<φ in ARQEA.Proof.
∃
d
>
0, when ε>0 and X(t)-Xbest≤d, then F(X(t))-Fbest<λ, in which 0<λ<ε; if C1={X(t)∣X(t)-Xbest≤d}, then C1⊂S1.
The variable scale contraction in ARQEA is Gaussian distribution. If the individualX in S2 performs variable scale contraction operation and obtained X+δ, then (10)pX+δ∈C1<pX+δ∈S1=p2→1.
Sinceδ is Gaussian distribution N(0,δ2), the probability density is(11)fx=1σ2π·e-x2/2σ2.Because(12)pX+δ∈C1=∏i=1npXi+δ-Xbest≤d=∏i=1n∫Xbest-Xi-dXbest-Xi+dfxdx,then(13)0<∏i=1n∫Xbest-Xi-dXbest-Xi+dfxdx<1⟹0<pX+δ∈C1<1.
Becauseδ depends on Gaussian distribution and p{(X+δ)∈C1} is continuous, then(14)pX′+δ∈S1=min⁡pX+δ∈S1.Let φ=1-p{(X′+δ)∈S1}; we can obtain following equation by (11) and (14):(15)pX′+δ∈S1≤pX+δ∈S1<p2→1=1-p2→2⟹p2→2<1-pX′+δ∈S1⟹p2→2<φ.Theorem B.
If one-step transition probability in ARQEAp2→2<φ, then ARQEA is global convergence.Proof.
For the termination criterionε>0, when the probability p′=p2→2=p{F(X(t))-F(Xbest)≥ε}, X(t) cannot satisfy the termination criterion ε>0 after t generations; we can obtain (16) by Theorem A:(16)∑t=1∞pt′<∑t=1∞φand 0<φ<1, so ∑t=1∞φ=φ/1-φ; we can get (17) by Lemma A:(17)p⋂i=1∞⋃t≥iFXt-FXbest≥ε=0.So limt→∞F(X(t))=F(Xbest). That is, ARQEA can converge to the optimal solution with probability 1.


## 4. Experiments and Results Analysis

In this section, we investigate the search ability of ARQEA by eight test functions and compare the results with GA, QEA, and DCQGA. And the above optimization algorithms are encoded in MATLAB 2010b and implemented on computer with Intel T3200 CPU and 2 G DDR3 memory using Windows XP.The test functions are listed in Table1. The test functions contain trigonometric function, polynomial function, and exponential function in the list. And f1, f2, and f3 are two-dimension multiple hump functions; f4, f5, f6, f7, and f8 are high dimension functions. Each test function has only one optimal solution in feasible region, in which the minimum of f1 and f2 is 0 at [0,0], the minimum of f3 is 0 at [1,1], and the minimum of test functions f4, f5, f6, f7, and f8 is 0 at [0,0,…,0]. However, the test functions with high dimension will bring more difficulty in global and local search process.Table 1
The test functions.
Number
Function expression
Search space
f
m
i
n
1
f
1
x
1
,
x
2
=
0.5
+
sin
2
⁡
x
1
2
+
x
2
2
-
0.5
1
+
0.001
x
1
2
+
x
2
2
2
∑
X
X
x
i
∈
[
-
10,10
]
f
m
i
n
=
0
2
f
2
x
1
,
x
2
=
100
x
1
-
x
2
2
2
+
x
1
-
1
2
∑
X
X
x
i
∈
[
-
10,10
]
f
m
i
n
=
0
3
f
3
x
1
,
x
2
=
-
20
exp
⁡
-
0.2
x
1
2
+
x
2
2
2
-
e
x
p
cos
⁡
2
π
x
1
+
cos
⁡
2
π
x
2
2
+
exp
⁡
1
∑
X
X
x
i
∈
[
-
10,10
]
f
m
i
n
=
0
4
f
4
x
=
418.9829
n
+
∑
i
=
1
n
x
i
⋅
sin
⁡
x
i
,
n
=
10
∑
X
X
x
i
∈
[
-
500,500
]
f
m
i
n
=
0
5
f
5
x
=
∑
i
=
1
n
i
+
1
10
exp
⁡
x
i
-
x
i
-
5.5
,
n
=
10
∑
X
X
x
i
∈
[
-
5.12,5.12
]
f
m
i
n
=
0
6
f
6
x
=
1
4000
∑
i
=
1
n
-
1
x
i
2
-
∏
i
=
1
n
-
1
cos
⁡
x
i
i
+
1
+
1
,
n
=
20
∑
X
X
x
i
∈
[
-
100,100
]
f
m
i
n
=
0
7
f
7
x
=
∑
i
=
1
n
x
i
2
,
n
=
30
∑
X
X
x
i
∈
[
-
10,10
]
f
m
i
n
=
0
8
f
8
x
=
10
n
+
∑
i
=
1
n
x
i
2
-
10
∑
i
=
1
n
cos
⁡
2
π
x
i
,
n
=
30
x
i
∈
[
-
10,10
]
f
m
i
n
=
0In this experiment, the population size is 50 for GA, QEA, DCQGA, and ARQEA; the max generation is 500 for two-dimension test functionsf1, f2, and f3, and 3000 for high dimension test functions f4, f5, f6, f7, and f8. And the coding for GA, QEA, DCQGA, and ARQEA is implemented, respectively, as follows:(a)
GA adopts real coding. The real coding is adapted to every variable in GA. The selection operation employs roulette wheel selection, crossover probability is 0.8, and mutation probability is 0.01. The real coding for chromosome is(18)x1x2⋯xi⋯xn.(b)
QEA adopts Q-bit coding. The length of every variable is 12. The updating strategy employs the rotating gate based on check table. The coding for theith individual with n variables is(19)pi=α11α12⋯α1lβ11β12⋯β1l⋯αn1αn2⋯αnlβn1βn2⋯βnl.(c)
DCQGA adopts double chain real-coding scheme. The step size of rotation angle is0.001π; mutation probability is 0.05; the coding for the ith individual with n variables is(20)pi=cos⁡ti1sin⁡ti1cos⁡ti2sin⁡ti2⋯⋯cos⁡tinsin⁡tin,wherepic=(cos(ti1),cos(ti2),…,cos(tin)) and pis=(sin(ti1),sin(ti2),…,sin(tin)). pic and pis represent a chromosome pair that maps the unit space of n dimensions to the solution space by solution space transformation.(d)
ARQEA adopts real coding based on allele with (1) and (2) and employs hybrid updating strategy to update the alleles and the corresponding probability amplitude.In this experiment, we run repeatedly the above optimization algorithms for each test function and record the running results (including the optimal values, average values, worst values, and average run times) in different optimization algorithms. The comparison results for different optimization algorithms are shown in Table2. From the comparison results, we can find that the search accuracy of ARQEA is obviously superior to GA’s, QEA’s, and DCQGA’s in solving continuous optimization problem. In addition, the running time of ARQEA is faster than GA’s, QEA’s, and DCQGA’s as well.Table 2
Comparison with different optimization algorithms.
Test function
Evolutionary algorithms
Best value
Average value
Worst value
Running time (sec.)
f
1
QEA
3.4533
e
-
06
4.5658
e
-
04
1.3433
e
-
03
9.543
e
+
01
DCQGA
6.8996
e
-
08
4.3543
e
-
06
7.8732
e
-
04
6.526
GA
2.6704
e
-
11
6.368
4
e
-
03
9
.
7
032
e
-
03
8.654
ARQEA
3.0738
e
-
15
6.0451
e
-
15
2.0368
e
-
14
3.481
f
2
QEA
6.3275
e
-
04
5.2164
e
-
03
1.6233
e
-
02
5.569
e
+
01
DCQGA
5.5437
e
-
08
1.2654
e
-
06
4.3251
e
-
04
5.658
GA
1.5684
e
-
05
9
.
19
82
e
-
02
4
.
052
3
e
-
01
6.423
ARQEA
2.1055
e
-
13
4.5264
e
-
13
7.3382
e
-
13
1.291
f
3
QEA
1.6048
e
-
02
3.2418
e
-
02
5
.
25
29
e
-
02
4.1324
e
+
01
DCQGA
1.432
3
e
-
05
5
.
21
89
e
-
02
1
.
5917
1
e
-
01
6.4383
GA
1.2181
e
-
08
3.7907
e
-
04
6
.
3
203
e
-
03
2.2957
ARQEA
2.534
6
e
-
16
4.8491
e
-
13
2.1526
e
-
0
9
4.4252
f
4
QEA
5.0412
e
+
01
1.6542
e
+
02
3.47741
e
+
02
4.8342
+
03
DCQGA
2.4342
7.0424
e
+
01
2
.
429242
e
+
02
5.3226
e
+
01
GA
7.0136
e
-
04
2.0
751
e
+
01
2
.
3687
e
+
01
3.5501
e
+
01
ARQEA
1.2728
e
-
04
1.2728
e
-
04
1.2728
e
-
04
3.1341
e
+
01
f
5
QEA
4.9056
e
-
04
1
.
38
72
e
-
02
3
.
43
41
e
-
02
3.5231
e
+
02
DCQGA
7.3975
e
-
06
1.8576
e
-
05
3.9103
e
-
03
6.3342
e
+
01
GA
5.0090
e
-
08
1.4547
e
-
05
6.9581
e
-
05
4.7454
e
+
01
ARQEA
1.7982
e
-
16
3.2573
e
-
16
8.8818
e
-
16
5.0032
e
+
01
f
6
QEA
2.2667
e
-
01
3.3742
7
.
4107
3.3703
e
+
03
DCQGA
3.2541
2
.
3
371
5
.
7233
1.0399
e
+
02
GA
2.9913
e
-
03
2.3544
e
-
01
6
.
627
e
-
01
7.3251
e
+
01
ARQEA
9.96785
e
-
03
2
.
05
76
e
-
02
2
.
70
94
e
-
02
4
.
8
1
2
e
+
01
f
7
QEA
3.6544
e
-
02
4.7685
e
-
01
1.3276
3.586
e
+
0
3
DCQGA
8.9768
e
-
04
3.4765
e
-
03
5.5876
e
-
02
1.635
e
+
0
2
GA
6.0000
e
-
0
3
3.7400
e
-
0
2
0.2193
6.3324
e
+
01
ARQEA
4.9223
e
-
14
7.2357
e
-
12
8.5674
e
-
11
5.011
e
+
0
1
f
8
QEA
6.3267
e
-
0
3
2.6832
e
-
01
1.9519
1.278
e
+
04
DCQGA
3.5257
e
-
05
4.2347
e
-
04
7
.
086
3
e
-
01
2.8593
e
+
03
GA
2
.
64
32
e
-
02
1.4242
3.0274
8.07
e
+
01
ARQEA
4.1248
e
-
11
5.3442
e
-
10
9.3327
e
-
8
6.158
e
+
0
1Figure3 shows the comparison of the convergence optimized by QEA, DCQGA, and ARQEA, respectively. We employ logarithmic ordinate to analyze search accuracy and convergence rate. For two-dimension test functions f1, f2, and f3, the convergence curve of ARQEA shows rapid decline after 500 generations in solving continuous optimization problem. For high dimension test functions, the convergence rate of ARQEA is obviously superior to GA’s, QEA’s, and DCQGA’s, even though the global and local search processes become more difficult. So, due to diversity of allele and hybrid updating strategy, the convergence rate of ARQEA is superior to GA, QEA, and DCQGA.Figure 3
Comparison of convergence for GA, QEA, DCQGA, and ARQEA.
(a)
The convergence curve off1
(b)
The convergence curve off2
(c)
The convergence curve off3
(d)
The convergence curve off4
(e)
The convergence curve off5
(f)
The convergence curve off6
(g)
The convergence curve off7
(h)
The convergence curve off8


## 5. Conclusions

In this paper, we present an allele real-coded quantum evolutionary algorithm. The proposed algorithm employs real coding based on probability superposition to maintain the diversity of population and prevent overlong length of chromosome. In hybrid updating strategy, we employ different evolutionary mode for superior and inferior allele in order to balance global search and local search. By comparing with different optimization algorithms, the search accuracy and convergence rate of ARQEA are obviously superior to GA’s, QEA’s, and DCQGA’s in solving continuous optimization problem. For the future, we will analyze the influence on initial population to search accuracy and relationship between parameters in updating strategy and convergence rate.



---

*Source: 9891382-2016-01-10.xml*