臺灣博碩士論文加值系統

近年來演化式計算(Evolution Computation；EC)對於現實世界中的複雜最佳化問題，如排程規劃、資源分配、組合最佳化等NP-Hard問題展現其優越的求解能力。自1996年首次提出的差分演化演算法(Differential Evolution；DE)更因其具備結構簡單、高效率、高精確度及所需設定參數較少等特性受到重視，並於諸多應用領域當中展現與以往常見之演化式演算法更為優良的求解成效。
透過相關研究的整理發現，差分演算法雖本身具備強大的求解能力，但演算法本身於最佳化問題求解上仍存在部分尚待解決之疑慮，如收斂情形的不穩定、易跳脫解空間以及一般演化式演算法所常見的通病“易陷入區域最佳解” 的問題，導致差分演算法之效能有所限制。故本研究提出活化策略差分演算法(Activated Strategy Differential Evolution；ASDE)，期望透過活化策略(Activated Strategy；AS)的導入，進一步產生擾動的效果以有效改良差分演化演算法並期許獲得全面性的穩定成效，透過活化策略導入將於求解過程中再次激化演算法，以強化差分演算法於求解效能與穩定性上的平衡。

Evolutionary Computation (EC) provides high performance on real world optimization problems such as scheduling, resource distribution, portfolio optimization etc. Differential Evolution (DE) algorithm was first reported in 1996. Based on the characteristics of simple structure, high accuracy and efficiency, and the requirement of fewer parameters, DE has received significant attention from researchers. It has been applied to numerous fields and performs much better than other evolutionary computation.
Although DE represents powerful performance, but it has attach importance to the drawbacks of unstable convergence, breakaway the solution space, and the common defect of evolution computation “dropping into regional optimum”. In this study, we attempt to improve the traditional differential evolution algorithm and propose a novel algorithm “Activated Strategy Differential Evolution” (ASDE). Based on import the Activated Strategy (AS) intensified the structure of traditional DE for balancing the solution accuracy and stability.

論文摘要…………………………………………………………………………..I
Abstract………………………………………………………………………….II
致謝詞……………………………………………………………………………III
目錄…………………………………………………………………………………V
圖目錄……………………………………………………………………………VII
表目錄………………………………………………………………………….VIII
第一章　緒論......................................................1
1.1 研究背景與動機................................................1
1.2 研究目的與問題............................................3
1.3研究架構.......................................................5
第二章 文獻探討...................................................6
2.1 仿生學....................................................6
2.2 演化式計算....................................................8
2.3基因演算法....................................................12
2.3.1 基因演算法發展背景.........................................12
2.3.2 基因演算法概念與流程.......................................12
2.3.3基因演算法的編碼方式........................................15
2.4差分演化演算法................................................19
2.4.1 差分演化演算法發展背景.....................................19
2.4.2 差分演化演算法之流程與策略.................................22
2.5 相關研究.....................................................26
第三章　研究方法.................................................30
3.1 建立差分演算法之改良架構.....................................30
3.2 活化策略.....................................................33
3.2.1 概念啟發...................................................33
3.2.2 運算流程...................................................34
3.3 測試函數.....................................................35
3.4 實驗流程.....................................................38
3.4.1 活化策略成效...............................................39
3.4.2 測試函數位移...............................................39
3.4.3 相關研究之比較.............................................40
第四章 實驗設計..................................................41
4.1實驗環境與參數設定............................................41
4.2活化策略成效..................................................42
4.2.1確立改良目標................................................42
4.2.2驗證ASDE有效性..............................................48
4.3測試函數位移..................................................53
4.4相關研究之比較................................................60
第五章 結論與未來建議............................................63
參考文獻.........................................................64



