簡易檢索 / 詳目顯示

研究生: 李鼎基
論文名稱: 以變化分配島嶼式MOEA/D求解多目標問題
Multiobjective Optimization using Island-Based MOEA/D with Changing Distribution
指導教授: 蔣宗哲
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2013
畢業學年度: 101
語文別: 中文
論文頁數: 66
中文關鍵詞: 多目標最佳化演化式演算法平行化OpenMP
論文種類: 學術論文
相關次數: 點閱:209下載:14
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在日常生活中,我們時常面臨最佳化問題,例如最小化交通的時間與成本,這兩項目標存在著衝突,此類問題稱為多目標最佳化問題,因應每人需求不同,會有不同的最佳解。一般解多目標最佳化問題是找出一組最佳解集合,集合中會有不同的目標取捨方式供使用者挑選,然而解決此類問題是相當耗時的,為了在有效時間內找出不錯的解,使用演化式演算法是廣受好評的方式。
    演化式演算法本身存在著許多可切割平行的要素,因此許多平行架構的演化式演算法因應而生,本論文嘗試將知名的多目標演化式演算法 MOEA/D 進行平行化,除了基本的平行要素外,尚有其他因平行化被破壞的 MOEA/D 之要素需要修補。本論文針對17個多目標最佳化問題進行測試,並慢慢調整島嶼式 MOEA/D,一一討論各要素之影響,最後與 MOEA/D 進行比較成效與差異性,並且運用 OpenMP 進行平行加速。

    中文摘要 i 誌謝 ii 目錄 iii 附表目錄 vi 附圖目錄 viii 第一章 緒論 1 1.1 研究動機 1 1.2 背景知識 1 1.2.1 多目標最佳化問題 1 1.2.2 演化式演算法 3 1.3 研究目的與方法 5 第二章 文獻探討 6 2.1 平行演化式演算法 6 2.2 平行多目標演化式演算法 8 2.3 平行演化式演算法之分配與遷徙策略 11 第三章 變化分配島嶼式 MOEA/D 演算法實現 18 3.1 MOEA/D基本流程 18 3.2 變化分配島嶼式 MOEA/D 21 3.2.1 族群分配與變化分配 21 3.2.2 變化子族群數量 24 3.2.3 遷徙 25 3.2.4 變化分配島嶼式 MOEA/D 流程 26 第四章 實驗數據與效能評比 33 4.1 測試問題 33 4.2 效能指標 40 4.3 測試環境與參數設定 41 4.4 實驗與討論 42 4.4.1 族群大小實驗 43 4.4.2 族群分配實驗 45 4.4.3 遷徙挑選與數量之實驗 47 4.4.4 遷徙頻率與拓撲之實驗 48 4.4.5 變化島嶼數量之實驗 51 4.4.6 變化分配島嶼之實驗 53 4.4.7 執行時間之實驗 58 第五章 結論與未來發展 62 參考文獻 64

    Affenzeller, M., & Anwagner, S. (2004). SASEGASA: A new generic parallel evolutionary algorithm for achieving highest quality results. Journal of Heuristics, 10(3), 243–267.
    Araujo, L., & Merelo, J.J. (2011). Diversity through multiculturality: Assessing migrant choice policies in an island model. IEEE Transactions on Evolutionary Computation, 15(4), 456–469.
    Arias Montaño, A., Coello Coello, C.A., & Mezura-Montes, E. (2010a). MODE-LD+SS: A novel differential evolution algorithm incorporating local dominance and scalar selection mechanisms for multi-objective optimization. In IEEE Congress on Evolutionary Computation (pp. 203–208).
    Arias Montaño, A., Coello Coello, C.A., & Mezura-Montes, E. (2010b). pMODE-LD+SS: An effective and efficient parallel differential evolution algorithm for multi-objective optimization. Lecture Notes in Computer Science, 6239, 21–30.
    Branke, J., Schmeck, H., Deb, K., & Reddy S., M. (2004). Parallelizing multiobjective evolutionary algorithms: cone separation. In IEEE Congress on Evolutionary Computation (pp. 1952–1957).
    Cantú-Paz, E. (1998). A survey of parallel genetic Algorithms. Calculateurs Paralleles, 10(2), 141–171.
    Chapman, D., Jost, G., & van der Pas, R. (2007). Using OpenMP: Portable Shared Memory Parallel Programming.
    de Toro Negro, F., Ortega, J., & Paechter, B. (2003). Parallel single front genetic algorithm: Performance analysis in a cluster system. In International Parallel and Distributed Processing Symposium.
    de Toro Negro, F., Ortega, J., Ros, E., Mota, S., Paechter, B., & Martín, J.M. (2004). PSFGA: Parallel processing and evolutionary computation for multiobjective optimisation. Parallel Computing, 30(5–6), 721–739.
    Deb, K., & Agrawal, R. B. (1995). Simulated binary crossover for continuous search space. Complex System, 9, 115–148.
    Deb, K., & Goyal, M. (1996). A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics, 26(4), 30–45.
    Deb, K., Pratap, A., Agarwal. S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
    Deb, K., Zope, P., & Jain, A. (2003). Distributed computing of pareto-optimal solutions with evolutionary algorithms. Lecture Notes in Computer Science, 2632, 534–549.
    Durillo, J.J., Zhang, Q., Nebro, A.J., & Alba, E. (2011). Distribution of computational effort in parallel MOEA/D. Lecture Notes in Computer Science, 6683, 488–502.
    Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.
    Horn, J., & Nafpliotis, N. (1993). Multiobjective optimization using the niched Pareto genetic algorithm. University Illinois at Urbana-Champain, Urbana, IL, IlliGAL Report 93005.
    Li, H., & Zhang, Q. (2009). Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation, 13(2), 284–302.
    Matsumoto, M., & Nishimura, T. (1998). Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 8(1), 3–30.
    Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Norwell, MA: Kluwer.
    Streichert, F., Ulmer, H., & Zell, A. (2005). Parallelization of multi-objective evolutionary algorithms using clustering algorithms. Lecture Notes in Computer Science, 3410, 92–107.
    Xiao, N., & Armstrong, M. P. (2003). A specialized island model and its application in multiobjective optimization. Lecture Notes in Computer Science, 2724, 1530–1540.
    Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731.
    Zhang, Q., Zhou, A., & Li, H. (2009). The performance of a new version of MOEA/D on CEC09 unconstrained mop test instances. In IEEE Congress on Evolutionary Computation (pp. 203–208).
    Zhang, Q., Zhou, A., Zhao, S., Suganthan, P. N., Liu, W., & Tiwari, S. (2008). Multiobjective 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).
    Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2), 173–195.
    Zitzler, E., Thiele, L., Laumanns, M., Fonseca C. M., & Fonseca, V. G. da (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2), 117–132.

    下載圖示
    QR CODE