# The Improvement of Quantum Genetic Algorithm and Its Application on Function Optimization

Authors: Huaixiao Wang; Jianyong Liu; Jun Zhi; Chengqun Fu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

To accelerate the evolutionary process and increase the probability to find the optimal solution, the following methods are proposed to improve the conventional quantum genetic algorithm: an improved method to determine the rotating angle, the self-adaptive rotating angle strategy, adding the quantum mutation operation and quantum disaster operation. The efficiency and accuracy to search the optimal solution of the algorithm are greatly improved. Simulation test shows that the improved quantum genetic algorithm is more effective than the conventional quantum genetic algorithm to solve some optimization problems.


---

## Body

## 1. Introduction

Quantum genetic algorithm (QGA) is the product of the combination of quantum computation and genetic algorithms, and it is a new evolutionary algorithm of probability [1].  In 1996, quantum genetic algorithm is first proposed by Narayanan and Moore, and it is successfully used to solve the TSP problem [2]. QGA is essentially a kind of genetic algorithm and can be applied in the field that the conventional genetic algorithm can be applied. The efficiency of QGA is significantly better than the conventional genetic algorithm. The QGA is with a small value of the population, a fast speed of convergence, a great capability of global optimization, and a good robustness. The quantum state vector is introduced in the Genetic Algorithm to express genetic code, and quantum logic gates are used to realize the chromosome evolution. By these means, better results are achieved. However, there are still some problems in conventional QGA [3, 4]. For example, determining the direction of the rotating angle relies on a lookup table. It leads to a program with multiple judgment conditions. Moreover, the fixed rotating angle has a negative impact on the quickly searching and the lately convergence [5]. Aiming to resolve the above problem, the QGA is improved with an adaptive evolution process in this paper. Quantum mutation and quantum disaster operations are also introduced to make the algorithm with a better performance.Quantum computation is contrary to classical computation. It uses the superposition, coherence, and the entanglement of different qubits of quantum state to realize quantum computation [6]. Quantum computation is the product of quantum mechanics applying in the field of algorithm. The ability of parallelism is the essential difference between quantum computation and classical computation. In the probability calculation, the system is not in an invariable state. Conversely, it has a certain probability, and the state probability vector is corresponding to different possible states. Quantum computation is similar to it, the probability amplitudes of quantum states is used in quantum computation, and probability amplitudes of quantum states are squared normalized, so the speed of calculation of quantum computation is N times faster than the speed of classic calculation. Quantum transformation is realized by quantum rotating gates. There are some special properties of quantum computation relative to classical computation [7]. Some mechanisms of these properties can be introduced to the optimization algorithms for improving traditional optimization algorithm.(1) Superposition of quantum computation: the basic unit for information storage is qubit in the quantum computer [8]. An n-bits quantum register can be in the state |ϕ〉 which is the coherent superposition state of 2n ground states. An act on an n-bits quantum register is equal to the act on 2n numbers. The relationship between superposition state and ground states is
(1)|ϕ〉=∑ici|ϕi〉,
where ci represents the probability amplitude of the state |ϕi〉; |ci|2 represents the probability to collapse to the ground state |ϕi〉 when the state |ϕ〉 is measured; ci should satisfy the condition [9]:
(2)∑i|ci|2=1.(2) Coherence of quantum computation: different from classical computation, coherence is another important property of quantum computation. The relative phase of the respective ground states changes with the interference that occurs to each ground state by the action of quantum rotating gates. For example, a quantum system of a single qubit is|ϕ〉=c1|0〉+c2|1〉 and |c1|2+|c2|2=1. After the role of some quantum gate, the values of c1 and c2 change correspondingly, and the new c1 and c2 still satisfy |c1|2+|c2|2=1. So the probability amplitude of the ground state |1〉 will be reduced if the probability amplitude of the ground state |0〉 increases. When the quantum system is measured, coherence will disappear and collapse to some ground state, while the probability is determined by |ci|2.(3) Entanglement of the quantum state: the quantum state which cannot be broken down into the form of the direct product of two subsystems is called entanglement state [10]. Both the operated state of the qubit and the state of the other qubit entangled are changed once operating on one or more specific qubits.(4) Parallelism of the quantum computation: parallelism of quantum computation is completed in the same quantum circuit rather than being implemented by multiple hardwares calculated simultaneously. Parallelism of quantum computation makes use of the superimposed ability of different states which the quantum computer lies in; therefore, using a singlef(x) circuit can calculate multiple values of x.


## 2. Conventional Quantum Genetic Algorithm

Quantum genetic algorithm is proposed based on the concept of quantum bits and quantum superposition state [11]. In a quantum computer, a double quanta system called qubit acts as the physical media to store the information units. Qubit is the smallest unit of information in quantum computers. A qubit can be in any state |0〉, |1〉, and superposition state between |0〉 and |1〉 [12]. A state of a qubit is described as
(3)|φ〉=α|0〉+β|1〉,
where α and β are the complex numbers which are called the probability amplitude of corresponding state of qubit and satisfy the condition that |α|2+|β|2=1. The states |0〉 and |1〉, respectively, denote the spin-down state and spin-up state [13]. A qubit can contain the information of both the state |0〉 and the state |1〉.


### 2.1. Qubit Encoding

Binary code is used to encode qubit on the polymorphic problem. A qubit can be defined by its probability amplitude as[αβ], and the multiqubits encoding which has m parameters is defined as follows:(4)qjt=[α11tβ11t|α12tβ12t|⋯⋯|α1ktβ1kt|α21tβ21t|α22tβ22t|⋯⋯|α2ktβ2kt|αm1tβm1t|αm2tβm2t|⋯⋯|αmktβmtt],where qjt represents the jth individual chromosome of the tth generation; k represents the number of qubit encoding of each gene; m represents the number of genes in the chromosome [14].Initialize the quantum encoding(α,β) of each individual in the population with (1/2,1/2), which indicates that when t=0, the possibility of each state expressed by a chromosomal is equal [15].


