Received 15 March 2015; accepted 22 August 2015; published 25 August 2015

ABSTRACT

To enhance the performance of the artificial bee colony optimization by integrating the quantum computing model into bee colony optimization, we present a quantum-inspired bee colony optimization algorithm. In our method, the bees are encoded with the qubits described on the Bloch sphere. The classical bee colony algorithm is used to compute the rotation axes and rotation angles. The Pauli matrices are used to construct the rotation matrices. The evolutionary search is achieved by rotating the qubit about the rotation axis to the target qubit on the Bloch sphere. By measuring with the Pauli matrices, the Bloch coordinates of qubit can be obtained, and the optimization solutions can be presented through the solution space transformation. The proposed method can simultaneously adjust two parameters of a qubit and automatically achieve the best match between two adjustment quantities, which may accelerate the optimization process. The experimental results show that the proposed method is obviously superior to the classical one for some benchmark functions.

Keywords:

Quantum Computing, Bee Colony Optimizing, Bloch Sphere Rotating, Algorithm Designing

1. Introduction

Artificial bee colony algorithm is proposed as an intelligent optimization algorithm which attempts to simulate bee colony to search food sources by scholars from Turkey in 2005 [1] . Compared with genetic algorithm, particle swarm optimization and other intelligent algorithm, the outstanding advantage of this algorithm is synchronously to perform the global and local search in each of iterations, which avoids the premature convergence greatly and increases the probability of obtaining the optimal solution. At present, this algorithm has already been successfully applied to numerical optimization [2] - [4] , neural network design [5] , digital filter design [6] , and network reconfiguration in distributed system [7] , construction of the minimum spanning tree [8] and many other fields. However, the progress has been slow in the algorithm improvement. For the design of the control parameters, Ding Haijun et al. present an improved artificial bee colony algorithm for the solution to TSP problem [9] . Kang Fei et al. propose a cultural annealing artificial bee colony algorithm [10] . Duan Haibin et al. present a new algorithm with application of the combination of artificial bee colony algorithm and quantum evolutionary algorithm [11] .

As a new computing model, quantum computing catches wide attention of international and domestic academics for its polymorphism, superposition and concurrency. At present, the fusion with genetic algorithm, immune optimization, paticle swarm optimization and other intelligent optimization model is successfully applied. In the real quantum system, the qubits are described on the Bloch sphere with two adjustable parameters. However, in the existing quantum intelligent optimization algorithms, individuals are encoded by qubits described by unit circle with a single adjustable parameter. Evolutionary mechanism adopts quantum rotation gates and quantum non-gates, and it essentially rotates qubits about circle center, which only changes one parameter of qubits as well. Therefore quantum properties have not been fully reflected. Although Ref. [12] presents a quantum genetic algorithm based on the Bloch coordinates of qubit, however, this algorithm does not consider the match between two adjustment quantities, which means it doesn’t go along the shortest path when the current qubit moves towards the target qubit. As a result, the optimization performance is influenced.

This paper proposes a new individual coding evolutionary mechanism, which is different from the coding of quantum genetic algorithm in Ref. [12] . In this paper, we directly use qubits described on the Bloch sphere to code (not the qubits coordinates). The evolutionary search is achieved by rotating the qubit about the rotation axis on the Bloch sphere. This method can automatically achieve the best match between two adjustment quantities of bee colony individual qubits. For the design of quantum-inspired bee colony algorithm, we elaborate design principle and implementation programs of the algorithm. Taking benchmark functions extremum optimization as example, it shows that the proposed method obviously outperforms the classical one by comparison.

2. Bee Colony Algorithm

Assuming the number of bees is, and the number of employed bees and onlooker bees are and, respectively. Individual dimension is, and individual searching space is. The employed bee colony is and its initial the n-th generation colony is and, respectively. The objective function is. Taking minimum optimization as example, the artificial bee colony algorithm can be described as follows:

(a) Randomly generating solutions, where the i-th solution is written as:

, (1)

where. Calculate the target values, and then initialize by the first solutions;

(b) For the employed bee in the current generation, the new position in its neighborhood can be obtained from the following equation:

, (2)

where, , and, and is a random number in the range (0, 1);

(c) We use greedy selection operator to select the better ones in and for the next generation. This operator is denoted as, and its probability distribution is written as:

; (3)

(d) Using the strategy of roulette, randomly select an employed bee, and search a new position in its neighborhood. This operator is written as, and its probability distribution is written as:

; (4)

(e) Let denote the minimum objective function value, and the corresponding individual be. We initialize the employed bee if its searching time Bas reach to the threshold value Limit and it does not find a better position;