圖目錄
圖1-1 研究流程 ...................................................................................................... 5
圖2-1 仿生學轉化概念模型 ................................................................................... 6
圖2-3 演化式計算共同運作流程............................................................................ 9
圖2-4 基因演算法示意圖 ..................................................................................... 14
圖2-5 基因演算法編碼示意圖 ............................................................................. 15
圖2-6 基因演算法交配機制示意圖 ...................................................................... 17
圖2-7 基因演算法突變機制示意圖 ...................................................................... 18
圖2-8 交配機制示意圖 ......................................................................................... 20
圖2-9 差分演化演算法運算流程.......................................................................... 24
圖2-10 TSP 問題交配MOX 交配 ......................................................................... 27
圖3-1 活化策略差分演算法運作流程 .................................................................. 32
圖3-2 活化策略示意圖 ......................................................................................... 34
圖3-3 測試函數f1 ................................................................................................ 36
圖3-4 測試函數f2 ................................................................................................ 36
圖3-5 測試函數f3 ................................................................................................ 37
圖3-6 測試函數f4 ................................................................................................ 37
圖4-1 測試函數f1 收斂圖 .................................................................................... 49
圖4-2 測試函數f2 收斂圖 .................................................................................... 49
圖4-3 測試函數f3 收斂圖 .................................................................................... 50
圖4-4 測試函數f4 收斂圖 .................................................................................... 50



表目錄
表1-1 差分演算法優缺點整理 ............................................................................... 4
表2-1 差分演算法之策略 ..................................................................................... 23
表3-1 測試函數 .................................................................................................... 35
表4-1 實驗環境 .................................................................................................... 41
表4-2 參數設定 .................................................................................................... 41
表4-3 30 維實驗結果 ............................................................................................. 43
表4-4 60 維實驗數據 ............................................................................................. 48
表4-5 函數正向位移 ............................................................................................. 54
表4-6 函數負向位移 ............................................................................................. 55
表4-7 函數正向位移實驗數據 ............................................................................. 56
表4-8 函數負向位移實驗數據 ............................................................................. 57
表4-9 正向位移前後ASDE 之實驗數據.............................................................. 58
表4-10 負向位移前後ASDE 之實驗數據 ............................................................ 59
表4-11 相關研究比較之函數與設定 .................................................................... 61
表4-12 相關研究比較之函數與設定 .................................................................... 61
表4-13 相關研究實驗數據之比較 ........................................................................ 62

[1] J. H. Holland, “Adaptation in Natural and Artificial System,” Ann Arbor:The University of Michigan Press, 1975.
[2] H.–P. Schwefel, “Numerical Optimization of Computer Models,” Wiley, Chichester, 1981.
[3] D. E. Goldberg, “Genetic Algorithms in Search Optimization and Machine Learning,” Addison-Wesley, 1989.
[4] Th. Back, F. Hoffmeister and H.-P. Schwefel, “A survey of evolution strategies,” Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, 1991, pp. 2-9.
[5] W. M. Spears, K. A. De Jong, T. Back, D. B. Fogel and H. deGaris, “An overview of evolutionary computation,” Proceedings of the 1993 European Conference on Machine Learning, 1993.
[6] Th. Back and H.-P. Schwefel, “An overview of evolutionary algorithms for parameter optimization,” Evolutionary Computation, vol.1 no.1, 1993, pp. 1-24.[7] K. Price, “Differential Evolution: A Fast and Simple Numerical Optimizer”, 1996 Biennial Conference of the North American Fuzzy Information Processing Society, June 1996, pp.524-527.
[8] R. Storn, “On the usage of differential evolution for function optimization”, 1996 Biennial Conference of the North American Fuzzy Information Processing Society, June 1996, pp.519–523.
[9] R. Storn and K. Price, “Minimizing the real functions of the ICEC'96 contest by Differential Evolution”, Int. Conf. on Evolutionary Computation, Nagoya, Japan, 1996, pp. 842-844.
[10] P. J. Bentley, T. Gordon, J. Kim and S. Kumar, “New trends in Evolutionary Computation,” The 2001 Congress on Evolutionary Computation, 2001.
[11] M. M. Ali, “Differential evolution with preferential crossover,” European journal of operational research, 2007, pp.1137-1147.
[12] F.-Z. Huang, L. Wang and H. Qie, “An effective co-evolutionary differential evolution for constrained optimization,” Applied mathematics and computation, 2007, pp.340-356.
[13] H.-K. Kim, J.-K. Chong, K.-Y. Park and D. A. Lowther, “Differential Evolution Strategy for Constrained Global Optimization and Application to Practical Engineering Problems,” IEEE Transactions on Magnetics, vol.43, 2007, pp. 1565-1568.
[14] H. Muhlenbein, G. Schleuter and O. Kramer, “Evolution algorithms in combinatorial optimization,” Parallel Computing, vol.7, 1988, pp. 65-88.
[15] I. Rechenberg, “Cybernetic solution path of an experimental problem,” Royal Aircraft Establishment, Library Translation, 1965.
[16] G. C. Onwubolu, “Optimizing CNC Drilling Machine Operations: Traveling Salesman Problem-Differential Evolution Approach,” in New Optimization Techniques in Engineering, 2004, pp. 537–566.
[17] E. M. Montes, J. V. Reyes, and C. A. CoelloCoello, “A Comparative Study of Differential Evolution Variants for Global Optimization,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2006
[18] D. He, F. Wang, and Z. Mo, “A hybrid genetic algorithm approach based on differential evolution for economic dispatch with valve-point effect,” Electrical Power and Energy Systems, vol.30, 2008, pp. 31-38.
[19] D. He, F. Wang, and Z. Mo, “An effective co-evolutionary differential evolution for constrained optimization,” Applied Mathematics and Computation, vol.186, 2007, pp. 340-356.
[20]M. Pant, M. Ali, and V. P. Singh, "Differential Evolution with Parent Centric Crossover," Computer Modeling and Simulation, 2008. EMS '08. Second UKSIM European Symposium on, pp. 141-146, 2008.
[21] M. Varadarajan and K.S. Swarup, “Network loss minimization with voltage security using differential evolution,” Electric Power Systems Research, vol.78, 2008, pp. 815-823.
[22] J. Li, P. Chen, and Z. Liu, “Solving Traveling Salesman Problems by Genetic Differential Evolution with Local Search,” Workshop on Power Electronics and Intelligent Transportation System, 2006, pp.454-457.
[23] J. Li, C. Wang, “A Modified Particle Swarm Optimization with Adaptive Mutation Operator,” Workshop on Intelligent Information Technology Application, 2007, pp.133-136.
[24] N. Higashi, H. Iba, “Particle Swarm Optimization with Gaussian Mutation,” Swarm Intelligence Symposium, 2003. SIS '03. Proceedings of the 2003 IEEE, pp.72-79.
[25] J. Chen, Z. Ren, X. Fan, “Particle Swarm Optimization with Adaptive Mutation and ItsApplication Research in Tuning of PID Parameters,” Systems and Control in Aerospace and Astronautics, 2006. ISSCAA 2006. 1st International Symposium, 2006
pp.990-994.

