臺灣博碩士論文加值系統

差分演化演算法(Differential evolution)為近年來新穎且正迅速發展的演化式計算，該演算法擁有結構簡單、容易使用、及快速收斂之特性。而不同於傳統演算法的複雜流程，差分演化演算法除了流程簡單外，更因其優越之求解能力，而被廣泛地運用於複雜型最佳化問題之中，也因此成為近年來學者熱門研究對象之一。
與大多數傳統之演算法相同，差分演算法於求解過程中，同樣有收斂不穩定，，及陷入區域最佳解之問題存在。因此，現今許多學者針對此一缺點去進行改良，除了調整參數及改良演化機制之外，本研究嘗試結合多群的協同演化(Co-evolutionary)的架構及重置因子(reset factor) ，進而提出一CO-DE演算法。 協同演化能預防演算法的過早收斂，同時維持粒子多樣性，因此，本研究期望利用結合多群協同架構同時兼顧粒子搜尋過程的精度和效率，並利用重置因子更新機制防止粒子陷入停滯。

Differential evolution, termed DE, is a novel and rapidly developed evolution computation in recent year. There are some advantages of DE, including simple structure, easy use and rapid convergence speed. Besides, DE can be also applied on complex optimization problem. However, there are some problems, such as premature convergence and stagnation, remaining in DE algorithm. To overcome those disadvantages, a different method was proposed, named CO-DE, by combining with a simple co-evolutionary model and reset mechanism. Thus, CO-DE can maintain appropriate swarm diversity and reduce the premature convergence. On the other hand, a reset mechanism was set to avoid the particle stagnates, which can further improve the performance of differential evolution. The proposed model can be now successfully applied with some well-known benchmark functions.

目錄
摘要 I
Abstract II
致謝詞 III
第一章 緒論 1
1.1研究背景與動機 1
1.2研究問題與目的 2
1.3研究流程架構 4
第二章 文獻探討 6
2.1演化式計算(Evolutionary Computation； EC) 6
2.2差分演化演算法(Differential Evolution; DE) 7
2.2.1 差分演化演算法發展背景 7
2.2.2差分演算法概念及流程 8
2.2.3 差分演化演算法之策略探討 12
2.3 共演化模式(Co-Evolutionary Mode) 13
2.4其它以共演化協同模式為基礎之演算法 14
2.4.1 一個競爭式及合作協同之多群架構運用於粒子群演算法 15
2.4.2 多粒子群協同優化算法(PSCO) 17
2.4.3以協同架構為基礎之差分演化演算法於約束問題 17
第三章 研究方法 21
3.1 多群協同的差分演化演算法演算流程 21
3.2 測試函數 25
第四章 實驗結果 31
4-1 參數設定 31
4-2 維度實驗 33
4.2.1維度實驗 – Sphere函數(f1) 34
4.2.2維度實驗 – Rosenbrock函數(f2) 36
4.2.3維度實驗 – Rastrigrin函數(f3) 38
4.2.4維度實驗 – Griwank函數(f4) 40
4.2.5維度實驗 – Ackley函數(f5) 42
4-3 相關研究比較 44
第五章 結論及建議 46
5-1 結論 46
5-2 未來研究 47
參考文獻 48

