簡易檢索 / 詳目顯示

研究生: 賴永斌
Lai Yung-Pin
論文名稱: 以融合新式親代選擇機制之MOEA/D求解多目標最佳化問題
Multiobjective Optimization using MOEA/D with a New Mating Selection Mechanism
指導教授: 蔣宗哲
Chiang, Tsung-Che
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2010
畢業學年度: 98
語文別: 中文
論文頁數: 62
中文關鍵詞: 多目標最佳化問題新式親代選擇機制密集度評估機制收斂評估機制交配池選擇機制
英文關鍵詞: multiobjective optimization, mating selection, crowding distance, convergence, mating pool selection
論文種類: 學術論文
相關次數: 點閱:173下載:13
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本論文提出一個融入新式親代選擇機制的MOEA/D演算法,用來求解多目標最佳化問題,新式親代選擇機制由三個機制組成:密集度評估機制、收斂評估機制、交配池選擇機制,使用此機制來改良MOEA/D演算法,增進演化效能,使用密集度跟收斂評估機制來分配計算資源,使計算資源不致浪費在無謂的演化上,充分的利用計算資源來達到更有效的演化,使用交配池選擇機制來改變交配池成員,原本MOEA/D演算法的設計是選擇固定成員當成交配池,而有少許機會可以選擇整個族群當成交配池,或許由固定成員進行交配在某些問題上很難逼近Pareto Front,所以我們使用交配池選擇機制來改變交配池成員,由此本論文提出一個新式親代選擇機制架構在MOEA/D演算法中,由實驗結果得知,此機制對於複雜的多目標最佳化問題可以得到很好的效能。

    This thesis presents the multiobjective optimization using MOEA/D with a new mating selection mechanism to solve multiobjective problems. The MOEA/D algorithm often selects fixed members as the mating pool. The probability for a whole population can be selected as the mating pool is low. Select fixed members to make offspring may difficult to approach Pareto Front in some problems. And the MOEA/D algorithm allocates computing resources equally. It may waste computing resources in useless evolution. Thus, this thesis presents a new mating selection mechanism in the MOEA/D algorithm to solve multiobjective problems. The new mating selection mechanism includes three mechanisms: the crowding distance mechanism, the convergence mechanism, and the mating pool selection mechanism. We use the new mating selection mechanism to improve MOEA/D’s efficacy. This thesis uses the crowding distance mechanism and the convergence mechanism to allocate computing resources, which can avoid wasting computing resources in useless evolution. This strategy makes full use of computing resources in effective evolution. We use the mating pool selection mechanism to change the mating pool members. Experimental results show that the new mechanism has good performance in these problems.

    中文摘要 II Abstract III 目錄 IV 附圖目錄 VI 附表目錄 VIII 第一章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的、方法與貢獻 3 1.3全文架構 5 第二章 文獻探討 6 2.1 演化式演算法 6 2.2 多目標演化式演算法 10 2.2.1凌越關係類別 11 2.2.2 效能指標類別 16 2.2.3權重法類別 18 第三章 融入新式親代選擇機制之MOEA/D演算法實現 23 3.1 MOEA/D基本流程 23 3.2染色體編碼與子代生成 26 3.3 新式親代選擇機制 28 3.3.1 密集度評估機制 28 3.3.2 收斂評估機制 30 3.3.3交配池選擇機制 32 3.3.4 新式親代選擇機制 33 第四章 實驗數據與效能評比 36 4.1 多目標最佳化問題 36 4.2 效能評比 41 4.3 測試環境與參數設定 43 4.4 實驗數據 46 4.5 討論 56 第五章 結論與未來發展 59 參考文獻 60

    [1] Beume, N., Naujoks, B., Emmerich, M. (2007). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181 (3), 1653–1669.
    [2] Gepperth, A., and Roth, S. (2006). Applications of multi-objective structure optimization. Neurocomputing, 69 (7–9), 701–713.
    [3] Reddy, J. M., and Kumar, N. D. (2007). Multiobjective Differential Evolution with Application to Reservoir System Optimization. Computing in Civil Engineering, 21 (2), 136-146.
    [4] Kacem, I., Hammadi, S., and Borne, P. (2002). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C 32 (1), 1–13.
    [5] Veldhuizen, D. A. V., and Lamont, G. B. (2000). Multiobjective evolutionary algorithms: Analyzing the state-of-the-art. Evolutionary Computation, 8 (2), 125-147.
    [6] Zhang, Q. and Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transation on Evolutionary Computation, 11 (6), 712-731.
    [7] Zitzler, E., Deb, K., and Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8 (2),173–195.
    [8] Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. (2002). Scalable multi-objectiveoptimization test problems. in Congress on Evolutionary Computation (CEC’2002) , 1, 825–830.
    [9] Fang, K. T., and Ma, C. X. (2001). Orthogonal and Uniform Design. Science Press, Beijing, China (in Chinese).
    [10] Deb, K., Agrawal, S., Pratap, A., and Meyarivan T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transation on Evolutionary Computation, 6 (2), 182–197.
    [11] Zitzler, E., Künzli, S. (2004). Indicator-based selection in multiobjective search. Parallel Problem Solving from Nature (PPSN VIII), 832–842.
    [12] Zitzler, E., Thiele, L., Laumanns, M., Fonseca C. M. and Fonseca, V. G. da (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transation on Evolutionary Computation, 7 (2), 117–132.
    [13] Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Inc., Reading, Massachusetts.
    [14] Horn, J., and Nafpliotis, N. (1993). Multiobjective Optimization using the Niched Pareto Genetic Algorithm. University Illinois at Urbana-Champain, Urbana, IL, IlliGAL Report 93005.
    [15] Deb, K., and Agrawal, R. B. (1995). Simulated binary crossover for continuous search space. Complex System, 9, 115–148.
    [16] Price, K., Storn, R. M., and Lampinen, J. A. (2005). Differential Evolution: A Practical Approach to Global Optimization. (Natural Computing Series) Springer-Verlag New York, Inc., Secaucus, NJ.
    [17] Deb, K., and Goyal, M. (1996). A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics, 26 (4), 30–45.
    [18] Glover, F. (1989). Tabu Search - Part I. ORSA Journal on Computing, 1(3), 190-206.
    [19] Srinivas, N., and Deb, K. (1994). Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 2(3), 221–248.
    [20] Zitzler, E., and Thiele, L. (1999). Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Transation on Evolutionary Computation, 3 (4), 257–271.
    [21] Zitzler, E., Laumanns M., and Thiele, L. (2002). SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, 95–100.
    [22] Kim, M., Hiroyasu, T., and Miki, M. (2004). SPEA2+: Improving the Performance of the Strength Pareto Evolutionary Algorithm2. Parallel Problem Solving from Nature - PPSN VIII, 742-751.
    [23] Knowles, J. D., Corne, D. W. (2000). Approximating the nondominated front using the Pareto Archived Evolution Strategy. Evolutionary Computation, 8(2), 149-172.
    [24] Li, H., and Zhang, Q. (2009). Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Transation on Evolutionary Computation, 13 (2), 284-302.
    [25] Zitzler, E., Thiele, L., and Bader, J. (2008). SPAM: Set preference algorithm for multiobjective optimization. Parallel Problem Solving from Nature (PPSN X), 847–858.
    [26] Ishibuchi, H., Yoshida, T. and Murata T. (2003). Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transation on Evolutionary Computation, 7 (2), 204–223.
    [27] Chang, P. C., Chen, S. H., Liu C. H. (2007). Sub-population genetic algorithm with mining gene structures for multi-objective flow shop scheduling problems. Expert Systems with Applications, 33 (3),762–771.
    [28] Chang, P. C., Chen, S. H. (2009). The development of a sub-population genetic algorithm II (SPGAII) for the Multi-objective combinatorial problems, Applied Soft Computing Journal, 9 (1), 173–181.
    [29] Zhang, Q., Zhou, A., Zhao, S., Suganthan, P. N., Liu, W., and Tiwari, S. (2008). Mmultiobjective optimization test instances for the CEC 2009 sepcial session and competition. The Shool of Computer Science and Electronic Engineering, University of Essex (Technical Report CES-487).

    下載圖示
    QR CODE