- 期刊
量子啟發改良式差分演化法求解數值最佳化問題
Quantum-inspired Modified Differential Evolution for Numerical Optimization Problems
摘要
差分演化（Differential Evolution, DE）為一種有效率、隨機性基於群體理論的最佳化方法，然而與大多數演化式演算法一樣，差分演化於求解過程可能會有收斂不穩定，或陷入區域最佳解的問題。因此，許多改良的差分演化方法陸續出現，其目的就是希望能找到有效的方法求解複雜問題且能加速收斂速度，其中引進量子計算就是一種新的嘗試。量子計算是描述微觀世界的現象，具有量子疊加與量子糾纏等特性，能將所有狀態以不同的機率振幅構成一個疊加態來同時呈現，而擁有大量平行處理能力，可用來求解複雜的數值最佳化問題。本研究是探討如何於差分演化中導入量子計算觀念，設計量子啟發改良式差分演化法（Quantum-inspired Modified Differential Evolution, QDE），考慮探索（exploration）與開發（exploitation）間的平衡，來有效求解數值最佳化問題。本研究共進行三項實驗。第一個實驗測試十個10維度的標準測試函數，第二個實驗測試20維度的複雜函數，第三個實驗則是測試較困難的Schwefel函數，共嘗試20, 30, 40, 50 等高維度空間。實驗的結果顯示：QDE比起DE與改良式DE獲得較佳的執行結果。
並列摘要
Differential evolution (DE) is regarded as one of the most powerful stochastic population-based optimization methods. However, it has the same problem as most of the evolutionary algorithms that regarding the instability for global convergence and easily trapping to local optima. Therefore, many modified DE emerges for the purpose of having the ability to solve complicated problems and enhancing the global convergence. One of these new approaches is to introduce quantum computing to DE. Quantum Computing (QC) is a probabilistic model to describe the phenomenon of microscopic world which has the peculiar characteristics of quantum superposition and quantum entanglement. All possible states in QC coexist at the same time in which each state has its own amplitude that creates a superposed state. Thus it has massively parallel processing power that can be used to solve complicated numerical optimization problems. The motivations of this study are to investigate the combination of QC and DE, taking the tradeoff between exploration and exploitation into consideration, and to design a quantum-inspired modified differential evolution (QDE) algorithm to solve numerical optimization problems. Three experiments were conducted in this study. The first experiment is to test 10 benchmark functions for 10-dimensional problems. The second experiment is to test a 20-dimensional complex function and conduct 30 independent runs. The last experiment is to test more difficult Schwefel function for its 20, 30, 40 and 50 dimensional problems, respectively. The experimental results show that QDE outperforms ADE (Adaptive DE) and DE in those all dimensional test problems.