### 2.2. Quantum Rotating Gates

Compared with the conventional genetic algorithm, quantum genetic algorithm applies the probability amplitude of qubits to encode chromosome and uses quantum rotating gates to realize chromosomal updated operation. Since the chromosomes are in superposition state or entanglement state, the generation of offspring is not determined by the parent group when the Quantum rotating gates is used to realize the genetic operation. It is jointly determined by the optimal individual of the parent group and probability amplitude of each state. In other words, the genetic manipulation of quantum genetic algorithm is mainly through acting on the superposition state or entanglement state by the Quantum rotating gates to change the probability amplitude. Therefore, the construction of Quantum rotating gates is the key issue of quantum genetic algorithm [16], and it directly affects the performance of the algorithm.Quantum rotating gates can be designed according to the practical problems and usually can be defined as(5)U(θi)=[cosθi-sinθisinθicosθi].
The updated process is
(6)[αi′βi′]=U(θi)[αiβi]=[cosθi-sinθisinθicosθi][αiβi],
where (αi,βi)T and (αi′,βi′)T are the probability amplitudes of the ith qubit in chromosome before and after the quantum rotating gates updating, respectively; θi is the rotating angle; the value and the sign of θi are determined by the adjustment strategy [17], which are shown in Table 1. Moreover, xi is the ith bit of the current chromosome; besti is the ith bit of the current optimal chromosome; f(x) is the fitness function; s(αi,βi) is the direction of the rotating angle; Δθi is the value of the rotating angle. The value of Δθi is determined by certain adjustment strategy, in conventional quantum genetic algorithm and the value of Δθi is generally a constant value is around 0.01π. The adjustment strategy is, comparing the fitness of the currently measured value f(x) of the individual qjt with the fitness of the current optimal individual f(besti), if f(x)>f(best), then adjust the corresponding qubits of qjt, making the probability amplitude (αi,βi) evolves toward the direction that is propitious to the emergence of xi. Conversely, if f(x)<f(best), then adjust the corresponding qubits of qjt, making the probability amplitude (αi,βi) evolves toward the direction that is propitious to the emergence of best.Table 1
Adjustment strategy of rotating angle.
x
i
bes
t
i
f
(
x
)
>
f
(
best
)
Δ
θ
i
s
(
α
i
,
β
i
)
α
i
β
i
>
0
α
i
β
i
<
0
α
i
=
0
β
i
=
0
0
0
FALSE
0
0
0
0
0
0
0
TRUE
0
0
0
0
0
0
1
FALSE
Δ
θ
i
+1
−1
0
±
1
0
1
TRUE
Δ
θ
i
−1
+1
±
1
0
1
0
FALSE
Δ
θ
i
−1
+1
±
1
0
1
0
TRUE
Δ
θ
i
+1
−1
0
±
1
1
1
FALSE
0
0
0
0
0
1
1
TRUE
0
0
0
0
0


### 2.3. Analysis on the Characteristic of Quantum Genetic Algorithm

Quantum genetic algorithm is a more wonderful optimization process than the conventional genetic algorithm, and its encoding mode is more complex, and each generation of the evolution can cover a wider area [18]. Quantum genetic algorithm combines some characteristics of quantum computation with the genetic algorithm whose individuals are chosen by the natural selection. The fine species better adapt to environment of quantum genetic algorithm are produced by the operation of quantum rotating gates with the goal of the best individual of current generation [19]. The main features of quantum genetic algorithm are as follows.(1) QGA is self-organizing, self-adaptive, and self-learning [20]. (2) The object handling by QGA is not the parameter, but the chromosome strings encoded according to parameter variable [21]. The encoding operation enables the quantum genetic algorithm to operate directly on the structure of the object. (3) QGA searches a group of points rather than a single point in the solution space at the same time. QGA samples in different areas of space simultaneously [22]. (4) In QGA, the knowledge of the searching space or other ancillary information is not needed. Only the fitness function is used to evaluate the individuals [23].The flowchart of conventional quantum genetic algorithm is shown in Figure1.Figure 1
Flowchart of conventional quantum genetic algorithm.


## 2.1. Qubit Encoding

Binary code is used to encode qubit on the polymorphic problem. A qubit can be defined by its probability amplitude as[αβ], and the multiqubits encoding which has m parameters is defined as follows:(4)qjt=[α11tβ11t|α12tβ12t|⋯⋯|α1ktβ1kt|α21tβ21t|α22tβ22t|⋯⋯|α2ktβ2kt|αm1tβm1t|αm2tβm2t|⋯⋯|αmktβmtt],where qjt represents the jth individual chromosome of the tth generation; k represents the number of qubit encoding of each gene; m represents the number of genes in the chromosome [14].Initialize the quantum encoding(α,β) of each individual in the population with (1/2,1/2), which indicates that when t=0, the possibility of each state expressed by a chromosomal is equal [15].


## 2.2. Quantum Rotating Gates

