| 摘要: | 微分演化 (Differential Evolution, DE) 目前被視是一種極有效率隨機性基於群體理論的最佳化方法。微分演化與進化演算法以及人工生命有密切的關聯，是基因演算法的一種變型，事實上它是一種新的演化計算技術。最初，微分演化是用來求解切比雪夫多項式問題 (Chebyshev Polynomials)，它能夠找到 33 維度切比雪夫多項式的係數。後來發現微分演化也可以求解連續空間的複雜最佳化問題，對於多維度函數或多重模態函數有極大的機率找到全體最佳解。由於可獲得不錯的成效，微分演化被廣泛地運用在機械工具設計、資料探勘、決策支援等問題上。微分演化將每一個個體視為一個向量，每個變數向量根據微分向量在偌大空間做搜尋，經由微分向量來找到更好的適應值，得到新解以避免陷入區域最佳解。微分演化雖然擁有結構簡單、容易使用、以及快速收斂之特性，然而與大多數傳統演算法一樣，微分演化於求解過程仍可能會有收斂不穩定，或陷入區域最佳解等問題。因此，許多學者針對此一缺點進行改良，包括探討微分向量的數量、改良演化機制、以及調整參數等研究。去年我們曾應用微分演化求解模糊運輸問題，並與先前使用的基因演算法做比較，發覺微分演化確實有快速收斂之特性，對於某些情況它的表現優於基因演算法，此結果已發表在期刊上。於本計畫我們想研究應用微分演化求解限制性最佳化問題的成效，並拿來與基因演算法比較，再去探討參數調整方式對於限制性最佳化問題效能的影響程度，最後將提出求解限制性最佳化問題的高效能微分演化法。
Differential evolution (DE) is regarded as one of the most powerful stochastic population-based optimization methods. DE is closely relevant to Evolutionary Algorithms and Artificial Life, and is a variant of Genetic Algorithms (GAs). It is, in fact, to be a novel evolutionary computational technique. DE was initially invented to solve Chebyshev polynomials. It has no difficulty to find the coefficients of the 33-dimensional Chebyshev polynomial. Later, DE was found can be applied to solve complex global optimization over continuous spaces. DE finds the global minimum of a multidimensional or multimodal function with good probability. Due to its effectiveness, DE was widely applied to mechanical units design, data mining, and decision support problems. Each individual of 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 advantages 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. Therefore, many researchers try to improve the deficiencies by studying the number of differential vectors, evolution mechanism, and parameters adjustment. Last year, we applied DE to solve the fuzzy transportation problem and to compare the efficiency obtained with that of GAs. We found DE has the capability of fast convergence and it outperforms GA in some cases. The result obtained in this study was written in a paper and was published in a Journal. In this proposal, we would like to study the effectiveness of applying DE to solve constrained optimization problems, and to compare the result obtained with that of GA. Also, we would like to know the effects of the performance of adjusting parameters in DE while solving constrained optimization problems. Finally, a high efficiency DE will be presented for solving constrained optimization problems. |
