DOC

A New Quantum Clone Evolutionary Algorithm for Multi-objective Optimization

By James Moore,2014-08-13 16:37
10 views 0
A New Quantum Clone Evolutionary Algorithm for Multi-objective Optimization

    数量经济理论与方法?一,?计量经济学等,

    A New Quantum Clone Evolutionary Algorithm

    for Multi-objective Optimization

     Zhoufangzhao, Quzhentao, Zhouzheng

     (The Research Center of Economics, Harbin University of Commerce, Harbin 150028, P.R. China)

    Email:fangzhaozhou@yahoo.com.cn

    Abstract: Most of the quantum inspired evolution algorithms(QEA) is improved and used for the optimization of continuous functions with multi-peak now, However, they are easy to be trapped into the 1ocal deceptive peakIn this papera new improved quantum evolution algorithm is proposed to overcome the shortcoming of traditional QEA. The new improved QEA combines the main mechanisms of clone (QCEA). Every individual of each chromosome will make its own dynamic clone to build its new sub-swarm; then every new chromosome will be mutation in its low bit; at last, the QCEA will update the whole swarm by using random strategy. The algorithm not only has the global searching capacitybut also

    improves the local searching capacity of algorithm by using quantum probabilistic searchExperiments are

    implemented and compared with other QEAs. The result indicates that the new algorithm in this paper can search and get the global optimum solution in a shorter time.

Keywords: Quantum Clone Evolution Algorithm, Clone, Mutation

