量子免疫算法的改进及其在组合优化中的应用 第3页
4.2 Evaluation of fitness function
According to encased program ensured by each chromosome, the total value of theknapsack calculated can be taken as the evaluation criteria of the fitness function of this chromosome. The higher the total value, the greater the fitness function will be. If the total weight of the knapsack exceeds the weight withstood, the fitness function will be set to minimum value.
4.3 Obtain the vaccine
Through analyzing the 0-1 knapsack problem, the optimal allocation scheme must have the following characteristics: items which have larger value and lighter weight, i.e. items with larger value of density will appear in the knapsack. Items with weight heavier than the weight endured by the knapsack will not appear in the knapsack. Vaccines can be prepared according to the above two priori information. For items with the first feature, gene vaccination would be at location 1. For items with the second feature, gene vaccination would be at location 0.
For partial optimal solution in the iterative process, directly use its gene as a vaccine.
4.4 Immune Selection and Vaccination
Methods introduced in the above section are adopted for Immune selection and vaccination, and impacting factor while vaccination would be produced using the following formula:
（4.1）
5 Algorithm Simulation and Discussion
5.1 Parameters used while Simulation
Use the following data on the simulation algorithm:
Number of items in the first group: n = 30; Maximum Weight: Y = 150.
Number of items in the second group: n = 40, Maximum Weight: Y = 200.
For these data, greedy algorithm, quantum genetic algorithm and quantum immune algorithm were used to obtain the optimal value solution simulation.
Quantum genetic algorithm: the initial population size is 40, times of evolution of algebra are 500, adopting quantum overall interference crossover, quantum mutation probability is 0.15.
Quantum immune algorithm: the initial size is 40, times of evolution of algebra are 500, also adopting quantum overall interference crossover, quantum mutation probability is 0.15; the concentration of the vaccine is set as 0.4.
5.2 Simulation results
For each data group, using greedy algorithm, genetic algorithm, quantum immune algorithm to run 50 times independently, the statistical results are in the following table:
Table 1 Simulation results of three algorithms
data Algorithm The best value Average time Average convergence algebra
First Group Greedy algorithm 351 0.005316 None
QGA 369 0.643356 240.8
QIA 369 0.649120 152.4
Second Group Greedy algorithm 763 0.005513 None
QGA 816 0.653031 260.6
QIA 816 0.674332 192.2
Figure 3 simulation results of the first knapsack data group
Figure 4 simulation results of the second knapsack data group