圖目錄
圖1-1 研究流程 5
圖2-1 演化流程 7
圖2-2 差分演化演算法運算子 10
圖2-3 差分演化演算法流程圖 12
圖2-4 合作協同型共演化模式(Cooperative co-ecolution) 16
圖2-5 競爭型共演化模式(Competitive co-ecolution) 16
圖2-6 CODE流程架構圖 19
圖3-1 CO-DE演算法流程圖 22
圖3-2 CO-DE演化架構 24
圖3-3 重置因子置換方法 25
圖3-4 Sphere三維圖示 27
圖3-5 Rosenbrock三維圖示 27
圖3-6 Rastrigin三維圖示 28
圖3-7 Griewank三維圖示 29
圖3-8 Ackley三維圖示 30
圖 4-1 Sphere(f1) 10維收斂曲線圖 35
圖 4-2 Sphere(f1) 20維收斂曲線圖 35
圖 4-3 Sphere(f1) 30維收斂曲線圖 35
圖 4-4 Rosenbrock(f2) 10維收斂曲線圖 37
圖 4-5 Rosenbrock(f2) 20維收斂曲線圖 37
圖 4-5 Rosenbrock(f2) 30維收斂曲線圖 38
圖 4-7 Rastrigrin(f3) 10維收斂曲線圖 39
圖 4-8 Rastrigrin(f3) 20維收斂曲線圖 39
圖 4-9 Rastrigrin(f3) 30維收斂曲線圖 39
圖 4-8 Griwank(f4) 10維收斂曲線圖 41
圖 4-9 Griwank(f4) 20維收斂曲線圖 41
圖 4-10 Griwank(f4) 30維收斂曲線圖 41
圖 4-11 Ackley(f5) 10維收斂曲線圖 43
圖 4-12 Ackley(f5) 20維收斂曲線圖 43
圖 4-13 Ackley(f5) 30維收斂曲線圖 44

表目錄
表1-1 差分演算法及粒子群演算法優缺點整理 3
表2-1 差分演算法主要公式及演算概念 12
表3-1 測試函數 26
表4-1 DE/rand1參數設定 31
表4-2 DE/rand-to-best1參數設定 32
表4-3 CO-DE參數設定 32
表4-4 Sphere函數測試結果 34
表4-5 Rosenbrock函數測試結果 36
表4-6 Rastrigrin函數測試結果 38
表4-7 Griwank函數測試結果 40
表4-8 Ackley函數測試結果 42
表4-9 相關研究之比較實驗結果 45

