量子免疫算法的改进及其在组合优化中的应用/
Abstract: This paper introduces a new improved algorithm: the quantum immune algorithm, which combines the immune algorithm with the quantum genetic algorithm. It gets a shorter global convergence time. And it performs well while applying to the Combinatorial Optimization.
Key words: quantum immune algorithm; quantum genetic algorithm; Combinatorial Optimization; greed algorithm
1 Introduction
Quantum Genetic Algorithm, which is the product of the combination of quantum computation theory and genetic algorithm, has better quality on population diversity and convergence. However, information on the problem often cannot be reflected in the process of iterative algorithm. Quantum Immune Algorithm (QIA), which is posed based on introducing vaccination idea of artificial immune to quantum genetic algorithm, can better solve the above problem. Knapsack problem is a classic one of combinatorial optimization [1]. The name comes from the idea of choosing and putting the most appropriate items into the given knapsack. Knapsack problem has broad application background, such as budget controlling, program selecting, material cutting, cargo loading and so on [2]. Generally, greedy algorithm or dynamic programming algorithm can be adopted, while the former has no way to overall Qto solve this problem by using quantum immune algorithm.
2 Quantum Immune Algorithm
2.1 Quantum Genetic Algorithm
Quantum Genetic Algorithm is a kind of randomly optimizing way to optimize problem solution. It develops from simulating Darwinian evolution theory and Mendelian genetics theory. Only by using target function guiding under the probability principle to do complete and self-adaptable search, can this algorithm deal with difficult and complex problems which many traditional optimizing method cannot solve. Therefore, it is widespread within a lot of optimization areas and becomes a hot topic for interdisciplinary research.
Quantum Genetic Algorithm (QGA) is the product of the combination of quantum computation theory and genetic algorithm principle. It is based on quantum computation theory, and applies the probability range display of quantum bit to the coding of chromosomes, of which one may express the adding of multi-states. In the process of arithmetic, performing quantum intercross can make full use of information of all chromosomes to produce more new units. Quantum mutation can prevent premature convergence and improve arithmetic global search capability, achieved by using quantum rotation gate operation to realize updating of population chromosomes. This arithmetic is better than GA in population diversity and convergence, so QGA has the following characteristics: small-scale population, better optimization searching ability, rapid convergence and short time computation [3] [4].
In quantum information theory, the information carrier is no longer a classical bit but a quantum bit, which may be at any superposition state at two current state 0,1, the state can be expressed as , where demonstrate the probability of corresponding state respectively, demonstrate the probability of quantum bit at the state of 0 and 1 respectively, and satisfy . The algorithm flow is as follows [5]:
（1）Initialized population ；
（2）Acquiring a group of decided state by measuring population ;
（3）Conducting on the individual fitness evaluation within ;
（4）Recording the best individual fitness value and the corresponding target as the next updated reference population;
（5）While not meeting the stop condition do
①Measure the population, achieve the state and conduct fitness assessment of the function;
②Record the current best fitness value and individuals, compared with the previous parameters recorded, take those best one as the target of the next updating population;
③ Make population crossover and mutation in accordance with certain strategies, and make use of quantum rotation gate to update population, then acquire descendant ;
End;
2.2 Quantum Immune Algorithm
Genetic algorithm and quantum genetic algorithm take superiority and inferiority of the fitness function as the sole criterion of population evolution, but the other priori knowledge of the problem cannot be used. And the best individual of which information on each gene may not be fully used is only regarded as the target of population evolution. Therefore, quantum immune algorithm is proposed through introducing immune operator of the immune algorithm into quantum genetic algorithm, thus can take advantage of prior knowledge of the problem and the best individual generated by iteration to speed up the convergence and improve capacity for searching for optimal solutions.
Algorithm operating framework as shown below: 1122