微分演化是一種新的演化計算技術，被視為是有效率、隨機性基於群體理論的最佳化方法。微分演化將每一個個體視為一個向量，每個變數向量根據微分突變向量在偌大空間做搜尋，來找到更好的適應值，以避免陷入區域最佳解。微分演化雖然有結構簡單、容易使用、以及快速收斂之特性，然而與大多數傳統演算法一樣，微分演化於求解過程仍可能會有收斂不穩定，或陷入區域最佳解等問題。因此，許多改良的微分演化方法陸續出現，其目的就是希望能求解更複雜的問題與加速收斂速度，其中引進量子計算就是一種新的嘗試。量子計算屬於量子力學的機率模式。量子力學是描述微觀世界的現象，具有量子疊加與量子糾纏特性，所有狀態以不同的機率振幅構成一個疊加態而同時呈現。其計算過程是透過量子邏輯閘，每一個邏輯閘對映數學的一個么正矩陣，是可逆的計算程序。所以，量子計算就是一系列么正矩陣的變換，具有大量的平行處理能力，能用來求解複雜的組合最佳化問題。本計畫的研究動機就是想探索微分演化過程應如何導入量子計算，以及如何設計量子微分演化法來求解不同類型的組合最佳化問題。因此，本研究的目的是：(1) 想探討如何適當且正確的在微分演化過程中導入量子計算觀念，瞭解量子計算對於組合最佳化問題的 strongly corrected、weakly correlated 以及 uncorrected 三種不同資料分佈時的執行效能。(2) 研究微分演化與量子計算的結合情況，探討量子計算對於微分演化的影響程度。(3) 由於量子計算有大量平行處理能力，我們想設計多個具量子計算能力的改良式微分演化法來求解不同類型的組合最佳化問題。我們提出兩年期的研究計畫。第一年，將研究如何於微分演化導入量子計算，設計多個具量子計算能力的微分演化演算法。第二年，將所設計的量子微分演化法應用於求解包括實數及二元不同類型的數個組合最佳化問題。
Differential evolution (DE) is a novel evolutionary computation technique, which is regarded as one of the most powerful stochastic population-based optimization methods. Each individual in the population is a vector to DE. DE perturbs vectors with scaled difference of two randomly selected population vectors and adds the scaled, random vector difference to a third randomly selected population vector to avoid trapping in the local optima. The characteristics of DE are its simplicity, easy to use and fast convergence. However, it has the same problems of the instability for global convergence and easily trapping to local optima as most of the evolutionary algorithms have. Therefore, many modified DE emerges for the purpose of having the ability to solve more complicated problems and enhancing the global convergence. Quantum Computing (QC) is a probabilistic model of quantum mechanics. Quantum mechanics describes the phenomenon of microscopic world that has the peculiar characteristics of quantum superposition and quantum entanglement. All possible states coexist at the same time in which each state has its own amplitude that creates a superposed state. The operations of QC are using quantum logical gates. Each quantum logic gate correspond a unitary matrix in mathematics and it is a reversible computation. Therefore the quantum computation is a series of unitary matrix transformations. It has massively parallel processing power that can be used to solve complicated combinatorial optimization problems. The motivations of this research are to explore the combination of QC and DE and to design quantum differential evolution algorithms to solve various types of optimization problems. Thus, the objectives of this proposal are listed in the following. First, we want to investigate how to correctly and appropriately introduce QC into DE, and also to understand the performance of QC for dealing strongly corrected, weakly corrected and uncorrected data distributions in optimization problems. Second, we want to study the interaction while combining QC and DE and the influence of DE for the combination. Third, since QC has massively parallelism, we want to design quantum differential evolution (QDE) algorithms for solving various types of optimization problems. Consequently, we submit a two-year research grant proposal. In the first year, we investigate how to introduce QC into DE and design several QDE algorithms. In the second year, we apply those QDE algorithms to solve both real number and binary number types of optimization problems.
