著者

中山 茂 飯村 伊智郎 松尾 翠 前薗 正宜

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.8, pp.2625-2635, 2006-08-15

参考文献数

21

被引用文献数

5

---

量子コンピュータは,量子重ね合わせ状態や量子干渉効果,量子もつれ状態などの量子力学的原理を利用した計算モデルである.量子もつれ状態は,従来の古典的コンピュータでは実現しにくいものであるが,量子重ね合わせ状態や量子干渉効果は既存のアルゴリズムでも容易に取り入れることができる考え方である.この量子計算アルゴリズムなどに応用されている量子系の干渉効果を模擬した干渉交叉と呼ばれる手法を従来の遺伝的アルゴリズム(古典的GA)の遺伝的オペレータに組み込んだ量子風遺伝的アルゴリズム(量子風GA)に関する研究が,Narayanan らによって比較的都市数の少ない巡回セールスマン問題に対して行われ,古典的GA と比較してより少ない世代数で最適解の探索に成功している.そこで,本論文では,従来の研究よりもより問題規模の大きいTSPLIB の5 つの都市配置を対象として,干渉交叉の対象となる親個体の選択法や局所探索を新たに導入し詳細に実験を行い,古典的GA と量子風GA とを比較検討した.その結果,量子風GA は,最適解発見率および平均探索世代数の観点で,古典的GA に比べ優れた性能を有することが,対象とした5 つの都市配置に関して分かった.さらに,局所的な探索改善を目的とする2-Opt 法には,量子風GA の特徴である干渉交叉による探索世代数の削減効果をさらに向上させる効果があることが分かった.Quantum computer is a computation model using quantum mechanical principle such as quantum superposition state, quantum interference effect and quantum entanglement state. Quantum entanglement state is not achieved easily with conventional classical computers. However, quantum superposition state and quantum interference effect are an idea that can be easily adapted even by conventional algorithms. Quantum-inspired genetic algorithm (quantum-inspired GA) was proposed by Narayanan, et al. The quantum-inspired GA is a new GA having a technique called "interference crossover" (IX), which imitates quantum interference effect, embedded in genetic operators of a conventional GA (classical GA). The quantum-inspired GA succeeded in the search for an optimal solution in a less number of generations compared with the classical GA in the case that the number of cities of a TSP is comparatively little. In this paper, we have made comparative study of a classical GA and a quantum-inspired GA by considering selection methods of parent individuals for the IX, a local search, and experimenting in detail on five problems of TSPLIB, which are larger scale than a problem used in a previous study. As a result, we have confirmed in the five TSPs that search ability of the quantum-inspired GA is superior to the classical GA in the viewpoints of "discovery rate of the optimal solution" and "average number of generations for search". Furthermore, it should be noted that 2-Opt method improves the reduction effect of "average number of generations for search" of the quantum-inspired GA.