臺灣博碩士論文加值系統

進化多目標優化 (Evolutionary multi-objective optimization)在許多條件互相衝突的問題上佔有一席之地，因為此優化方法能找到一組接近帕雷托最優前沿 (Pareto optimal front)的非支配解 (nondominated solutions)。但在最後的選擇演算法執行之前，這組非支配解的數量可能很多甚至接近無限，這些不分上下的非支配解到底要如何決定誰去誰留？那就是進一步從中選出最具有代表性的解。最終的解之間的差異性越大才越有參考價值。

本研究係從最後候補的非支配解中選出正式非支配解(在NSGA-II的模式是先把親與子兩代合起來後，再利用此演算法從中選出新一代作為最新的演算因子)的演算法做優化，我們希望以時間換取精確度，根據候補解需求數量把整條分布於帕雷托前沿的候補解形成的曲線平均分割成數等分，找到最接近平均分割線上的候補解並予以保留。我們的演算法是以接續在別人的多目標優化演算法之後的形式來作用，首先以NSGA-II的快速非支配排序來判斷解的好壞，因為首先要找到盡量接近於帕雷托最優前沿的候補解，再針對這些候補解作選別。

Evolutionary multi-objective optimization (EMO) plays a leading role in solving many problems with multiple conflicting objectives due to their ability to find a set of nondominated solutions near the Pareto optimal front. But before applying a selection algorithm, the size of this nondominated solution set might be big or even unlimited. Then how shall we choose from this set of solutions nondominated to each other? We go further and choose solutions that are more unique. The more diverse the final solutions are, the better these solutions are for reference.

This paper aims to optimize the step for selecting final solutions from the candidate nondominated solutions set or the step where NSGA-II combines the parent and child population set and makes a new generation from half of them. We hope to achieve higher precision with more computation time. By knowing the number of final solutions needed, we divide the whole nondominated front into equal parts, and we select solutions closest to the boundary line. Our algorithm works by appending it to other multiobjective optimization algorithms, we also uses the fast non-dominated sorting from NSGA-II to sort out the solutions because finding solutions near the pareto optimal front is our first priority, then we apply our selection algorithm.

選擇帕雷托最優解的平均分布演算法 II
摘要 I
Abstract II
目錄 III
圖目錄 V
表目錄 VI
第一章 1
緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 論文架構 4
第二章 5
相關研究 5
2.1 NSGA-II 5
2.2 MTS 7
第三章 8
系統架構 8
3.1系統流程簡介 8
3.2 Equal Distribution Algorithm-Select_V1 8
3.4 Equal Distribution Algorithm-Select_V2 11
3.3 Equal Distribution Algorithm-Select_V3 12
3.5 Fast Nondominated Sorting 15
3.6 comparefunc 18
3.7 step1(sorting) 19
3.8 weight_count 21
3.9 step3(summing distances of adjacent solutions) 21
3.10 step4(calculate distance) 22
3.11 getHeadTailLength(storing head and tail solutions of all segments and their lengths) 22
3.12 fbs_distribute 27
3.13 step6_V1(selection) 30
3.14 step6_V2(selection) 33
3.15 step6_V3(selection) 36
3.16 diversity 40
第四章 42
4.1測試資料介紹與參數設定 42
4.2實驗結果 43
4.3實驗結果討論 70
第五章 71
結論 71
參考文獻 72

[1] Shirazi, Ali; Najafi, Behzad; Aminyavari, Mehdi; Rinaldi, Fabio; Taylor, Robert A. (2014-05-01). "Thermal–economic–environmental analysis and multi-objective optimization of an ice thermal energy storage system for gas turbine cycle inlet air cooling". Energy. 69: 212–226. doi:10.1016/j.energy.2014.02.071.
[2] Q. Zhang, H. Li, "MOEA/D: a multiobjective evolutionary algorithm based on decomposition", IEEE Trans. Evol., vol. 11, no. 6, pp. 712-731, 2007.
[3] Wikipedia Multi-objective optimization
https://en.wikipedia.org/wiki/Multi-objective_optimization
[4] Wikipedia Pareto efficiency
[5] Wikipedia Evolution algorithm
https://en.wikipedia.org/wiki/Evolutionary_algorithm
[6] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002.
[7] L. Y. Tseng, C. Chen, "Multiple trajectory search for unconstrained/constrained multi-objective optimization", Proceeding 2008 IEEE Congress on Evolutionary Computation, pp. 1951-1958, 2009.
[8] K. Sindhya, A. Sinha, K. Deb, K. Miettinen, "Local search based evolutionary Multiobjective optimization algorithm for constrained and unconstrained problems", IEEE Congress on Evolutionary Computing (CEC) 2009, 18–21 May, 2009.
[9] Deb K., Deb K. (2014) Multi-objective Optimization. In: Burke E., Kendall G. (eds) Search Methodologies. Springer, Boston, MA
[10] N. Srinivas and K. Deb, "Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms," in Evolutionary Computation, vol. 2, no. 3, pp. 221-248, Sept. 1994.
[11] Deb K. (2015) Multi-Objective Evolutionary Algorithms. In: Kacprzyk J., Pedrycz W. (eds) Springer Handbook of Computational Intelligence. Springer Handbooks. Springer, Berlin, Heidelberg
[12] Wikipedia Pearson correlation coefficient
[13] Chih-Ming Chen, Ying-ping Chen and Qingfu Zhang, "Enhancing MOEA/D with guided mutation and priority update for multi-objective optimization," 2009 IEEE Congress on Evolutionary Computation, Trondheim, 2009, pp. 209-216.
[14] J. Knowles and D. Corne, “The Pareto archived evolution strategy: A new baseline algorithm for multiobjective optimization,” in Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 1999, pp. 98–105.
[15] E. Zitzler, “Evolutionary algorithms for multiobjective optimization: Methods and applications,” Doctoral dissertation ETH 13398, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, 1999.
[16] D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Wesley, 1989.
[17] Jhih-Sian Wu (2010), “Using Multiple Trajectory Search Algorithm to Solve the Quadratic Assignment Problem”, National Chung-Hsing University, Department of Computer Science and Engineering Master’s thesis, Taichun city https://hdl.handle.net/11296/h7t94g
[18] Q. Zhang, A. Zhou, S. Zhao, P. N. Suganthan, W. Liu, and S. Tiwari, “Multiobjective optimization test Instances for the CEC 2009 special session and competition,” Technical Report CES-487, University of Essex and Nanyang Technological University, September. Available: http://www.ntu.edu.sg/home/EPNSugan/
[19] Q. Zhang, and P. N. Suganthan, “Final Report on CEC’09 MOEA Competition,” , University of Essex and Nanyang Technological University, 2009. Available: https://dces.essex.ac.uk/staff/qzhang/MOEAcompetition/cecmoeafinalreport.pdf