基于自适应机制的多宇宙并行量子衍生进化算法

Multi-universe parallel quantum-inspired evolutionary algorithm based on adaptive mechanism

进化参量的选取对量子衍生进化算法(QEA)的优化性能有极大的影响,传统QEA在选择进化参量时并未考虑种群中个体间的差异,种群中所有个体采用相同的进化参量完成更新,导致算法在解决组合优化问题中存在收敛速度慢、容易陷入局部最优解等问题。针对这一问题,采用自适应机制调整QEA的旋转角步长和量子变异概率,算法中任意一代的任一个体的进化参量均由该个体自身适应度确定,从而保证尽可能多的进化个体能够朝着最优解方向不断靠近。此外,由于自适应量子进化算法需要评估个体的适应度,导致运算时间较长,针对这一问题则采用多宇宙机制将算法分布于多个宇宙中并行实现,从而提高算法的执行效率。通过搜索多峰函数最优解和求解背包问题测试算法性能,结果表明,与传统QEA相比,所提出算法在收敛速度、搜索全局最优解及执行速度方面具有较好的表现。

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.