研究生: |
周彥辰 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 |
論文種類: | 學術論文 |
相關次數: | 點閱:109 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
隨著科學技術的進步及大數據的時代來臨,我們面臨的最佳化問題越來越龐大,變數也越來越多,甚至多達上千個;隨著最佳化問題的維度增加,大部分演化演算法的性能將因此迅速惡化而陷入高維度災難。因此,近年來有越來越多的演化計算領域學者投入大規模全域最佳化問題的研究並應用於求解生活中的實際問題。
本研究結合目前兩大主流應用於大規模單目標實數最佳化的方法—協同演化框架 (CC) 和SHADE演算法,提出CBCCLS-mSHADE-RDG3 演算法。從大量的參數調整實驗到演算法行為設計與驗證,一步一步將CC與SHADE演算法結合。於CC框架下,我們採用RDG3 演算法做為問題分解策略;使用CBCC3 進行計算資源的分配,給予對整體適應值貢獻度高的子族群更多必須的計算資源提升演算法效能;以改良版 mSHADE演化子族群。另外,我們提出一個新穎的設計,於 CBCC3 架構下,對適應值貢獻度高的子族群除了使用mSHADE演算法進行演化外,我們以額外區域搜尋演算法MTS-LS1 協助提升最佳解之品質。此獨特設計從實驗結果驗證得知,不僅可以穩定LSGO問題解的品質,更可以提升求解部分可疊加分解問題的效能,整體演算法表現與近兩年的LSGO比賽優勝演算法相比頗具競爭力。
[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