[26] W. Gong, Z. Cai, L. Jiang, “Enhancing the performance of differential evolution using orthogonal design method,” Applied Mathematics and Computation, 2008, pp.57-69.
[27]林豐澤，“演化式計算上篇：演化式演算法的三種理論模式”，智慧科技與應用統計學報，第3卷，第1期, 2005 年 6 月，第1-28頁。
[28]林豐澤，“演化式計算下篇：基因演算法以及三種應用實例”，智慧科技與應用統計學報，第3卷，第1期，第 29-56頁， 2005 年 6 月。
[29]謝昆霖、沈進成、周君妍、鄭丞君，“基因演算法應用於顧客旅遊行程路徑最適化模式之研究”，旅遊管理研究，第四卷、第一期，2005年，第53-66頁。
[30]張英斌、吳啟瑞，“結合可行方向法與與基因演算法於濾波器之最佳規劃”，技術學刊，第二十卷，第一期，2005年，第43-56頁。
[31]胡中波、熊盛武、胡付高、蘇清華，“改進的差分演化算法及其在函數優化中的應用”，武漢理工大學學報，第29卷，第四期，2007年，第125-127頁
[32]高尚、楊靜宇，“群智能演算法及其應用”，2006年5月，ISBN：7508437985。
[33]鄢靖豐、張泊平、龔文引、潭水木，“一種新型的差分演化算法及其應用研究”， 計算機應用，第28卷，第三期，2008年，第719-725頁。
[34]賀毅朝、王熙照、寇應展，“一種具有混和編碼的二進制差分演化算法”，計算機研究與成果，第44卷，第9期，2007年，第1476-1484頁。
[35]岑海堂、陳五一，“仿生學及其演變”，機械設計，第24卷，第七期，2007年。
[36]謝曉鋒,張文俊,張國瑞,楊之廉，《差分演化的實驗研究》，控制與決策，第19 卷第1 期，第49-53頁，2004年1月。