Study on EvolutionaryAlgorithm with Quantum Bits

量子计算机是利用叠加态、干涉效应、纠缠态等量子力学原理的计算模型。近年来，结合量子力学原理或量子比特的随机组合搜索算法与进化算法相结合。Narayanan，et.等人在经典遗传算法（CGA）求解旅行商问题（TSP）时提出了干扰交叉（IX）算法，并证明了IX算法在求解9个城市的TSP问题时能使CGA的搜索代价降低到原来的2/3。我们还表明，IX和免疫算法（IA）的组合显示出更好的搜索性能比经典的IA在TSP问题，涉及50多个城市。等人提出了量子启发进化算法（QEA），其中每个基因由量子比特表示。QEA可以进行单点搜索，并像模拟退火（SA）一样自动从全局搜索转向局部搜索。QEA还可以执行mu ...更多信息 像CGA这样的多点搜索，以解决大规模优化问题。在QEA中，有一个以上的亚群（组），如岛GA（伊加），并执行组间和组内迁移程序。每个组中的进化实现粗粒度并行化并防止过早收敛，并且迁移过程可以控制搜索多样化和强化。然而，对于每个问题的组数和迁移间隔数，需要调整多个参数。事实上，Han et.在本研究中，我们提出了一种简单的量子进化算法，称为量子进化算法与配对交换策略（QEAPS）。QEAPS只涉及一个种群和一个简单的遗传操作，该操作在随机选择的两个个体之间交换每个最佳解的信息。因此，QEAPS比QEA需要调整的参数更少。我们评估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