Study on EvolutionaryAlgorithm with Quantum Bits

量子计算机是利用叠加态、干涉效应、纠缠态等量子力学原理的计算模型。近年来，利用量子力学原理或量子比特，提出了与进化算法相结合的随机组合搜索算法。Narayanan等人在旅行商问题（TSP）中提出了经典遗传算法（CGA）的干扰交叉（IX），并表明在涉及9个城市的CGA问题中，IX可以将搜索成本降低到2/3。我们还表明，在涉及50多个城市的TSP问题中，IX和免疫算法（IA）的组合表现出比经典IA更好的搜索性能。Han等人提出了量子启发的进化算法（QEA），其中每个基因由一个量子比特表示。QEA可以进行单点搜索，并像模拟退火（SA）一样自动从全局搜索转移到局部搜索。QEA还可以像CGA一样执行更多的多点搜索，以解决大规模的优化问题。在QEA中，有一个以上的亚种群（群体），如岛屿GA (IGA)，并执行群体间和群体内的迁移过程。每组的演化实现了粗粒度并行化，防止了过早收敛，迁移过程控制了搜索的多样化和集约化。然而，对于每个问题的组数和迁移间隔，需要调整许多参数。事实上，Han等人为了得到KP参数调整的指导，不得不做大量的实验。在这项研究中，我们提出了一个更简单的算法，称为量子启发的进化算法与配对交换策略（QEAPS）。QEAPS只涉及一个种群和一个简单的遗传操作，该操作在随机选择的两个个体之间交换每个最佳解决方案的信息。因此，与QEA相比，QEAPS需要调整的参数更少。对QEAPS算法在0-1背包问题（KP）上的搜索性能进行了评价，结果表明，QEAPS算法比QEA算法更有效、更稳定地找到相似的甚至高质量的解。少

Quantum computer is a computation model using quantum mechanical principles such as superposition state, interference effect, and entanglement state. Recently, stochastic combinatorial search algorithms combined with evolutionary algorithm have been recently proposed by incorporating quantum mechanical principles or quantum bits. Narayanan, et. al. have proposed Interference Crossover (IX) for Classical Genetic Algorithm (CGA) in Traveling Salesman Problem (TSP), and have shown that IX can reduce search cost to 2/3 in CGA with a problem involving 9 cities. We have also shown that the combination of IX and Immune Algorithm (IA) shows better search performance than classical IA in TSP problems involving more than 50 cities.Han, et. al. have proposed Quantum-inspired Evolutionary Algorithm (QEA) in which each gene is represented by a quantum bit. QEA can do single-point search and automatically shift from global search to local search like Simulated Annealing (SA). QEA can also perform mu … More lti-point search like CGA in order to solve large-scale optimization problems. In QEA, there are more than one subpopulations (groups) like Island GA (IGA), and inter- and intra-group migration procedures are performed. Evolution in each group enables coarse-grained parallelization and prevents premature convergence, and the migration procedures can control search diversification and intensification. However, the adjustment of a number of parameters is required for the number of group and migration intervals for each problem. In fact, Han, et. al. had to do vast experiments in order to get guidelines for the parameter adjustment in KP.In this research, we propose a simpler algorithm which is referred to as Quantum-inspired Evolutionary Algorithm with Pair-Swap strategy (QEAPS). QEAPS involves just one population and a simple genetic operation which exchanges each best solution information between two individuals chosen randomly. Therefore, QEAPS involves less parameters necessary to be adjusted than QEA. We evaluate the search performance of QEAPS on 0-1 Knapsack Problem (KP), and show that QEAPS can find similar or even highly qualified solutions more efficiently and stably than QEA. Less