參考文獻
[1] R. Storn and K. Price, “Minimizing the real functions of the ICEC'96 contest by differential evolution “, Evolutionary Computation, 1996., Proceedings of IEEE International Conference on 20-22 May 1996 Page(s):842 – 844
[2] R. Storn and K. Price, “Differential Evolution- a simple and efficient adaptive scheme for global optimization over continuous spaces“, Technical Report TR-95-012, ICSI.
[3] K. Price, “Differential Evolution: A Fast and Simple Numerical Optimizer,” 1996 Biennial Conference of the North American Fuzzy Information Processing Society, Jun. 1996, pp.524-527.
[4] N. Amin and W. Hong, “Co-evolutionary Self-Adaptive Differential Evolution with a Uniform-distribution Update Rule”, Intemational Symposium on Intelligent Control Munich, Germany, 2006, October 4-6.
[5] M. Dorigo, V. Maniezzo and A. Colorni, “The ant system: Optimizatoin by a colony of cooperating agents”, IEEE Transactions on Systems and Cybernetics - Part B, 1996, Vol 26-1, pp.29-41.
[6] T. Back, D. B. Fogel, and Z. Michalewicz, “Evolutionary Computation 2: Advanced Algorithms and Operators”, Bristol, U.K., Institute of Physics, 2000.
[7] P.R. Ehrlich and P.H. Raven, “Butter Dies and plants: a study in co-evolution”, 1964, Evolution vol.18 pp.586–608.
[8] R.C. Eberhart, and J. Kennedy, “A new optimizer using particle swarm theory”, Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan,1996, pp.39-43.
[9] J. Kennedy and R.C. Eberhart, “ Particle swarm optimization”, Proc. IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, pp. IV：1942-1948.Proceedings of the First IEEE Conference, 1995, June Vol 2 pp.645-650.
[10] C.D. Rosin and R.K. Belew ,“New methods for Competitive Co-evolution”, Evolutionary Computation 1997, 5:1-30.
[11] W.D. Hillis, “Coevolving parasites improve simulated evolution as an optimization procedure”, In Langton, C.G., Taylor, C., Farmer, J.D., & Rasmussen, S. (Eds), Artificial Life II , Redwood City, CA: Addison Wesley. 1992, pp.313-324.
[12] F. van den Bergh and A.P. Engelbrecht, “A cooperative approach to particle swarm optimization”, IEEE Transaction on Evolutionary Computation 8 (3), 2004, 225–239.
[13]C.K. Goh, K.C. Tan, D.S. Liu and S.C. Chiam, “A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design” , European Journal of Operational Research, 2009, p42-45.
[14] K. Price, “Differential Evolution: A Fast and Simple Numerical Optimizer,” 1996 Biennial Conference of the North American Fuzzy Information Processing Society, Jun. 1996, pp.524-527.
[15] N. Amin, ”Co-evolutionary Self-Adaptive Differential Evolution with a Uniform-distribution Update Rule”, International Symposium on Intelligent Control, Munich, Germany, 2006, October 4-6.
[16] M.M. Ali *, “Differential evolution with preferential crossover”, European Journal Of operational Research, 181, 2007, 1137–1147.
[17] T. Ville and N. Ferrante, “Enhancing Differential Evolution Frameworks by Scale Factor Local Search - Part I”, IEEE, May 2009, P118 – 125.
[18] N. Noman and H. Iba, “Accelerating Differential Evolution Using an Adaptive Local Search,” IEEE Transactions on Evolutionary Computation, vol. 12, no. 1, Feb. 2008, pp. 107-125.
[19] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization,” IEEE Transactions on Evolutionary Computation, Dec. 2003, pp. 1-20.
[20] Bo Liu, Hannan Ma and Xuejun Zhang, “A Memetic Co-evolution Algorithm for Constrained Optimization”, IEEE, 2007.
[21] P, Husband and F. Mill, “Simulated co-evolution as the mechanism for emergent planning and scheduling”, Proceedings of 4th International Conference on Genetic Algorithms, San Mateo,Morgan Kaufmann, 1991, 264-270.
[22] C.K. Goh, K.C. Tan, D.S. Liu and S.C. Chiam, “A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design”, European Journal of Operational Research, 202, 2010, p42–54.
[23]C.H.Liang and C.Y. Chung,“Parallel Optimal Reactive Power Flow Based on Cooperative Co-Evolutionary Differential Evolution and Power System Decimposition”, IEEE Transactions on Power Systems, VOL. 22, No.1, February, 2007.
[24] B. Olsson,“Co-evolutionary search in asymmetric spaces, Information Science”, vol.133, 2001, pp.103-125.
[25] A.K. Qin, V.L.Huang, and P.N. Suganthan, “Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization”,IEEE transactions on evolutionary computation, vol.13,No 2, April 2009.
[26]Jing. J., Jianchao. Z., Chongzhao. H., and Qinghua. W., “Knowledge-based cooperative particle swarm optimization”, Applied Mathematics and Computation, 205, 2008, pp.861–873.
[27] N. Ben and L. Li., “A Novel PSO-DE-Based Hybrid Algorithm for Global Optimization”, Computer Science, Vol. 5227, 2008, pp. 156-163.
[28]李愛國，“多粒子群協同優化算法”，負旦學報，第四十三卷，第一期：923-925頁，2004。
[29]胡中波、熊盛武、胡付高、蘇清華，“改進的差分演化算法及其在函數優化
中的應用”，武漢理工大學學報，第29 卷，第四期，2007 年，第125-127 頁。
[30]林豐澤，“演化式計算上篇：演化式演算法的三種理論模式”，智慧科技與應用統計學報，第3卷，第1期，2005年6月，第1-28頁。
[31]郭信川、劉清祥、許凱雄，“粒子群演算法於最佳化問題之研究”，第一屆台灣作業研究學會學術研討會，2004年。
[32]張宏瑋，“動態式準則評估於旅遊行程安排之最優化”，大同大學資訊經營所 碩士論文，第8-11頁。
[33]鞏進衛，孫曉燕，“協同進化遺傳算法理論及應用”，智能科技2009年5月，ISBN:9787030244642。