具糾纏態之量子啟發式演算法解決最佳化問題

Entanglement Enhanced Quantum-inspired Search Algorithm for Solving Optimization Problem

郭姝妤(Shu-Yu Kuo)

指導教授 ： 周耀新

國立暨南國際大學/科技學院/資訊工程學系/博士(2018年)

摘要

解決最佳化問題在許多領域是很重要的議題。許多啟發式演算法被提出來解決這些組合最佳化問題以及數值最佳化問題。而大多數的最佳化問題是具有相依性的特性，表示變數的值皆會相互影響。如果演算法只是考慮各個擊破，獨立解決問題是很難找到眾多參數中的最佳組合。當傳統的方法應用在高度相依性問題，會容易陷落在區域最佳解無法找到最佳解。而為了解決上述問題，我們發明一個創新的演算法「具糾纏態之量子啟發式禁忌搜尋演算法」，此演算法主要是基於量子糾纏態特性的啟發並結合量子啟發式禁忌搜尋演算法，同時考慮多個維度和變數，讓演算法在解決最佳化問題時能考慮到其變數的相依性。具糾纏態之量子啟發式禁忌搜尋演算法不同於其他量子啟發式演算法，其量子態是可以具有糾纏態特性，能夠考慮各個維度變數的關係，此方法是很新穎的想法。具糾纏態之量子啟發式禁忌搜尋演算法不僅能夠平衡廣及深的搜尋力道、利用量子反閘跳脫區域最佳解、利用糾纏態解決高維度及高相依性的問題，利用糾纏區域搜尋加強深度搜尋的能力以及其搜索速度。本研究將此演算法應用在方程式最佳化問題上。實驗證明，在方程式最佳化問題此方法比其他啟發式演算法在解的品質以及時間效率上有更好的效能，並能解決傳統解不好的相依性問題，並達到高水準品質。除此之外，也應用此演算法在無線感測網路中的擺放問題。無線感測網路可以在應用於交通控制和安全監控等領域，而拓樸的擺放在其中是一重要且基本的問題，實驗證明本研究相比於傳統的方法能使用較少數量的感測器來滿足監控要求和拓撲連接。

關鍵字

萬用啟發式演算法 ； 最佳化問題 ； 方程式最佳化問題 ； 擺放問題 ； 相依性問題 ； 量子糾纏 ； 量子啟發式搜尋演算法

並列摘要

Solving optimization problem is an important issue in many areas. Many metaheuristic algorithms have been proposed to solve combinatorial and numerical optimization problems. Most optimization problems have dependency feature, meaning that variables are strongly dependent on one another. If a method were to attempt to optimize each variable independently, its performance would suffer significantly. When traditional optimization techniques are applied to high-dependency problems, they experience difficulty in finding the global optimum. To address this problem, this study proposes a novel metaheuristic algorithm, the entanglement-enhanced quantum-inspired tabu search algorithm (Entanglement-QTS), which is based on the quantum-inspired tabu search (QTS) algorithm and the feature of quantum entanglement. Entanglement-QTS differs from other quantum-inspired evolutionary algorithms in that its Q-bits have entangled states, which can express a high degree of correlation, rendering the variables more intertwined. Entangled Q-bits represent a state-of-the-art idea that can significantly improve the treatment of multimodal and high-dependency problems. Entanglement-QTS can discover optimal solutions, balance diversification and intensification, escape numerous local optimal solutions by using the quantum NOT gate, reinforce the intensification effect by local search and entanglement local search, and manage strong-dependency problems and accelerate the optimization process by using entangled states.
This study uses nine benchmark functions to test the search ability of the Entanglement-QTS algorithm. The results demonstrate that Entanglement-QTS outperforms QTS and other metaheuristic algorithms in both its effectiveness at finding the global optimum and its computational efficiency. In addition, with recent advances in camera and visual computing technology, visual surveillance is playing a significant role in wireless sensor networks (WSNs) and cyber-physical systems (CPSs). It can be used in civilian areas for traffic control and security monitoring. Deployment is an important and fundamental issue in a WSN/CPS. Many issues, such as the quality of service, energy efficiency, and lifetime, are based on the placement of sensors. Different heuristic and deterministic methods have been proposed to achieve optimal deployment. In this study, Entanglement-QTS is applied to a deployment problem to determine the minimum number of sensors required and their locations. The experiment results showed that Entanglement-QTS outperformed other deployment approaches and used the least number of sensors to satisfy the monitoring requirement and topology connectivity. With Entanglement-QTS, the performance of surveillance system deployment has improved further.

並列關鍵字

Metabolic algorithm ； Optimization problem ； Function optimization problem ； Deployment problem ； Dependency problem ； Quantum entanglement ； Quantum-inspired tabu search algorithm

參考文獻

[1] J. H. Holland, “Genetic algorithms” Scientific american, vol. 267, no. 1, pp. 66-72, 1992.

[2] J. Kennedy and R. Eberhart, “Particle swarm optimization,” IEEE International Conference on Neural Networks, pp. 1942–1948, 1995.

[3] K.-H. Han and J.-H. Kim, “Quantum-inspired evolutionary algorithm for a class of combinatorial optimization,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, pp. 580-593, 2002.

[4] G. X. Zhang, “Quantum-inspired evolutionary algorithms: a survey and empirical study,” Journal of Heuristics, vol. 17, no. 3, pp. 303-351, 2011.

[5] A. Glassner, “Quantum computing. 1,” IEEE Computer Graphics and Applications, vol. 21, no. 4, pp. 84-92, 2001.