Compared with the conventional genetic algorithm, quantum genetic algorithm applies the probability amplitude of qubits to encode chromosome and uses quantum rotating gates to realize chromosomal updated operation. Since the chromosomes are in superposition state or entanglement state, the generation of offspring is not determined by the parent group when the Quantum rotating gates is used to realize the genetic operation. It is jointly determined by the optimal individual of the parent group and probability amplitude of each state. In other words, the genetic manipulation of quantum genetic algorithm is mainly through acting on the superposition state or entanglement state by the Quantum rotating gates to change the probability amplitude. Therefore, the construction of Quantum rotating gates is the key issue of quantum genetic algorithm [16], and it directly affects the performance of the algorithm.Quantum rotating gates can be designed according to the practical problems and usually can be defined as(5)U(θi)=[cosθi-sinθisinθicosθi].
The updated process is
(6)[αi′βi′]=U(θi)[αiβi]=[cosθi-sinθisinθicosθi][αiβi],
where (αi,βi)T and (αi′,βi′)T are the probability amplitudes of the ith qubit in chromosome before and after the quantum rotating gates updating, respectively; θi is the rotating angle; the value and the sign of θi are determined by the adjustment strategy [17], which are shown in Table 1. Moreover, xi is the ith bit of the current chromosome; besti is the ith bit of the current optimal chromosome; f(x) is the fitness function; s(αi,βi) is the direction of the rotating angle; Δθi is the value of the rotating angle. The value of Δθi is determined by certain adjustment strategy, in conventional quantum genetic algorithm and the value of Δθi is generally a constant value is around 0.01π. The adjustment strategy is, comparing the fitness of the currently measured value f(x) of the individual qjt with the fitness of the current optimal individual f(besti), if f(x)>f(best), then adjust the corresponding qubits of qjt, making the probability amplitude (αi,βi) evolves toward the direction that is propitious to the emergence of xi. Conversely, if f(x)<f(best), then adjust the corresponding qubits of qjt, making the probability amplitude (αi,βi) evolves toward the direction that is propitious to the emergence of best.Table 1
Adjustment strategy of rotating angle.
x
i
bes
t
i
f
(
x
)
>
f
(
best
)
Δ
θ
i
s
(
α
i
,
β
i
)
α
i
β
i
>
0
α
i
β
i
<
0
α
i
=
0
β
i
=
0
0
0
FALSE
0
0
0
0
0
0
0
TRUE
0
0
0
0
0
0
1
FALSE
Δ
θ
i
+1
−1
0
±
1
0
1
TRUE
Δ
θ
i
−1
+1
±
1
0
1
0
FALSE
Δ
θ
i
−1
+1
±
1
0
1
0
TRUE
Δ
θ
i
+1
−1
0
±
1
1
1
FALSE
0
0
0
0
0
1
1
TRUE
0
0
0
0
0


## 2.3. Analysis on the Characteristic of Quantum Genetic Algorithm

Quantum genetic algorithm is a more wonderful optimization process than the conventional genetic algorithm, and its encoding mode is more complex, and each generation of the evolution can cover a wider area [18]. Quantum genetic algorithm combines some characteristics of quantum computation with the genetic algorithm whose individuals are chosen by the natural selection. The fine species better adapt to environment of quantum genetic algorithm are produced by the operation of quantum rotating gates with the goal of the best individual of current generation [19]. The main features of quantum genetic algorithm are as follows.(1) QGA is self-organizing, self-adaptive, and self-learning [20]. (2) The object handling by QGA is not the parameter, but the chromosome strings encoded according to parameter variable [21]. The encoding operation enables the quantum genetic algorithm to operate directly on the structure of the object. (3) QGA searches a group of points rather than a single point in the solution space at the same time. QGA samples in different areas of space simultaneously [22]. (4) In QGA, the knowledge of the searching space or other ancillary information is not needed. Only the fitness function is used to evaluate the individuals [23].The flowchart of conventional quantum genetic algorithm is shown in Figure1.Figure 1
Flowchart of conventional quantum genetic algorithm.


## 3. Improvements of Quantum Genetic Algorithm

There are some shortages in conventional quantum genetic algorithm [24]. (1) The premature convergence problem: conventional quantum genetic algorithm simply uses fitness to evaluate the solution, causing the genes of some individuals whose fitness is large to spread rapidly in the population, making the population loses diversity prematurely. The solution often falls into the local optimal solution; (2) local search ability: conventional quantum genetic algorithm is good at global search performance, but its local search performance is inadequate, resulting in slower convergence in the later stage of evolution and cannot converge to the global optimal solution.


### 3.1. Determination on Rotating Direction

In the optimization process, the value and direction of the quantum rotating gates are determined firstly. The current method to determine the direction of the rotating angle is based on a lookup table. As the lookup table involves judgment of multiple conditions, the efficiency of the algorithm is affected [25]. Therefore, a new method is introduced to simplify the determination of the direction of the rotating angle in this paper.Theorem 1.
Construct a determinantA=|αbαiβbβi|, where, (αb,βb) is the probability amplitude of some qubit of the optimal solution which has been searched. (αi,βi) is the probability amplitude of corresponding state of qubit in the current solution. When xi≠besti, if A≠0, then the direction of the rotating angle is—sgn(A). If A=0, the direction of the rotating angle can be either positive or negative.Proof.
The angles of the qubits[αb,βb]T and [αi,βi]T in the unit circle are separately θb and θi; then,
(7)A=|cosθbcosθisinθbsinθi|=sin(θi-θb).
If A≠0, when 0<|θi-θb|<π, sgn(Δθ)=-sgn(θi-θb)=-sgn(sin(θi-θb))=-sgnA and when π<|θi-θb|<2π, sgn(Δθ)=sgn(θi-θb)=-sgn(sin(θi-θb))=-sgnA. If A=0, then |θi-θb|=0 or π. Positive and negative rotating effect is the same at this time, so the direction of the rotating angle θ can be either positive or negative (proof is over).


### 3.2. Self-Adaptive Rotating Angle Strategy