作者简介(

    周方召?1978—,(男!在读博士研究生!哈尔滨商业大学经济研究中心讲师。

    联系方式(fangzhaozhou@yahoo.com.cn

    曲振涛?1957—,(男!博士、教授、博士生导师!哈尔滨商业大学经济研究中心教授!

     正?1975—,(男!在读博士研究生!哈尔滨商业大学经济研究中心副教授。

    A New Quantum Clone Evolutionary Algorithm

    for Multi-objective Optimization

     Zhoufangzhao, Quzhentao, Zhouzheng

     (The Research Center of Economics, Harbin University of Commerce, Harbin 150028, P.R. China)

    Email:fangzhaozhou@yahoo.com.cn

    Abstract: Most of the quantum inspired evolution algorithms(QEA) is improved and used for the optimization of continuous functions with multi-peak now, However, they are easy to be trapped into the 1ocal deceptive peakIn this papera new improved quantum evolution algorithm is proposed to overcome

    the shortcoming of traditional QEA. The new improved QEA combines the main mechanisms of clone (QCEA). Every individual of each chromosome will make its own dynamic clone to build its new sub-swarm; then every new chromosome will be mutation in its low bit; at last, the QCEA will update the whole swarm by using random strategy. The algorithm not only has the global searching capacitybut also

    improves the local searching capacity of algorithm by using quantum probabilistic searchExperiments are

    implemented and compared with other QEAs. The result indicates that the new algorithm in this paper can search and get the global optimum solution in a shorter time.

Keywords: Quantum Clone Evolution Algorithm, Clone, Mutation

    I INTRODUCTION [1]Quantum Evolutionary Algorithm is a new probability optimization method based on quantum

    calculation theory. QEA has triumphantly applied to the optimization of continuous and low dimensionality

    [25]functions of multi-peak. However, when QEA is used to deal with the complex functions, it will

    [6]definitely become slow converging speed and prematurity. In He’s paper, he proposed an improved QEA,

    firstly he divided domain into a lot of parts, then he get the best solution in each small part. His result indicates that his algorithm will overcome the prematurity, but this algorithm inevitably increases the

    [7]complexity at the same time. In Xie’s paper, he attempts to make a new hybrid quantum evolution

    algorithm, and the result indicates that the new hybrid QEA is better than QEA in both quality of final result and the convergence rate. This algorithm has obvious advantage when it is used for the optimization of continuous and low dimensionality functions with one-peak, however, when it is not fit for the high and low

    [8]dimensionality functions with multi-peak. Li is the pioneer to import the mechanisms of clone to QEA,

    he design a new quantum inspired evolution algorithm which can be used for solving the prematurity effectively in a shorter time, however, the fact of Li’s algorithm is just combine the theory of quantum with the mechanisms of clone simply, and the result of clone is to copy each chromosome to keep the diversity of the solution space of functions, so when the chromosome is replaced with quantum gate, the probability of the diversity of the solution space of functions will be increased. This is a good change as a new QEA, but we should find two problems, firstly, the result of clone is just increase the probability to get the best individual of chromosome, it will not help to improve the algorithm’s search space; secondly, when Li begin to delete the chromosome simply in order to keep the scale of the swarm after replacing chromosome with quantum gate, it will enhance the probability of degradation of the solution space.

    In this paper, the mechanisms of clone will be imported into QEA, and apply it to the optimization of continuous and low and high dimensionality functions of multi-peak, it is testified that this new algorithm improves from two points: search capability and computing time.

    II. OVERVIEW OF QEA

    QEA relies on a basic concept which is quantum bit or qubit. A qubit can take value 0, 1 or a superposition of the two at the same time. Its state can be defined by:

     (1) 0;(1

    Where and represent the classical bit values 0 and 1 respectively; and, are complex 10(

    2numbers that specify the probability amplitudes of the corresponding states. gives the probability that

    2the qubit will be found in the 0 state and gives the probability that the qubit will be found in the 1 (

    state. Normalization of the state to unity guarantees

    22 (2) ,(;=1

    The state of a qubit can be changed by the operation with a quantum gate. Inspired by the concept of quantum computing, QEA is designed with a novel Q-bit representation, a Q-gate as a variation operator, and an observation process.

    A Q-bit individual as a string of Q-bits is defined as n

    ttt)?......12jjjmt (3) q?jttt(((......12jjjm?

    Where j1,2,...,n

    Q-bit representation has the advantage that it is able to represent a linear superposition of states, if there is for instance, a three Q-bit system with three pairs of amplitudes such as:

    111)??222? (4) 131?

    ?222

    Then the states of the system can be represented as:

1133000;001;010;0114444

    1133100;101110;1114444

    The above results means that the probabilities to represent the states:

     000, , 010, , 100, 101, 110, and 111 are: 001011

11331133 , , , , , , , , respectively. By consequence, the three Q-bit system can contains 1616161616161616

    the information of eight states.

    QEA with Q-bit representation has a better characteristic of population diversity than other representations, since it can represent linear superposition of states probabilistically. Only one Q-bit individual such as (4) is enough to represent eight states, but in binary representation at least eight strings, (000), (001), (010), (011), (100), (101), (110), and (111) are needed.

III. AN IMPROVED QUANTUM EVOLUTIONARY ALGORITHM COMBINING MECHANISM

    OF CLONE

    A. The Description of the New QCEA

    In this paper, improving quantum evolutionary algorithm is made up of three factors as follows:

    1) When the traditional artificial immune clone algorithm is in the phase of clone copy, the scale of cope is fixed. In this paper, the scale of cope is dynamic.

    tfitp()tiNroundn (5) (~)intfitp()(j1j

    twhere , and is the scale of clone of each individual in the th iterative time, and the i1,2,...,nNti

    scale of clone of the swarm is:

    tnfit(p)ti (6) N?round(n~)n(Cn1tifit(p)(j1j

    When every individual in the swarm is in the phase of clone, the number is not fixation in formula (5), which means that more excellence the father individual is, more bigger the scale of son individual is. At the same time, every sub-swarm actually can represent a larger search space, at the subsequent steps; it becomes mutation in its low bit. All of this can make sub-swarm distribute around father individual’s search space,

    which can increase the diversity of the solution space of functions and avoid trapping into local peak effectively. So the algorithm can get balance between depth search and breadth search by doing this and improve its ability to solve the function. At the same time, the scale of swarm does not change obviously in formula (6), which can make sure the efficiency of the algorithm.

     2)Before a Q-gate is employed to update a Q-bit individual in this paper, the new algorithm will make mutation in its low bit(multi-point mutation), which can represent a larger search space and increase the diversity of the solution space of functions.

    3)When this new algorithm is on its run, it will identify automatically. If the swarm’s average fitness has a little change in th iteration in contrast with the fitness which was got in th iteration, then the (t;1)t

    new algorithm will create new individual random and join them in the swarm instead of the round((*n)

    individual except the best individual. In this way, the algorithm can make trouble in the swarm in order to make sure the diversity of the search space. In this case, is an adaptive parameter, which is negatively (

    correlated with . is the scale of swarm in th iteration. (t;1)n

    B. Procedure QCEA for the Optimization of Continuous Functions with Multi-peak

    Begin

    ttt1. initialize , define a empty memory storeroom. Q(t){q,q,...,q}t012n

    2. make by observing the states of R(t)Q(t)

    '3. clone the individual which included in , then get a new swarm R(t)R(t)

    4. each sub-swarm mutation in their low bit.

    '5. evaluate , store the best solutions in memory storeroom. R(t)

    6. while the termination is false

    (1)update the swarm by Q-gate to get the new swarm

    (2)if has a little change, update the swarm random.

    (3), go to (2). tt;1

     end

    End

    [8]When QEA is In the step of mutation, there are often three mutation methods.

    1)traditional mutation;

    2)build the values of the updated Q-bit (, ) random; (

    3)use the appropriate Q-gate, by which operation the Q-bit should be updated.

    In this paper, QCEA use the third method. The following rotation gate is used as a Q-gate in QCEA,

    such

    cos()sin())? (7) ()U?sin()cos()

    Where is a rotation angle of each Q-bit toward either 0 or 1 state depending on its sign.

    [9]In the formula (7), Q-gate has a parameter, which can get as follows:.

    Table 1. the rotation ’s modulation strategy

     (s,()ii

     xbestf(x)f(best)iii

     (0(00(0iiiiii

    0 0 false 0 0 0 0 0

    0 0 true 0 0 0 0 0

    0 1 false 0.05π +1 -1 0 ?1

    0 1 true 0.05π -1 +1 ?1 0

    1 0 false 0.025π -1 +1 ?1 0

    1 0 true 0.01π +1 -1 0 ?1

    1 1 false 0 0 0 0 0

    1 1 true 0 0 0 0 0

    Look up table1, where , is the th bit of current individual, is the best s(,()~xbestiiiiiii

    individual’s th bit in current swarm, is fitness function. is the quantum rotation angle’s value, f(?)ii

    which can control the convergence scope of the algorithm. is the rotation angle’s direction, s(,()ii

    which can control the convergence speed of the algorithm.

    Quantum rotation angle is very important for the algorithm. Different rotation angle will induce

    different results. If the angle is too small, which will decrease the speed of the algorithm, contrarily, which

    will conduce prematurity. So we define the angle is in [0.005,0.050].

    V. EXPERIMENTAL RESULTS

    It is very important for the optimization of continuous functions with multi-peak. The algorithm should

make sure that it can detect the global optimal value and use the less time. There are two typical functions as

    test functions in order to depict He’s QEA, Li’s QEA and the QCEA which is proposed in this paper, and to witness that QCEA would be better than Xie’s, He’s and Li’s QEA.

    A. Low Dimensional Function

    Think about this function as follows:

     F(x)xsin(4x);ysin(20y)2

    , x?[5,12.1]y?[4,5.8]

    Whereand, , and every swarm contains 100 individuals, and y5.7250F17.3503x11.6255best

    each individual is encoding by 10 bits.

    B. High Dimensional Function

    nn12, , F(x)xcos(xi);1x?[500,500]i1,2,...,302(ii?i4000i1i1

    Where,, and every swarm contains 50 individuals, and each individual is encoding by 20 bits. F0best

    Table2 results of the low dimensional function

    Algorithm Average iteration Average global

    times optimal value

    He’s 41 16.96557

    Li’s 35 17.22341

    QCEA 20 17.32041

    Table3 results of the high dimensional function

    Algorithm Average iteration Average global

    times optimal value

    Xie’s 1210 0.006200

    Li’s 1800 0.000546

    QCEA 930 0.000013

    VI. CONCLUSIONS

    This paper proposed a new QCEA. Every individual of each chromosome in this QCEA will make its own dynamic clone to build its new sub-swarm; then every new chromosome will be mutation in its low bit;

    at last, the improved QEA will update the whole swarm by using random strategy. According to the experimental results, the QCEA overcomes the shortcoming of the traditional QEA, and can deal with the

    continuous functions with multi-peak either low dimension or high dimension successfully in a shorter time.

    REFERENCES

    [1]. Han Kuk Hyun, Kim Jong Hwan, Quantum Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization. IEEE Transactions on Evolutionary Computation, 2002, 6(6):580~593

    [2]. Wang LWu HTang F. Hybrid quantum genetic algorithms and performance analysis [J]Control and Decision, 2005, 20 (2):156~160. [3]. Yang J A , Li B, Zhuang Z Q. Research of quantum genetic algorithms and its application in blind source separation[J]. Journal of Electronics, 2003, 20 (1): 62~68. [4]. Yang S Y, Liu F, Jiao L C. A novel genetic algorithm based on the quantum chromosome[J]. Journal of Xidian University, 2004, 31 (1) : 76~81. [5]. Y.J.LV, N.X.LIU, Application of Quantum Genetic Algorithm on Finding Minimal Reduct, IEEE International Conference on Granular Computing, 2007, 728~733

    [6] He M W, Li G H, Ruan B Y, Application of modified quantum genetic algorithm in optimization of multi-peak functions[J]Computer Engineering and

    Applications200844(7)(41~43

    [7] Xie P, Li B, Zhuang Z Q, A New Hybrid Quantum Evolutionary Algorithm[J]Computer Science200835(2)(166~170

    [8]. Li Y Y, Jiao L CQuantum Clonal Genetic Algorithms[J]Computer Science200734(11)(147~149

[9]. Du H F, Jiao L C. Clonal Operator Antibody Clone Algorithms[A]. In: Proceedings of 2002 International Conference on Machine Learning and Cybernetics. New York:IEEE,2002, 1:506~510

Report this document

For any questions or suggestions please email
cust-service@docsford.com