(f) If algorithm meet the stopping criteria, it outputs and the corresponding individual, else go back to (b).

3. Quantum-Inspired Bee Colony Algorithm

This paper studies a new method of quantum-inspired searching with the fusion of bee algorithm. This method is named quantum-inspired bee colony algorithm (QIBC).

3.1. Description of Qubits on the Bloch Sphere

During the quantum computing, a qubit is a two-level quantum system which could be described in two-dimen- sion complex Hilbert space. Based on principle of superposition, a qubit can be defined as:

, (5)

where and.

Owing to the continuity of and, a qubit can be in infinitely many different states and described by a point on the Bloch sphere. As shown in Figure 1.

3.2. The Rotation of Qubits about the Axis

In this paper, we create a search mechanism on the Bloch sphere which is used to rotate the qubit about the rotation axis to the target qubit on the Bloch sphere. The rotation can simultaneously change two parameters of a qubit, and automatically achieve the best match between two adjustment quantities, thus we can enhance the performance of optimization. The key to the above rotation is the design of rotation axis. The design method given by this paper can be expressed as the follows [13] [14] .

Assuming and denote two points on the Bloch sphere respectively, the rotation axis about which P rotates to Q along the shortest path is the vector product of P and Q, namely,. As shown in Figure 2.

Based on the principle of quantum computing, the rotation matrix makes the qubit rotate about a rotation axis

along the unit vector with radian of rotation, and it’s defined by

, (6)

where I is the unit matrix, and, are Pauli matrices [15] .

Therefore, on the Bloch sphere, the rotation matrix that rotates the about to can be described as follows:

. (7)

The rotation operation is given by

, (8)

where t is iteration step.

3.3. QIBC Coding Method

In QIBC, the individual coding adopts qubit based on the Bloch sphere. Let denote population size, D de-

note the number of variables, and denote the t-th generation colony. During in

itialization, the i-th individual can be coded as follows:

, (9)

where.

3.4. The Projection Measurement of Qubits

On the basis of the principle of quantum computing, by applying Pauli matrices to, we can get the Bloch coordinates of. The qubits projection measurement is denoted by the following equations:

, (10)

, (11)

, (12)

where and.

In QIBC, each qubit are regarded as three paratactic genes, each one contains three paratactic gene chains, and each of gene chains represents an optimization solution. Therefore, each entity represents three optimization solutions at the same time.

3.5. The Solution Space Transformation

In QIBC, three optimization solutions given by each entity can be expressed by Bloch coordinates. Because the value of coordinate is in (−1, 1), we must map it to solutions to the problems. Assuming the j-th variable is

, the solution transformation can be expressed as the following three equations:

, (13)

, (14)

, (15)

where and.

3.6. Employed Bee Search

Taking minimum optimization as example, according to the value of target function, we rank the optimized population in descending order, and select the first entities to compose employed bee colony. The rest of them compose onlooker colony. For the i-th employed bee, first of all, randomly select employed bees

and , and also randomly select a dimension d. Then calculate the rotation axis and the rotation angle between and. Taking as target, rotate about through. Let denote the employed bee after rotation. By greedy selection operator, we select the better ones between and for the next generation from the following equations:

, (16)

where,

, (17)

. (18)

3.7. Onlooker Bee Search

It is similar with employed bee search. First, we calculate selective probability of each employed bee with the equation as follows:

. (19)

To each onlooker bee, first, we select employed bee according to the roulette method, and in its neighborhood we search for new position in the same method as the employed bee search. If is better than, set, and set the number of searches. If is less than threshold, set, otherwise, we initialize and set.

3.8. Algorithm Termination Criterion

To this algorithm, the termination criterion is the number of iterations. Whether it meets the pre-set accuracy or not, the algorithm will stop when the limited number of iterations reaches.

4. Analysis of Experimental Results

Taking functions extremum optimization as example, by comparing with bee colony [1] , Bloch quantum genetic algorithm [12] , elite genetic algorithm, quantum delta potential-based particle swarm optimization [16] , we verify the superiority of QIBC. All of algorithms use Matlab R2009a to implement on the computer (P-II 2.0 GHz) with 1.0 G memory.

4.1. Benchmark Functions

To verify the superiority of QIBC, the following ten Benchmark functions are used in this experiment. All of ten functions are for the minimum optimization, and is the minimum extreme value point.

(1), , ,;

(2), , ,;

(3), , ,;

(4), , ,;

(5), , ,;

(6), , , ,;

(7), ,

, , ;

(8), , ,;

(9), , ,;

(10), , , ,.

4.2. Parameters Setting