The conventional quantum genetic algorithm adopts a rotating strategy with fixed angle. In this paper, a rotating strategy with self-adaptive angle is adopted. It can dynamically adjust the value of the rotating angle of the Quantum rotating gates based on the evolutionary process [26]. A large rotating angle is set early in the evolutionary process to quickly facilitate the entire interval and find the region with the optimal values​​. To accurately find the optimal value, we reduce the value of rotating angle, while the evolution increases. Measure the individual qjt and compare its fitness f(xj)t with the fitness f(best) of the best individual. Adjust the corresponding qubit in qjt based on the result of the above comparison and make (α,β) evolve to the direction of the optimal solution.The self-adaptive quantum genetic algorithm (AQGA) is proposed in this paper. AQGA adjusts the value of the rotating angle according to the situation of evolution of the population at any time.Adjust the value of the rotating angle according to the number of generation; the regulator is as the following formula:(8)θi=θmax-(θmax-θminitmax)*iter,
where θi is the value of the rotating angle of the ith generation, θmax is the maximal rotating angle, θmin is the minimal rotating angle, itmax is the maximal generation, and iter is the current generation. From the formula (8), it can be concluded that the value of the rotating angle θ is gradually reduced with the increase of the generation.


### 3.3. Add Quantum Mutation Operation

Add quantum mutation operation in conventional quantum genetic algorithm. Quantum mutation enables some individuals to deviate slightly from the current evolutionary direction and prevent the evolution of individual into a local optimal solution [27]. Quantum mutation can completely reverse the individual’s evolutionary direction by swapping the value of probability amplitude of qubits (α,β).Quantum mutation is an assistant operation with the purpose to enhance the local searching ability of quantum genetic algorithm and avoid the loss of important information in the population. Quantum NOT gates is adopted to realize chromosomal variation. Quantum NOT gate is applied to transform the selected number of qubits according to mutation probability randomly to transform corresponding probability amplitude of the qubits. Quantum mutation operation helps to increase the diversity of the population and reduce the probability of premature convergence.Pseudocode program of quantum mutation process is described as in Algorithm1.Algorithm 1
Procedure Mutate (pi)
Begin
Ifpi is not the current optimum chromosome then
Begin
j=0;
When (j<n)
j=j+1;
Generate Random Number rand in range (0,1);
If rand<α or rand <β
Exchangeα and β;
End
End


### 3.4. Add Quantum Disaster Operation

Add quantum disaster operation in the conventional quantum genetic algorithm. The algorithm may fall into local optimal solution, while the algorithm has performed several generations and the best individual is in a stable state. Thus, we need to take the quantum disaster operation to get out of the local optimal solution [28]. The method is to apply a large disturbance to some individuals in the population and regenerate some other new random individuals.Quantum disaster process pseudocode program is described as in Algorithm2.Algorithm 2
Begin
If (disaster-condition)
Begin
If (The chromosome is not the best chromosome)
Initialize the chromosome;
End
EndIt needs to be noted that the intercross operation is not added into the improved quantum genetic algorithm. The crossover operator is able to change the linear superposition state observation probability of the quantum chromosome. However, the quantum chromosome itself has the property of individual diversity resulted from quantum superposition. So, there is no need to perform the intercross operation. In contrast, if the intercross operation is used in some cases, the performance of QGA may decline [29].The flowchart of improved quantum genetic algorithm is shown in Figure2.Figure 2
Flowchart of improved quantum genetic algorithm.


## 3.1. Determination on Rotating Direction

In the optimization process, the value and direction of the quantum rotating gates are determined firstly. The current method to determine the direction of the rotating angle is based on a lookup table. As the lookup table involves judgment of multiple conditions, the efficiency of the algorithm is affected [25]. Therefore, a new method is introduced to simplify the determination of the direction of the rotating angle in this paper.Theorem 1.
Construct a determinantA=|αbαiβbβi|, where, (αb,βb) is the probability amplitude of some qubit of the optimal solution which has been searched. (αi,βi) is the probability amplitude of corresponding state of qubit in the current solution. When xi≠besti, if A≠0, then the direction of the rotating angle is—sgn(A). If A=0, the direction of the rotating angle can be either positive or negative.Proof.
The angles of the qubits[αb,βb]T and [αi,βi]T in the unit circle are separately θb and θi; then,
(7)A=|cosθbcosθisinθbsinθi|=sin(θi-θb).
If A≠0, when 0<|θi-θb|<π, sgn(Δθ)=-sgn(θi-θb)=-sgn(sin(θi-θb))=-sgnA and when π<|θi-θb|<2π, sgn(Δθ)=sgn(θi-θb)=-sgn(sin(θi-θb))=-sgnA. If A=0, then |θi-θb|=0 or π. Positive and negative rotating effect is the same at this time, so the direction of the rotating angle θ can be either positive or negative (proof is over).


## 3.2. Self-Adaptive Rotating Angle Strategy

The conventional quantum genetic algorithm adopts a rotating strategy with fixed angle. In this paper, a rotating strategy with self-adaptive angle is adopted. It can dynamically adjust the value of the rotating angle of the Quantum rotating gates based on the evolutionary process [26]. A large rotating angle is set early in the evolutionary process to quickly facilitate the entire interval and find the region with the optimal values​​. To accurately find the optimal value, we reduce the value of rotating angle, while the evolution increases. Measure the individual qjt and compare its fitness f(xj)t with the fitness f(best) of the best individual. Adjust the corresponding qubit in qjt based on the result of the above comparison and make (α,β) evolve to the direction of the optimal solution.The self-adaptive quantum genetic algorithm (AQGA) is proposed in this paper. AQGA adjusts the value of the rotating angle according to the situation of evolution of the population at any time.Adjust the value of the rotating angle according to the number of generation; the regulator is as the following formula:(8)θi=θmax-(θmax-θminitmax)*iter,
where θi is the value of the rotating angle of the ith generation, θmax is the maximal rotating angle, θmin is the minimal rotating angle, itmax is the maximal generation, and iter is the current generation. From the formula (8), it can be concluded that the value of the rotating angle θ is gradually reduced with the increase of the generation.


