以變化分配島嶼式MOEA/D求解多目標問題

Multiobjective Optimization using Island-Based MOEA/D with Changing Distribution

李鼎基

指導教授 ： 蔣宗哲

國立臺灣師範大學/理學院/資訊工程學系/碩士(2013年)

摘要

在日常生活中，我們時常面臨最佳化問題，例如最小化交通的時間與成本，這兩項目標存在著衝突，此類問題稱為多目標最佳化問題，因應每人需求不同，會有不同的最佳解。一般解多目標最佳化問題是找出一組最佳解集合，集合中會有不同的目標取捨方式供使用者挑選，然而解決此類問題是相當耗時的，為了在有效時間內找出不錯的解，使用演化式演算法是廣受好評的方式。
演化式演算法本身存在著許多可切割平行的要素，因此許多平行架構的演化式演算法因應而生，本論文嘗試將知名的多目標演化式演算法 MOEA/D 進行平行化，除了基本的平行要素外，尚有其他因平行化被破壞的 MOEA/D 之要素需要修補。本論文針對17個多目標最佳化問題進行測試，並慢慢調整島嶼式 MOEA/D，一一討論各要素之影響，最後與 MOEA/D 進行比較成效與差異性，並且運用 OpenMP 進行平行加速。

關鍵字

多目標最佳化 ； 演化式演算法 ； 平行化 ； 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).