簡易檢索 / 詳目顯示

研究生: 周彥辰
Jou, Yann-Chern
論文名稱: 以協同演化演算法求解單目標大規模全域最佳化問題
Solving Single-Objective Large-Scale Global Optimization Problems Using Cooperative Co-evolution Algorithm
指導教授: 蔣宗哲
Chiang, Tsung-Che
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2020
畢業學年度: 108
語文別: 中文
論文頁數: 79
中文關鍵詞: 演化演算法協同演化大規模全域最佳化問題單目標實數最佳化問題SHADE演算法自適應控制區域搜索
DOI URL: http://doi.org/10.6345/NTNU202001489
論文種類: 學術論文
相關次數: 點閱:152下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 隨著科學技術的進步及大數據的時代來臨,我們面臨的最佳化問題越來越龐大,變數也越來越多,甚至多達上千個;隨著最佳化問題的維度增加,大部分演化演算法的性能將因此迅速惡化而陷入高維度災難。因此,近年來有越來越多的演化計算領域學者投入大規模全域最佳化問題的研究並應用於求解生活中的實際問題。
    本研究結合目前兩大主流應用於大規模單目標實數最佳化的方法—協同演化框架 (CC) 和SHADE演算法,提出CBCCLS-mSHADE-RDG3 演算法。從大量的參數調整實驗到演算法行為設計與驗證,一步一步將CC與SHADE演算法結合。於CC框架下,我們採用RDG3 演算法做為問題分解策略;使用CBCC3 進行計算資源的分配,給予對整體適應值貢獻度高的子族群更多必須的計算資源提升演算法效能;以改良版 mSHADE演化子族群。另外,我們提出一個新穎的設計,於 CBCC3 架構下,對適應值貢獻度高的子族群除了使用mSHADE演算法進行演化外,我們以額外區域搜尋演算法MTS-LS1 協助提升最佳解之品質。此獨特設計從實驗結果驗證得知,不僅可以穩定LSGO問題解的品質,更可以提升求解部分可疊加分解問題的效能,整體演算法表現與近兩年的LSGO比賽優勝演算法相比頗具競爭力。

    中文摘要 i 致謝 ii 目錄 iii 附表目錄 v 附圖目錄 vi 第一章 緒論 1 1.1 研究背景與動機 1 1.2 研究問題定義 2 1.3 差分演化演算法 4 1.3.1 解個體編碼與評估 5 1.3.2 初始化解個體 6 1.3.3 突變策略 6 1.3.4 交配策略 7 1.3.5 選擇策略 8 1.4 協同演化演算法框架 8 1.5 研究目的與方法 12 1.6 論文架構 13 第二章 文獻探討 14 2.1 第一個協同演化演算法CCGA 14 2.2 CCEA問題分解策略 16 2.2.1 靜態分群與隨機變數分群策略 16 2.2.2 基於學習變數交互關係的分群策略 17 2.3 CCEA計算資源分配策略 21 2.4 CCEA優化演算法 23 第三章 CBCCLS-mSHADE-RDG3演算法 25 3.1 CBCCLS-mSHADE-RDG3演變歷程 25 3.1.1 協同演化演算法結合SHADE 25 3.1.2 加入計算資源分配CBCC3 26 3.1.3 基於CBCC3加入區域搜尋演算法 27 3.2 CC問題分解策略–RDG3 29 3.3 mSHADE演算法 34 3.3.1 子族群初始化 34 3.3.2 突變策略 34 3.3.3 交配策略 35 3.3.4 選擇策略 35 3.3.5 參數控制機制—記憶體系統 35 3.3.6 本研究基於SHADE的改動部分 37 3.3.7 mSHADE演算法虛擬碼 39 3.4 區域搜索演算法MTS-LS1 41 3.5 CBCCLS-mSHADE-RDG3虛擬碼 43 第四章 實驗設計與結果 45 4.1 測試函式集 45 4.2 實驗環境設定與效能測試 46 4.3 演算法參數設定 47 4.4 演算法參數調整實驗 48 4.5 SHADE結合CC架構實驗 53 4.6 優化演算法設計調整實驗 54 4.6.1 SHADE演算法加入記憶體擾動機制實驗 55 4.6.2 SHADE演算法加入線性族群縮減機制實驗 56 4.7 加入CBCC3計算資源分配實驗 57 4.8 基於CBCC3計算資源分配加入區域搜尋 58 4.9 CBCCLS-mSHADE-RDG3演算法效能 60 4.10 比較文獻算法 65 第五章 結論與未來研究方向 70 參考文獻 72 附錄 1: CEC2013 LSGO測試函式定義 76 附錄 2: 實驗環境硬體規格表 79

    [1] A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, 2003.
    [2] O. B. Haddad, A. Afshar, and M. A. Mariño, “Honey-bees mating optimization (HBMO) algorithm: a new heuristic approach for water resources optimization,” Water Resources Management, vol. 20, pp. 661-680, 2006.
    [3] M. A. Abido, “Environmental/economic power dispatch using multiobjective evo-lutionary algorithms,” In: Proceedings of 2003 IEEE Power Engineering Society General Meeting, pp. 920-925, 2003.
    [4] D. Molina, A. R. Nesterenko, and A. LaTorre, “Comparing large-scale global optimization competition winners in a real-world problem,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2019), Wellington, New Zealand, pp. 359-365, 2019.
    [5] R. E. Bellman, Dynamic Programming, Princeton University Press, 1957.
    [6] R. E. Bellman, Adaptive Control Processes: A Guided Tour, Princeton University Press, 1961.
    [7] X. Li, K. Tang, M. Omidvar, Z. Yang, and K. Qin, “Benchmark functions for the CEC’2013 special session and competition on large scale global optimization,” Technical Report, Evolutionary Computation and Machine Learning Group, RMIT University, Australia, 2013.
    [8] IEEE Task Force on Large-Scale Global Optimization, url: http://www.tflsgo.org/
    [9] IEEE Congress on Evolutionary Computation 2020 Special Session on Large Scale Global Optimization, url: http://www.tflsgo.org/special_sessions/wcci2020.html
    [10] D. Molina, A. LaTorre, and F. Herrera, “SHADE with iterative local search for large-scale global optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2018), Rio de Janeiro, pp. 1-8, 2018.
    [11] A. A. Hadi, A. W. Mohamed, and K. M. Jambi, “LSHADE-SPA memetic framework for solving large-scale optimization problems,” Complex & Intelligent Systems, Volume 5, Issue 1, pp 25-40, 2019.
    [12] D. Molina and F. Herrera, “Iterative hybridization of DE with local search for the CEC'2015 special session on large scale global optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2015), Sendai, pp. 1974-1978, 2015.
    [13] J. Brest, A. Zamuda, B. Boskovic, M. S. Maucec, and V. Zumer, “High-dimensional real-parameter optimization using Self-Adaptive Differential Evolution algorithm with population size reduction,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2008), Hong Kong, pp. 2032-2039, 2008.
    [14] Y. Sun, X. Li, A. Ernst, and M. N. Omidvar, “Decomposition for large-scale optimization problems with overlapping components,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2019) , Wellington, New Zealand, pp. 326-333, 2019.
    [15] W. Liu, Y. Zhou, B. Li, and K. Tang, “Cooperative co-evolution with soft grouping for large scale global optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2019), Wellington, New Zealand, pp. 318-325, 2019.
    [16] J. Liu and K. Tang, “Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution,” In: Proceedings of Intelligent Data Engineering and Automated Learning, pp. 350-357, 2013.
    [17] Z. Yang, K. Tang, and X. Yao, “Large scale evolutionary optimization using cooperative coevolution,” Information Science, vol. 178, no. 15, pp. 2986-2999, 2008.
    [18] D. Molina, M. Lozano, and F. Herrera, “MA-SW-Chains: Memetic algorithm based on local search chains for large scale continuous global optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2010), Barcelona, pp. 1-8, 2010.
    [19] L. Y. Tseng and C. Chen, “Multiple trajectory search for large scale global optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2008), Hong Kong, pp. 3052-3059, 2008.
    [20] X. Ma et al., “A survey on cooperative co-evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol. 23, no. 3, pp. 421-441, June 2019.
    [21] R. Storn and K. Price, “Differential evolution a simple and efficient heuristic for global optimization over continuous spaces,” Global Optimization, vol. 11, no. 4, pp. 341-359, 1997.
    [22] M. A. Potter and K. A. De Jong, “A cooperative coevolutionary approach to function optimization,” In: Proceedings of International Conference on Parallel Problem Solving from Nature, pp. 249-257, 1994.
    [23] Z. Yang, K. Tang, and X. Yao, “Differential evolution for high-dimensional function optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2007), Singapore, pp. 3523-3530, 2007.
    [24] X. Li and X. Yao, “Cooperatively coevolving particle swarms for large scale optimization,” IEEE Transactions on Evolutionary Computation, vol. 16, no. 2, pp. 210-224, Apr. 2012.
    [25] R. Tanabe and A. Fukunaga, “Success-history based parameter adaptation for dif-ferential evolution,” In: Proceedings of IEEE Congress on Evolutionary Computa-tion (CEC2013), Cancun, pp. 71-78, 2013.
    [26] F. V. D. Bergh and A. P. Engelbrecht, “A cooperative approach to particle swarm optimization,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, pp. 225-239, Jun. 2004.
    [27] Z. Yang, K. Tang, and X. Yao, “Self-adaptive differential evolution with neighborhood search,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2008), Hong Kong, pp. 1110-1116, 2008.
    [28] Z. Yang, K. Tang, and X. Yao, “Multilevel cooperative coevolution for large scale optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2008), Hong Kong, pp. 1663-1670, 2008.
    [29] M. N. Omidvar, X. Li, Y. Mei, and X. Yao, “Cooperative co-evolution with differential grouping for large scale optimization,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 3, pp. 378-393, Jun. 2014.
    [30] M. Tezuka, M. Munetomo, and K. Akama, “Linkage identification by nonlinearity check for real-coded genetic algorithms,” In: Proceedings of Genetic Evolutionary Computation Conference, LNCS 3103, pp. 222-233, 2004.
    [31] Y. Sun, M. Kirley, and S. K. Halgamuge, “Extended differential grouping for large scale global optimization with direct and indirect variable interactions” , In: Proceedings of Genetic Evolutionary Computation Conference, pp. 313-320, 2015.
    [32] Y. Mei, M. N. Omidvar, X. Li, and X. Yao, “A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization,” ACM Transactions on Mathematical Software, vol. 42, no. 2, pp. 1-13, 2016.
    [33] M. N. Omidvar, M. Yang, Y. Mei, X. Li, and X. Yao, “DG2: A faster and more accurate differential grouping for large-scale black-box optimization,” IEEE Transactions on Evolutionary Computation, vol. 21, no. 6, pp. 929–942, Dec. 2017.
    [34] Y. Sun, M. Kirley, and S. K. Halgamuge, “A recursive decomposition method for large scale continuous optimization, ” IEEE Transactions on Evolutionary Computation, vol. 22, no. 5, pp. 647-661, Oct. 2018.
    [35] Y. Sun, M. N. Omidvar, M. Kirley, and X. Li, “Adaptive threshold parameter estimation with recursive differential grouping for problem decomposition,” In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 889-896, 2018.
    [36] N. Hansen and A. Ostermeier, “Completely derandomized self-adaptation in evolution strategies,” Evolutionary Computation, vol. 9, no. 2, pp. 159-195, 2001.
    [37] M. Yang, A. Zhou, C. Li, and X. Yao, “An efficient recursive differential grouping for large-scale continuous problems,” IEEE Transactions on Evolutionary Computation, doi: 10.1109/TEVC.2020.3009390, 2020.
    [38] K. Tang, X. Li, P. Suganthan, Z. Yang, and T. Weise, “Benchmark functions for the CEC'2010 special session and competition on large scale global optimization,” 2009.
    [39] M. N. Omidvar, X. Li, and X. Yao, “Smart use of computational resources based on contribution for cooperative co-evolutionary algorithms”, In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 1115-1122, 2011.
    [40] M. N. Omidvar, B. Kazimipour, X. Li, and X. Yao, “CBCC3 — A contribution-based cooperative co-evolutionary algorithm with improved exploration/ exploitation balance,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2016), Vancouver, BC, pp. 3541-3548, 2016.
    [41] J. Zhang and A. C. Sanderson, “JADE: Adaptive differential evolution with optional external archive,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 5, pp. 945-958, Oct. 2009.
    [42] G. A. Trunfio, P. Topa, and J. Was, “A new algorithm for adapting the configuration of subcomponents in large-scale optimization with cooperative coevolution,” Information Science, vol. 372, pp. 773-795, Dec. 2016.
    [43] M. Sharawi and M. El-Abd, “A cooperative co-evolutionary LSHADE algorithm for large-scale global optimization,” In: Proceedings of IEEE Symposium Series on Computational Intelligence (SSCI2017), pp. 1-8, 2017.
    [44] M. El-Abd, “Hybrid cooperative co-evolution for large scale optimization,” In: Proceedings of IEEE Symposium on Swarm Intelligence, pp. 348-354, 2014.
    [45] W. Shi, W.-N. Chen, Q. Yang, and J. Zhang, “A multi-optimizer cooperative coevolution method for large scale optimization,” In: Proceedings of IEEE Symposium on Swarm Intelligence, pp. 1-8, 2014.
    [46] R. Tanabe and A. S. Fukunaga, “Improving the search performance of SHADE using linear population size reduction,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2014), Beijing, pp. 1658-1665, 2014.
    [47] J. Yeh, T. Chen, and T. Chiang, “Modified L-SHADE for single objective real-parameter optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2019), Wellington, New Zealand, pp. 381-386, 2019.
    [48] Y. Jou, S. Wang, J. Yeh, and T. Chiang, “Multi-population modified L-SHADE for single objective bound constrained optimization,” In: Proceedings of IEEE Congress on Evolutionary Computation (CEC2020), Glasgow, United Kingdom, pp. 1-8, 2020.
    [49] J. L. Morales and J. Nocedal, “Remark on algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization,” ACM Transactions on Mathematical Software (TOMS), vol. 38, no. 1, pp. 7:1-7:4, Dec. 2011.
    [50] Toolkit for Automatic Comparison of Optimizers, url: http://tacolab.org/bench

    無法下載圖示 電子全文延後公開
    2025/09/14
    QR CODE