簡易檢索 / 詳目顯示

研究生: 陳少文
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 負的優良表現。

    目 錄 中文摘要 i 誌 謝 ii 目 錄 iii 附表目錄 v 附圖目錄 vii 第一章 緒論 1 1.1 研究動機 1 1.2 背景知識 1 1.2.1 多目標最佳化問題 1 1.2.2 演化式演算法 3 1.2.3 平行演化式演算法 4 1.3 研究範疇 6 1.4 論文架構 7 第二章 文獻探討 8 2.1 求解高目標最佳化問題的難處 8 2.2 解決方式 10 2.2.1 變更柏拉圖凌越關係 11 2.2.2 採用不同的劃分階級方式 12 2.2.3 使用不同的分散度維持機制 13 2.2.4 使用指標函式計算適應度 14 2.2.5 使用純量化函式計算適應度 14 2.2.6 將偏好資訊加入搜尋條件中 15 2.2.7 減少求解目標的數量 15 第三章 強化親代選擇機制之平行化演算法 ESP-NSGA-III 17 3.1 NSGA-III 17 3.1.1 族群初始化 17 3.1.2 環境選擇 19 3.1.3 繁殖 24 3.1.4 終止條件 24 3.2 改進親代選擇機制 24 3.2.1 基於參考點的階層式親代選擇機制 (MS-RPU) 25 3.2.2 基於參考點的階層式親代選擇機制改進版 (MS-RPW) 25 3.2.3 強化劣勢參考點之親代選擇機制 (MS-WS) 26 3.2.4 鄰居親代選擇機制 (MS-NB) 28 3.3 改進環境選擇機制 29 3.3.1 週期式決策空間叢集環境選擇機制 (ES-CL) 30 3.3.2 混合式決策空間擁擠距離環境選擇機制 (ES-CD) 32 3.3.3 混合式收斂取向環境選擇機制 (ES-GB) 33 3.4 演算法平行化機制 34 3.4.1 各種權重向量分配法 34 3.4.2 保留邊框之權重向量分配法 35 3.4.3 遷徙與取代 38 第四章 實驗與分析 39 4.1 測試問題 39 4.2 效能指標 39 4.3 參數設定 40 4.4 改進親代選擇機制 41 4.4.1 基於參考點的階層式親代選擇機制 41 4.4.2 強化劣勢參考點之親代選擇機制 43 4.4.3 鄰居親代選擇機制 45 4.4.4 融合式親代選擇機制 47 4.5 改進環境選擇機制 51 4.5.1 維持決策空間分散度之環境選擇機制 51 4.5.2 混合式收斂取向環境選擇機制 55 4.6 平行化機制 56 4.6.1 各子族群之權重向量分配法 56 4.6.2 搭配遷徙功能之平行化演算法 61 4.6.3 搭配改進親代選擇機制之平行化演算法 65 4.6.4 演算法平行化後的優勢與缺陷 67 第五章 總結與未來展望 73 參考文獻 75

    [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.

    下載圖示
    QR CODE