Study on EvolutionaryAlgorithm with Quantum Bits

量子计算机是一种利用叠加态、干涉效应和纠缠态等量子力学原理的计算模型。最近，结合量子力学原理或量子比特的随机组合搜索算法和进化算法被提出。纳拉亚南等人艾尔针对旅行商问题(TSP)，提出了经典遗传算法(CGA)的干扰交叉(IX)算法，并将其应用于9个城市的旅行商问题中，将搜索代价降低到CGA的2/3。我们还表明，在涉及50多个城市的TSP问题上，IX和免疫算法(IA)的结合显示了比经典IA更好的搜索性能。艾尔提出了量子启发进化算法(QEA)，其中每个基因由一个量子比特表示。QEA可以进行单点搜索，并能像模拟退火法(SA)一样从全局搜索自动转换到局部搜索。QEA还可以执行MU…更多像CGA一样的LTI点搜索，以解决大规模优化问题。在QEA中，有多个子种群(组)，如孤岛遗传算法(IGA)，并执行组内和组内迁移程序。每个群体中的进化实现了粗粒度并行，防止了过早收敛，而迁移过程可以控制搜索的多样化和集约化。然而，对于每个问题的组数和迁移间隔，需要调整多个参数。事实上，韩等人。艾尔为了得到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