## 3.3. Add Quantum Mutation Operation

Add quantum mutation operation in conventional quantum genetic algorithm. Quantum mutation enables some individuals to deviate slightly from the current evolutionary direction and prevent the evolution of individual into a local optimal solution [27]. Quantum mutation can completely reverse the individual’s evolutionary direction by swapping the value of probability amplitude of qubits (α,β).Quantum mutation is an assistant operation with the purpose to enhance the local searching ability of quantum genetic algorithm and avoid the loss of important information in the population. Quantum NOT gates is adopted to realize chromosomal variation. Quantum NOT gate is applied to transform the selected number of qubits according to mutation probability randomly to transform corresponding probability amplitude of the qubits. Quantum mutation operation helps to increase the diversity of the population and reduce the probability of premature convergence.Pseudocode program of quantum mutation process is described as in Algorithm1.Algorithm 1
Procedure Mutate (pi)
Begin
Ifpi is not the current optimum chromosome then
Begin
j=0;
When (j<n)
j=j+1;
Generate Random Number rand in range (0,1);
If rand<α or rand <β
Exchangeα and β;
End
End


## 3.4. Add Quantum Disaster Operation

Add quantum disaster operation in the conventional quantum genetic algorithm. The algorithm may fall into local optimal solution, while the algorithm has performed several generations and the best individual is in a stable state. Thus, we need to take the quantum disaster operation to get out of the local optimal solution [28]. The method is to apply a large disturbance to some individuals in the population and regenerate some other new random individuals.Quantum disaster process pseudocode program is described as in Algorithm2.Algorithm 2
Begin
If (disaster-condition)
Begin
If (The chromosome is not the best chromosome)
Initialize the chromosome;
End
EndIt needs to be noted that the intercross operation is not added into the improved quantum genetic algorithm. The crossover operator is able to change the linear superposition state observation probability of the quantum chromosome. However, the quantum chromosome itself has the property of individual diversity resulted from quantum superposition. So, there is no need to perform the intercross operation. In contrast, if the intercross operation is used in some cases, the performance of QGA may decline [29].The flowchart of improved quantum genetic algorithm is shown in Figure2.Figure 2
Flowchart of improved quantum genetic algorithm.


## 4. Simulation Test

The simulation test in this paper is based on the AMD CPU 1.8 GHz, 1.5 GB RAM; the algorithm is written and compiled in MATLAB.


### 4.1. Problem Description

Find the optimal solution in the complex binary function:(9)maxf(x,y)=xsin(4πx)+ysin(20πy),-3.0≤x1≤12.1,4.1≤x2≤5.9.The figure of the function is shown in Figure3.Figure 3
Function figure.The parameters are set as follows. Both the conventional quantum genetic algorithm and improved quantum genetic algorithm are encoded by the binary; the evolution generation is 200; the size of population is 40; the length of each binary variable is 20; fitness function is the objective function. Take 10 times simulation test using conventional quantum genetic algorithm and its improved method, respectively.


### 4.2. The Results of Conventional Quantum Genetic Algorithm

The results of the conventional quantum genetic algorithm are shown in Table2.Table 2
The results of the conventional quantum genetic algorithm.
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6255
11.6254
11.6281
11.6255
11.6256
11.6255
11.6256
11.6255
11.6255
11.6281
x
2
5.72504
5.32505
5.72509
5.72505
5.72529
5.72504
5.72529
5.72496
5.72505
5.72504
Optimal value
17.3503
16.9503
17.3441
17.3503
17.3496
17.3503
17.3496
17.3502
17.3503
17.3441
Evolution generations
130
110
80
100
80
90
110
180
110
60Make a census of the data in Table2, the statistical results are shown in Table 3.Table 3
The statistical results of conventional quantum genetic algorithm.
Algorithm
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
CQGA
(11.6255, 5.72504, 17.3503)
(11.6254, 5.32505, 16.9503)
180
60
105
5The result of 200 generations’ evolutionary process of a certain time of conventional quantum genetic algorithm is shown in Figure4. The conventional quantum genetic algorithm obtains the optimal solution around 130 generation. Evolutionary process is slower between 50 and 110 generations. The x-axis represents the evolutionary generations; y-axis represents the best fitness of every generation. (The meaning of the x-axis and the y-axis of the following figure is the same as Figure 4).Figure 4
Evolutionary process of conventional quantum genetic algorithm.


### 4.3. Result of Self-Adaptive Quantum Genetic Algorithm

