研究生: |
賴永斌 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 |
論文種類: | 學術論文 |
相關次數: | 點閱:149 下載: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.
[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).