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