The rotating angle adaptively changes with the evolution generation based on the conventional quantum genetic algorithm. Four cases are tested in this paper; the maximum rotating angle and the minimum rotating angle of the four cases are, respectively, (0.008π, 0.1π), (0.01π, 0.1π), (0.01π, 0.05π), and (0.005π, 0.05π). Take 10 rounds of the experiments for the four cases; the experimental results were shown in Tables 4, 5, 6, 7, and 8, respectively.Table 4
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.008π, 0.1π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6245
10.1024
11.6244
11.6255
11.6281
11.6255
11.6244
11.1256
11.6254
11.6255
x
2
5.72505
5.72504
5.42813
5.72363
5.72504
5.42813
5.3252
5.72503
5.72504
5.72503
Optimal value
17.3503
15.8483
16.9479
17.3278
17.3278
16.949
16.9489
16.8503
17.3503
17.3503
Evolution generations
20
20
10
70
20
30
20
40
25
10Table 5
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.01π, 0.1π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6255
11.6263
11.6255
11.6255
11.6255
11.6256
11.6254
10.1256
11.6255
11.6254
x
2
5.72504
5.62735
5.72695
5.32499
4.92344
5.3252
5.32504
5.32505
5.72695
5.72509
Optimal value
17.3503
17.1911
17.3091
16.9503
16.525
16.9501
16.9503
15.4503
17.3091
17.3503
Evolution generations
20
10
18
20
20
20
45
30
30
70Table 6
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.01π, 0.05π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
10.1256
11.6255
11.6255
11.6255
11.6255
11.6255
11.6255
11.6255
11.6281
11.6281
x
2
5.72509
5.52504
5.72504
5.72529
5.72509
5.32505
5.72509
5.12504
5.72504
5.52441
Optimal value
15.8503
17.1503
17.3503
17.3496
17.3503
16.9503
17.3503
16.7503
17.3441
17.1398
Evolution generations
30
40
30
30
30
20
30
30
30
20Table 7
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.005π, 0.05π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6255
11.6281
11.6255
11.6255
11.6254
11.6255
11.6255
11.6281
11.6255
11.6255
x
2
5.32504
5.72488
5.72503
4.92504
5.72504
5.72509
5.72504
5.3252
5.52441
5.72504
Optimal value
16.9503
17.3438
17.3503
16.5503
17.3503
17.3503
17.3503
16.9439
17.1459
17.3503
Evolution generations
40
40
70
30
45
30
50
20
50
50Table 8
The statistical results of self-adaptive quantum genetic algorithm.
Rotating strategy
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
(0.008π, 0.1π)
(11.6255, 5.72503, 17.3503)
(10.1024, 5.72504, 15.8483)
70
10
26.5
3
(0.01π, 0.1π)
(11.6255, 5.72504, 17.3503)
(10.1256, 5.32505, 15.4503)
70
10
28.3
2
(0.01π, 0.05π)
(11.6255, 5.72504, 17.3503)
(10.1256, 5.72509, 15.8503)
40
20
29
4
(0.005π, 0.05π)
(11.6255, 5.72503, 17.3503)
(11.6255, 4.92504, 16.5503)
70
20
42.5
5Make a census of the experimental data in Tables4, 5, 6, and 7, the statistical results are shown in Table 8.According to the data in Table8, the rotating strategy is selected (0.005π, 0.05π) in this paper.


### 4.4. The Result of Self-Adaptive Quantum Genetic Algorithm in which Mutation Operation Is Added

The mutation operation is added based on the self-adaptive quantum genetic algorithm, and the probability of mutation is 0.001. Table9 shows the statistical results of the experiment by performing the algorithm 10 times. We can get the conclusion that the speed of evolution is improved again.Table 9
The statistical results of adaptive mutation quantum genetic algorithm.
Rotating strategy
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
(0.005π, 0.05π)
(11.6255, 5.72503, 17.3503)
(11.6288, 5.32489, 16.9405)
50
20
35
6One certain time of the evolution process is shown in Figure6. Through the evolutionary process in Figure 6, we can get that the optimal solution is obtained around the 30th generation. The speed of evolution is improved again, and times of convergence are also increased.


### 4.5. The Result of Self-Adaptive Mutation Quantum Genetic Algorithm Added Disaster Operation

The disaster operation is added based on the self-adaptive mutation quantum genetic algorithm. Table10 shows the statistical results of the experiment by performing the algorithm 10 times. We can get the conclusion that the times of convergence of self-adaptive mutation quantum genetic algorithm adding disaster operation have been improved, and the biggest evolution generation is largely more than the algorithm without disaster operation; the reason is that usually the disaster operation happens late in the evolution. The disaster operation makes the times of convergence improved, but the biggest evolution generation unavoidably becomes more.Table 10
The statistical results of adaptive mutation quantum genetic algorithm added disaster operation.
Rotating strategy
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
(0.005π, 0.05π)
(11.6255, 5.72503, 17.3503)
(11.6254, 5.52525, 17.1498)
150
20
65
8An evolutionary process is shown in Figure7.


### 4.6. Analysis on Evolutionary Process of Self-Adaptive Quantum Genetic Algorithm Added Intercross Operation

As mentioned previously, the improved quantum genetic algorithm cannot add the intercross operation [30]. Adding the intercross operation will decline the efficiency of the algorithm. The evolution process of self-adaptive quantum genetic algorithm with the adding intercross operation is shown in Figures 8 and 9. Compare Figure 5 with Figure 8, the optimal solution is obtained from 50 generation to 120 generation, and the evolutionary generation becomes more. Compare Figure 6 with Figure 9, the optimal solution is obtained from the 30th generation to the 120th generation, and the evolutionary generation becomes more too. Adding intercross operation makes the evolution faster in early generation and becomes unstable late in the evolutional process. So, it cannot add intercross operation into the improved quantum genetic algorithm.Figure 5
Evolutionary process of self-adaptive quantum genetic algorithm.Figure 6
Evolutionary process of self-adaptive quantum genetic algorithm in which mutation operation is added.Figure 7
Evolutionary process of self-adaptive mutation quantum genetic algorithm added disaster operation.Figure 8
Evolutionary process of self-adaptive quantum genetic algorithm adding the intercross operation.Figure 9
Evolutionary process of self-adaptive quantum genetic algorithm adding the intercross and mutation operation.