For convenient comparison, based on the complexity of benchmark functions, we set up precision thresholds for each function. Only when optimization effect is less than the thresholds, the algorithm is call converges. In this experiment, the precision thresholds are set as follows. for,; for ; for,; for,; for,; for,; for,. If the algorithm converges, the current optimization steps are called the number of iteration. If not, the number of iteration is equal to the pre-set limited number of iterations.

The dimensions of ten functions are set to, and population sizes of five algorithms are equal to 40. For QIBC and BC, we have, ,. For BQGA, on the basis of Ref. [12] , the initial value of rotation angle is, and the mutation probability is 10^-3. For QDPSO, based on Ref. [16] , the control parameter is. For EGA, the crossover probability is 0.8, the mutation probability is 0.01. The limited number of iterations of five algorithms is.

4.3. Comparison and Analysis of Simulation

To enhance the objectivity of comparisons, each algorithm independently runs 50 times, and we have comparisons of statistical results. The average time for each of iteration are shown in Table 1. To make comparisons be sufficient, besides showing the average results, the best and the worst ones are also are given. Comparison of the number of iterations, average iterations, and optimization results are shown in Table 2.

From Table 1, for the running time, we rank five algorithms in descending order as QIBC, BQGA, BC, EGA, QDPSO. The reason is that, in QIBC and BQGA, we use coding mechanism of qubit with three chains. During each iteration, each entity respectively do updating, solution to space transformation, calculating value of benchmark functions etc. and these operations take a long time. QIBC is longer than BQGA because QIBC needs the projection measurement, design of rotation axis and rotation matrices, and its calculating quantity is

larger.

In Table 2, for the ability of optimization, obviously, QIBC is better than QIBC, BQGA is better than EGA. QDPSO is worse than QIBC, but it’s better than BQGA, and it’s similar to BC. For the optimization performance of five algorithms, we rank them in descending order as QIBC, BC, QDPSO, BQGA, EGA.

For the above results, we present the following analysis. Firstly, we introduce the coding mechanism of qubit with three chains, and it effectively enhances the ergodicity of algorithm to solution space. Based on the geometric properties of the Bloch sphere, this mechanism can enlarge the number of global optimal solutions and the probability of attaining global optimal solutions. That is the reason why these two algorithms are better than their classical ones respectively. Secondly, QIBC has a better performance of optimization than BQGA, because they adjust qubit in the different ways.

In BQGA, qubits are updated by directly adjusting and with the same adjustment amount (namely). Obviously, in this method, it is hard to close to target qubits along the shortest path, because there must be some matching relation between and when it’s along the shortest path. But this matching relation is hard to be expressed clearly by analytic equations. In QIBC, we adjust qubit in indirect method. Namely, we rotate qubit to target qubit about the rotation axis on the Bloch sphere, and obviously, this path is

the shortest. Although it does’t adjust two parameters of qubit directly, it achieves the best match between and automatically and accurately. Hence, this method has better optimizing efficiency than classical ones.

It’s also worth pointing out that, although the QIBC has better optimizing performance, the complexity of this algorithm is obviously higher than classical ones. Comparing with classical ones, the QIBC needs some extra operations, such as calculating rotation axis, rotation angel, rotation matrices and the solution to space transformation. Considering run time and optimizing performance, QIBC earns better optimizing efficiency by sacrificing running time, which is the same as No Free Lunch. For many off-line optimizing tasks which may ignore running time, the QIBC has wide application prospects.

We need investigate and study the influence after dimensions and parameters change. Taking and as example, while, population size is, and,. Precision threshold of and is. The QIBC and the BC run 10 times respectively. Optimization results is shown in Table 3.

As the results are shown, for the high-dimensional optimization problems, the proposed algorithm also shows its better performance than classical ones.

5. Conclusion

We present a quantum-inspired bee colony optimization algorithm. In proposed method, the bees are encoded with the qubits described on the Bloch sphere. The population evolutionary is achieved by rotating the qubit about the rotation axis on the Bloch sphere. The experimental results show that, the method of qubits coding on the Bloch sphere and the method of bee updating which can achieve the best match between two adjustment quantities of qubit parameters by rotating about the rotation axis, can truly enhances the performance of the intelligent optimization algorithm.

Acknowledgements

This work was supported by the Natural Science Foundation of Heilongjiang Province, China (Grant No. F2015021), the Youth Foundation of Northeast Petroleum University (Grant No. 2013NQ119) and the Science Technology Research Project of Heilongjiang Educational Committee of China (Grant No. 12541059).

Cite this paper

GuoruiLi,MuSun,PanchiLi, (2015) Quantum-Inspired Bee Colony Algorithm. Open Journal of Optimization,04,51-60. doi: 10.4236/ojop.2015.43007

References