量子免疫算法的改进及其在组合优化中的应用 第2页
Figure 1 Framework of Quantum Immune Algorithm Running
(1) Obtain Vaccines:
The application of quantum immune algorithm is mainly on NP problem which is generally easier to be solved when it is small-scale and to find the solution under certain conditions. Therefore, there are two ways to obtain vaccines, one is to construct a vaccine according to the characteristics of the problem; and the other is to select a vaccine by simplifying the problem, which can be achieved by reducing the scale of the original problem based on analysis of the problem and setting up certain conditions.
Also, because each vaccine explores a global optimal solution through certain partial information, there is no need to make each vaccine precise. Therefore, according to the characteristics of the problem, vaccine extraction can be realized through iterative and optimizing algorithm on the original problem [6] [7].
As in the process of quantum genetic algorithm, each iteration will produce a partial optimal solution, in order to take full advantage of the current optimal solution, this paper introduces a new vaccine production method. It is to form a combined vaccine by combining about the characteristics of the current optimal solution and the priori knowledge of the problem. As the individual of the optimal solution carrying the gene which is more suitable for the problem, the vaccine obtained in this way may be more suitable for global optimization algorithm.
(2) Immune Selection:
Immune selection is the selection of scope and concentration of the vaccine.
Because the vaccine may be obtained from the priori knowledge of the problem, or from a partial optimal solution, it is necessary to choose the scope and concentration of vaccine.
Immune selection can be expressed with the following formula:
(2.1)
The Formula shows that in all individuals (n) of a generation, randomly select individuals according to the proportion , stands for the concentration of antibodies.
(3) Vaccination
Vaccination is to inject the vaccines selected into individual genes. Suppose the selected vaccine expressed as , quantum population , then vaccination can be expressed as follows:
(2.2)
In it, stands for impact factor of vaccines on the population.
3 Combinatorial Optimization Problem
0-1 knapsack problem is a classical combinatorial optimization problem, described as follows: We have number n items, weight of item is , the price is . We assume that all the weight and price are non-negative. Knapsack can bear maximum weight. If the limit for each item can only be 0 or 1, the problem is called the 0-1 knapsack problem. Formula can be expressed as:
maximize （3.1）
subject to （3.2）
For this problem we often use greedy algorithm. Greedy algorithm uses a range of choices for the problem solution; in each of the choices the best one in view of the current state is always made, i.e. achieving global optimum through the partial optimum. This heuristic may not always obtain the global optimal solution, but the problem mostly comes to the optimum solution available.
In the 0-1 knapsack problem we generally choose the following greedy algorithm [8]: the rate of value on density is maximum value. Selection criteria: Select one which has the greatest from the remaining items and put into the knapsack, which is intuitively the best choice. But the 0-1 knapsack problem may not access to the global optimal solution, and sometimes is far from optimal solution.
4 Quantum immune algorithm applied to combinatorial optimization problems
4.1 The quantum bit encoding scheme
on 0-1 knapsack problem, the length will be set as , which can be the total number of items added in the knapsack, i.e. each chromosome has quantum genes. After the collapse of quantum, each chromosome shall represent a encasing program of the knapsack problem. Take item into a knapsack as 1, and take 0 is on the contrary, as shown below:
Figure 2 Coding Scheme 0-1 Knapsack Problem