### 4.7. Comparison of Time between the Two Methods to Determine Rotating Angle Direction

Take 8 times of experiments separately using the conventional method and the method of this paper to determine the rotating angle direction; get rid of the largest and smallest group, respectively, and the time of the rest 6 groups is shown in Table11.Table 11
Comparison of the results of the two methods to determine rotating angle direction.
The first time(s)
The second time(s)
The third time(s)
The fourth time(s)
The fifth time(s)
The sixth time(s)
Maximal time value(s)
Minimal time value(s)
Average time value(s)
Time of conventional method
12.6389
12.9520
11.7157
12.7594
11.9885
12.6437
12.9520
11.7157
12.4497
Time of improved method
10.0858
10.2260
10.4878
12.3171
10.2552
10.3130
12.3171
10.0858
10.6142From Table11, it can be concluded that the average running time of the improved method to determine the rotating angle direction is significantly shorter than the time of conventional method. The efficiency of algorithm is improved.


## 4.1. Problem Description

Find the optimal solution in the complex binary function:(9)maxf(x,y)=xsin(4πx)+ysin(20πy),-3.0≤x1≤12.1,4.1≤x2≤5.9.The figure of the function is shown in Figure3.Figure 3
Function figure.The parameters are set as follows. Both the conventional quantum genetic algorithm and improved quantum genetic algorithm are encoded by the binary; the evolution generation is 200; the size of population is 40; the length of each binary variable is 20; fitness function is the objective function. Take 10 times simulation test using conventional quantum genetic algorithm and its improved method, respectively.


## 4.2. The Results of Conventional Quantum Genetic Algorithm

The results of the conventional quantum genetic algorithm are shown in Table2.Table 2
The results of the conventional quantum genetic algorithm.
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6255
11.6254
11.6281
11.6255
11.6256
11.6255
11.6256
11.6255
11.6255
11.6281
x
2
5.72504
5.32505
5.72509
5.72505
5.72529
5.72504
5.72529
5.72496
5.72505
5.72504
Optimal value
17.3503
16.9503
17.3441
17.3503
17.3496
17.3503
17.3496
17.3502
17.3503
17.3441
Evolution generations
130
110
80
100
80
90
110
180
110
60Make a census of the data in Table2, the statistical results are shown in Table 3.Table 3
The statistical results of conventional quantum genetic algorithm.
Algorithm
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
CQGA
(11.6255, 5.72504, 17.3503)
(11.6254, 5.32505, 16.9503)
180
60
105
5The result of 200 generations’ evolutionary process of a certain time of conventional quantum genetic algorithm is shown in Figure4. The conventional quantum genetic algorithm obtains the optimal solution around 130 generation. Evolutionary process is slower between 50 and 110 generations. The x-axis represents the evolutionary generations; y-axis represents the best fitness of every generation. (The meaning of the x-axis and the y-axis of the following figure is the same as Figure 4).Figure 4
Evolutionary process of conventional quantum genetic algorithm.


## 4.3. Result of Self-Adaptive Quantum Genetic Algorithm

The rotating angle adaptively changes with the evolution generation based on the conventional quantum genetic algorithm. Four cases are tested in this paper; the maximum rotating angle and the minimum rotating angle of the four cases are, respectively, (0.008π, 0.1π), (0.01π, 0.1π), (0.01π, 0.05π), and (0.005π, 0.05π). Take 10 rounds of the experiments for the four cases; the experimental results were shown in Tables 4, 5, 6, 7, and 8, respectively.Table 4
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.008π, 0.1π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6245
10.1024
11.6244
11.6255
11.6281
11.6255
11.6244
11.1256
11.6254
11.6255
x
2
5.72505
5.72504
5.42813
5.72363
5.72504
5.42813
5.3252
5.72503
5.72504
5.72503
Optimal value
17.3503
15.8483
16.9479
17.3278
17.3278
16.949
16.9489
16.8503
17.3503
17.3503
Evolution generations
20
20
10
70
20
30
20
40
25
10Table 5
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.01π, 0.1π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6255
11.6263
11.6255
11.6255
11.6255
11.6256
11.6254
10.1256
11.6255
11.6254
x
2
5.72504
5.62735
5.72695
5.32499
4.92344
5.3252
5.32504
5.32505
5.72695
5.72509
Optimal value
17.3503
17.1911
17.3091
16.9503
16.525
16.9501
16.9503
15.4503
17.3091
17.3503
Evolution generations
20
10
18
20
20
20
45
30
30
70Table 6
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.01π, 0.05π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
10.1256
11.6255
11.6255
11.6255
11.6255
11.6255
11.6255
11.6255
11.6281
11.6281
x
2
5.72509
5.52504
5.72504
5.72529
5.72509
5.32505
5.72509
5.12504
5.72504
5.52441
Optimal value
15.8503
17.1503
17.3503
17.3496
17.3503
16.9503
17.3503
16.7503
17.3441
17.1398
Evolution generations
30
40
30
30
30
20
30
30
30
20Table 7
The result of self-adaptive quantum genetic algorithm with the rotating strategy selected (0.005π, 0.05π).
Index
Times
1
2
3
4
5
6
7
8
9
10
x
1
11.6255
11.6281
11.6255
11.6255
11.6254
11.6255
11.6255
11.6281
11.6255
11.6255
x
2
5.32504
5.72488
5.72503
4.92504
5.72504
5.72509
5.72504
5.3252
5.52441
5.72504
Optimal value
16.9503
17.3438
17.3503
16.5503
17.3503
17.3503
17.3503
16.9439
17.1459
17.3503
Evolution generations
40
40
70
30
45
30
50
20
50
50Table 8
The statistical results of self-adaptive quantum genetic algorithm.
Rotating strategy
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
(0.008π, 0.1π)
(11.6255, 5.72503, 17.3503)
(10.1024, 5.72504, 15.8483)
70
10
26.5
3
(0.01π, 0.1π)
(11.6255, 5.72504, 17.3503)
(10.1256, 5.32505, 15.4503)
70
10
28.3
2
(0.01π, 0.05π)
(11.6255, 5.72504, 17.3503)
(10.1256, 5.72509, 15.8503)
40
20
29
4
(0.005π, 0.05π)
(11.6255, 5.72503, 17.3503)
(11.6255, 4.92504, 16.5503)
70
20
42.5
5Make a census of the experimental data in Tables4, 5, 6, and 7, the statistical results are shown in Table 8.According to the data in Table8, the rotating strategy is selected (0.005π, 0.05π) in this paper.


