关键词: 组合优化, 量子衍生进化算法, 最优解, 多宇宙, 并行计算

Abstract:

The way of selecting evolutionary parameters is vital for the optimal performance of the Quantum-inspired Evolutionary Algorithm (QEA). However, in conventional QEA, all individuals employ the same evolutionary parameters to complete update without considering the individual difference of the population, thus the drawbacks including slow convergence speed and being easy to fall into local optimal solution are exposed in computing combination optimization problem. To address those problems, an adaptive evolutionary mechanism was employed to adjust the rotation angle step and the quantum mutation probability in the quantum evolutionary algorithm. In the algorithm, the evolutionary parameters in each individual and each evolution generation were determined by the individual fitness to ensure that as many evolutionary individuals as possible could evolve to the optimal solution direction. In addition, the adaptive-evolution-based evolutionary algorithm needs to evaluate the fitness of each individual, which leads to a longer operation time. To solve this problem, the proposed adaptive quantum-inspired evolutionary algorithm was parallel implemented in different universe to improve the execution efficiency. The proposed algorithms were tested by searching the optimal solutions of three multimodal functions and solving knapsack problem. The experimental results show that, compared with conventional QEA, the proposed algorithms can achieve better performances in convergence speed and searching the global optimal solution.

Key words: combination optimization, Quantum-inspired Evolutionary Algorithm (QEA), optimal solution, multi-univere, parallel computing