研究生: |
陳少文 sao-wen chen |
---|---|
論文名稱: |
強化親代選擇機制之平行化高目標演化式演算法 A Parallel Many-objective Evolutionary Algorithm with Enhanced Mating Selection Mechanism |
指導教授: |
蔣宗哲
Chiang, Tsung-Che |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2013 |
畢業學年度: | 101 |
語文別: | 中文 |
論文頁數: | 78 |
中文關鍵詞: | 高目標 、演化式演算法 、平行化 、親代選擇 |
英文關鍵詞: | many-objective, evolutionary algorithm, parallelization, mating selection |
論文種類: | 學術論文 |
相關次數: | 點閱:216 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
當一個最佳化問題的求解目標數為兩個以上時,我們稱其為多目標最佳化問題 (multi-objective optimization problems),若目標數為四或四個以上時,則稱其為高目標最佳化問題 (many-objective optimization problems)。現實世界的最佳化問題中存在著許多高目標最佳化問題,傳統的多目標最佳化演算法只適合求解目標數四以下的問題,設計一個能夠求解高目標最佳化問題的演算法是目前演化式領域中的研究重點。
我們以非凌越性排序基因演算法 (NSGA-III) 為基底,深入觀察該演算法特性,改善親代選擇機制 (mating selection) 中選取親代的方式,優先改進族群中相對較差的區域,並搭配鄰域選取 (neighborhood-based selection) 概念,得到不錯的成效;在環境選擇機制 (environmental selection) 中,我們嘗試同時維持族群在目標空間與決策空間中的分散度,並使用其他方法替代原本 NSGA-III 演算法的選取機制,雖然成效不彰,但在實驗中我們觀察到了一些有趣的現象;我們更以島嶼模型 (island model) 將演算法平行化,透過預先分配給各島嶼屬於邊框權重向量的機制,在維持演算法原本求解能力的同時,還能加快整體的執行速度。
本論文所提出的各種改進機制可以互相搭配使用,以最佳版本的親代選擇機制配合平行化機制的狀況下 (ESP-NSGA-III),與原版的 NSGA-III 相比,求解 DTLZ1~4 並改變其問題目標數共 15 個測試問題中,在 Mann Whitney U 統計檢定下,我們的演算法有著 11 勝 3 和 1 負的優良表現。
[1] H. Ishibuchi, N. Tsukamoto & Y. Nojima, “Evolutionary many-objective optimization: A short review,” Proceedings of IEEE Congress on Evolutionary Computation, pp. 2419–2426, June. 2008.
[2] T. W. Simpson, W. Chen, J. K. Allen & F. Mistree, “Conceptual design of a family of products through the use of the robust concept exploration method,” in 6th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, vol. 2, pp. 1535–1545, 1996.
[3] H. Jain & K. Deb, “An improved adaptive approach for elitist nondominated sorting genetic algorithm for many-objective optimization,” Lecture Notes in Computer Science 7811: Evolutionary Multi-Criterion Optimization – EMO, pp. 307–321, 2013.
[4] K. Deb, A. Pratap, S. Agarwal & T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, issue 2, pp. 182–197, 2002.
[5] Q. Zhang & H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11(6), pp. 712–731, 2007.
[6] K. Deb & R. B. Agrawal, “Simulated binary crossover for continuous search space,” Complex Systems, vol. 9, pp. 115–148, Apr. 1995.
[7] E. Cantú-Paz, “A survey of parallel genetic algorithms,” Calculateurs Paralleles, vol. 10, pp. 141–171, 1998.
[8] K. Deb & H. Jain, “Handling many-objective problems using an improved NSGA-II procedure,” Proceedings of IEEE World Congress on Computational Intelligence, 2012
[9] H. Sato, H. E. Aguirre & K. Tanaka, “Controlling dominance area of solutions and its impact on the performance of MOEAs,” Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization – EMO, pp. 55–20, 2007.
[10] N. Drechsler, R. Drechsler & B. Becker, “Multi-objective optimization based on relation favour,” Lecture Notes in Computer Science 1993: Evolutionary Multi-Criterion Optimization – EMO, pp. 154–166, 2001.
[11] E. Zitzler & S. Künzli, “Indicator-based selection in multiobjective search,” Lecture Notes in Computer Science 3242: Parallel Problem Solving from Nature – PPSN VIII, pp. 832–842, 2004.
[12] N. Beume, B. Naujoks & M. Emmerich, “SMS-EMOA: multiobjective selection based on dominated hypervolume,” European Journal of Operational Research, pp. 1653–1669, 2007.
[13] K. Deb & J. Sundar, “Reference point based multi-objective optimization using evolutionary algorithms,” Proceedings of 2006 Genetic and Evolutionary Computation Conference, pp. 635–642, 2006.
[14] H. Ishibuchi, Y. Sakane, N. Tsukamoto & Y. Nojima, “Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations,” Proceedings of 2009 IEEE International Conference on Systems, Man, and Cybernetics, pp. 1820–1825, 2009
[15] K. Deb & K. Saxena, “Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems,” Proceedings of IEEE Congress on Evolutionary Computation, pp. 3353–3360, 2006.
[16] D. Brockhoff & E. Zitzler, “Are all objectives necessary? On dimensionality reduction in evolutionary multiobjective optimization,” Lecture Notes in Computer Science 4193: Parallel Problem Solving from Nature – PPSN IX, pp. 533–542, 2006.
[17] A. Sülflow, N. Drechsler & R. Drechsler, “Robust multi-objective optimization in high dimensional spaces,” Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization – EMO, pp. 715–726, 2007.
[18] D. Corne & J. Knowles, “Techniques for highly multiobjective optimization: Some non-dominated points are better than others,” Proceedings of 2007 Genetic and Evolutionary Computation Conference, pp. 773–780, 2007.
[19] M. Garza-Fabre, G. T. Pulido & C. A. C. Coello, “Ranking methods for many-objective optimization,” MICAI 2009: Advances in Artificial Intelligence, pp. 633–645, 2009.
[20] K. Deb & S. Tiwari, “Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization,” European Journal of Operational Research, vol. 185, issue 3, pp. 1062–1087, 2006.
[21] K. Köppen & K. Yoshida, “Substitute distance assignments in NSGA-II for handling many-objective optimization problems,” Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization – EMO, pp. 727–741, 2007.
[22] T. Wagner, N. Beume & B. Naujoks, “Pareto-, aggregation-, and indicator-based methods in many-objective optimization,” Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization – EMO, pp. 742–756, 2007.
[23] E. J. Hughes, “MSOPS-II: A general-purpose many-objective optimizer,” Proceedings of IEEE Congress on Evolutionary Computation, pp. 3944–3951, 2007.
[24] L. Thiele, K. Miettinen, P. J. Korhonen & J. Molina, “A preference-based interactive evolutionary algorithm for multiobjective optimization,” Helsinki School of Economics, Working Paper, 2007.
[25] H. Ishibuchi, N. Akedo & Y. Nojima, “Recombination of similar parents in SMS-EMOA on many-objective 0/1 knapsack problems,” PPSN’ 12 Proceedings of the 12th international conference on Parallel Problem Solving from Nature, vol. Part II, pp. 132–142, 2012.
[26] M. Garza-Fabre, G. T. Pulido & C. A. Coello Coello, “Two novel approaches for many-objective optimization,” Proceedings of IEEE Congress on Evolutionary Computation, 2010.
[27] K. Deb, L. Thiele, M. Laumanns & E. Zitzler, “Scalable test problems for evolutionary multi-objective optimization,” A. Abraham, L. Jain & R. Goldberg (eds.) Evolutionary Multi-objective Optimization, pp. 105–145, 2005.