## 4.4. The Result of Self-Adaptive Quantum Genetic Algorithm in which Mutation Operation Is Added

The mutation operation is added based on the self-adaptive quantum genetic algorithm, and the probability of mutation is 0.001. Table9 shows the statistical results of the experiment by performing the algorithm 10 times. We can get the conclusion that the speed of evolution is improved again.Table 9
The statistical results of adaptive mutation quantum genetic algorithm.
Rotating strategy
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
(0.005π, 0.05π)
(11.6255, 5.72503, 17.3503)
(11.6288, 5.32489, 16.9405)
50
20
35
6One certain time of the evolution process is shown in Figure6. Through the evolutionary process in Figure 6, we can get that the optimal solution is obtained around the 30th generation. The speed of evolution is improved again, and times of convergence are also increased.


## 4.5. The Result of Self-Adaptive Mutation Quantum Genetic Algorithm Added Disaster Operation

The disaster operation is added based on the self-adaptive mutation quantum genetic algorithm. Table10 shows the statistical results of the experiment by performing the algorithm 10 times. We can get the conclusion that the times of convergence of self-adaptive mutation quantum genetic algorithm adding disaster operation have been improved, and the biggest evolution generation is largely more than the algorithm without disaster operation; the reason is that usually the disaster operation happens late in the evolution. The disaster operation makes the times of convergence improved, but the biggest evolution generation unavoidably becomes more.Table 10
The statistical results of adaptive mutation quantum genetic algorithm added disaster operation.
Rotating strategy
The optimal result
The worst result
The biggest evolution generation
The smallest evolution generation
The average evolution generation
Times of convergence
(0.005π, 0.05π)
(11.6255, 5.72503, 17.3503)
(11.6254, 5.52525, 17.1498)
150
20
65
8An evolutionary process is shown in Figure7.


## 4.6. Analysis on Evolutionary Process of Self-Adaptive Quantum Genetic Algorithm Added Intercross Operation

As mentioned previously, the improved quantum genetic algorithm cannot add the intercross operation [30]. Adding the intercross operation will decline the efficiency of the algorithm. The evolution process of self-adaptive quantum genetic algorithm with the adding intercross operation is shown in Figures 8 and 9. Compare Figure 5 with Figure 8, the optimal solution is obtained from 50 generation to 120 generation, and the evolutionary generation becomes more. Compare Figure 6 with Figure 9, the optimal solution is obtained from the 30th generation to the 120th generation, and the evolutionary generation becomes more too. Adding intercross operation makes the evolution faster in early generation and becomes unstable late in the evolutional process. So, it cannot add intercross operation into the improved quantum genetic algorithm.Figure 5
Evolutionary process of self-adaptive quantum genetic algorithm.Figure 6
Evolutionary process of self-adaptive quantum genetic algorithm in which mutation operation is added.Figure 7
Evolutionary process of self-adaptive mutation quantum genetic algorithm added disaster operation.Figure 8
Evolutionary process of self-adaptive quantum genetic algorithm adding the intercross operation.Figure 9
Evolutionary process of self-adaptive quantum genetic algorithm adding the intercross and mutation operation.


## 4.7. Comparison of Time between the Two Methods to Determine Rotating Angle Direction

Take 8 times of experiments separately using the conventional method and the method of this paper to determine the rotating angle direction; get rid of the largest and smallest group, respectively, and the time of the rest 6 groups is shown in Table11.Table 11
Comparison of the results of the two methods to determine rotating angle direction.
The first time(s)
The second time(s)
The third time(s)
The fourth time(s)
The fifth time(s)
The sixth time(s)
Maximal time value(s)
Minimal time value(s)
Average time value(s)
Time of conventional method
12.6389
12.9520
11.7157
12.7594
11.9885
12.6437
12.9520
11.7157
12.4497
Time of improved method
10.0858
10.2260
10.4878
12.3171
10.2552
10.3130
12.3171
10.0858
10.6142From Table11, it can be concluded that the average running time of the improved method to determine the rotating angle direction is significantly shorter than the time of conventional method. The efficiency of algorithm is improved.


## 5. Conclusions

In this paper, six rounds of experiments were presented in this paper. We performed the experiments in each round for 10 tests. The experiments show that the conventional quantum genetic algorithm has been improved by adding many improvements. The simulation test shows that to improve the evolution efficiency of quantum genetic algorithm, some proper operations can be added in the evolutionary process; however, not all improvement strategies which can be applied to traditional genetic algorithms can be used to improve the conventional quantum genetic algorithm; it is because of the specificity of the conventional quantum genetic algorithm. The improvements made in this paper improve the algorithm structure, and efficiency of evolution of the conventional quantum genetic algorithm is also improved.



---

*Source: 730749-2013-05-08.xml*