Study on EvolutionaryAlgorithm with Quantum Bits

量子比特进化算法研究

• 批准号: 18500176
• 负责人: NAKAYAMA Shigeru
• 金额: $ 2.63万
• 依托单位: Kagoshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18500176/
• 关键词: Quantum-inspired Algorithm; Evolutionary Algorithm; Quantum Information Engineering; Combinatorial Optimization Pproblem; Pair-swap Strategy; Mixture Interference Crossover; Interference Crossover; Helical Crossover

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

量子计算机是利用叠加态、干涉效应、纠缠态等量子力学原理的计算模型。近年来，利用量子力学原理或量子比特，提出了与进化算法相结合的随机组合搜索算法。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算法更有效、更稳定地找到相似的甚至高质量的解。少

项目成果

免疫アルゴリズムにおける混合干渉交叉法の提案

免疫算法中混合干扰交叉方法的提出

• 发表时间: 2006
• 期刊: 電子情報通信学会論文誌D(2006年6月) 第J89-D巻 第6号
• 作者: 中山 茂;伊藤登志也;飯村 伊智郎;小野 智司
• 通讯作者: 小野 智司

Helical Crossover Method in Immune Algorithm: A Case for Job-Shop Scheduling Problem

免疫算法中的螺旋交叉法：作业车间调度问题的一个案例

• 发表时间: 2007
• 作者: Shigeru Nakayama;Takaaki Imabeppu;Satoshi Ono;Shigeru Nakayama;Shigeru Nakayama
• 通讯作者: Shigeru Nakayama

Study on Improvement of Memory Cell Control in Hybridization of Immune Algorithm and Gradient Search for Multiple Solution Search

多解搜索的免疫算法与梯度搜索杂交中记忆细胞控制的改进研究

• 发表时间: 2007
• 期刊: Institute of Electrical Engineers of Japan Vol.127 No.12
• 作者: Yusuke;Hirotani;Satoshi;Ono;Shigeru;Nakayama
• 通讯作者: Nakayama

Pair Swap Strategy in Quantum-Inspired Evolutinary Algorithm

量子进化算法中的配对交换策略

• 发表时间: 2006
• 期刊: Genetic and Evolutinary Computation Conference Seattle,Washington,USA GECCO-2006(CD-ROM)
• 作者: Shigeru Nakayama;Takaaki Imabeppu;Satoshi Ono
• 通讯作者: Satoshi Ono

複数解探索を目的とした免疫アルゴリズムと勾配法のハイブリッドにおける記憶細胞制御の改良

多解搜索免疫算法和梯度法混合的记忆细胞控制的改进

• 发表时间: 2007
• 期刊: 電気学会論文誌C 127
• 作者: 廣谷 裕介;小野 智司;中山 茂
• 通讯作者: 中山 茂