跳到主要內容

臺灣博碩士論文加值系統

(44.211.24.175) 您好!臺灣時間:2024/11/05 06:08
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:廖大發
研究生(外文):Ta-Fa Liao
論文名稱:多目標最佳化方法之研究
論文名稱(外文):On the Study of Multi-objective Optimization Using Evolutionary Computation
指導教授:陳善泰
學位類別:碩士
校院名稱:國防大學中正理工學院
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:67
中文關鍵詞:多目標問題非劣解演化式演算法寬鬆非劣解
外文關鍵詞:Multi-objective Optimization ProblemPareto SolutionEvolutionary AlgorithmRelaxed Pareto
相關次數:
  • 被引用被引用:1
  • 點閱點閱:2467
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
多目標最佳化方法的應用範圍十分地廣泛,舉凡工程、經濟、數學、甚至軍事作戰等不同的領域,都有實際有效的應用。目前用來處理多目標最佳化問題(MOP, Multi-objective Optimization Problem)的方法大致可分為三種:最常使用的方式是將多目標問題轉換為單一目標最佳化問題再求解;第二種是賦予各子目標不同的求解順序,並依照此優先順序循序求解;最後一種則是把所有的子目標同時列為目標函數,在考量各子目標之間不受支配(Non-dominated)的關係下找出所有的非劣解(Pareto Solutions)。
由於多目標之間佊此有相互衝突關係,求取最佳解的搜尋時間通常成指數成長。因此,在各種多目標規劃法的應用中,如何有效率的求得一個夠好的解或接近最佳解(Near Optimal Solution)是很重要的。因此,最近許多隨機搜尋(Stochastic Search)的策略被提出,其中演化式演算法(Evolutionary Algorithm),因為其對於複雜且非線性的問題具有高效率的全域搜尋能力,被證明很適合用來處理這些複雜且難纏的問題。
本論文提出寬鬆非劣解(Relaxed Pareto)的概念,進而發展出寬鬆非劣解基因演算法(Relaxed Pareto Genetic Algorithm, RPGA),來改善多目標演化式演算法效能。本論文亦將RPGA應用於射擊流路排程、多目標資源分配兩個最佳化問題,並與Lingo軟體、聚合法(Aggregation)與傳統的非劣解(Pareto)等演算法做比較。經實驗結果證明,本論文所提出的RPGA演算法可以有效的用來解決排程與資源分配等多目標之組合最佳化(Combinatorial Optimization) 問題。
Algorithms for multi-objective optimization problems (MOP) can be applied to many domains, such as engineering, economics, mathematics, and military operations. There are three main approaches for solving multi-objective optimization problems. The first approach is to transform the problems into single-objective ones. This is typically done by assigning a numerical weight to each objective and then combining the values of the weighted criteria into a single value. The second approach assigns different priorities to different objectives, and then optimizing the objectives in their order of priority. The third, the Pareto approach, uses a non-dominated concept to obtain solutions which are Pareto optimal.
Due to the conflict among objectives, it is computationally expensive to generate the “best” solutions for a given multi-objective problem. Instead of finding optimal solutions, how to obtain good solutions in reasonable time is a critical issue. A number of stochastic search strategies, such as evolutionary algorithms (EAs), have been developed in the last two decades. EAs are efficient optimizers with the ability to explore complex nonlinear search spaces and have been shown to be effective for NP-hard problems.
Taking advantage of EAs, in this paper we propose a concept of relaxed Pareto, and develop the relaxed Pareto genetic algorithm (RPGA) for multi-objective optimization problems. Furthermore, RPGA has been successfully applied to solve resource allocation and scheduling problems. Compared to the Pareto, aggregation approaches, and branch-and-bound algorithms performed by Lingo, experimental results show that RPGA is able to efficiently obtain high-quality solutions.
誌謝 ii
摘要 iii
ABSTRACT iv
表目錄 vii
圖目錄 viii
1. 緒論 1
1.1 研究動機 1
1.2 研究目的 3
2. 問題定義 5
2.1 決策空間與目標空間 6
2.2 非劣解概念與定義 7
2.3 多目標問題最佳解 9
3. 多目標數學規劃法 10
3.1 無偏好多目標規劃法 11
3.1.1 權重法(Weighting Method) 11
3.1.2 -限制法(-Constraint Method) 12
3.1.3 非劣解估計法(NISE, The Non-Inferior Set Estimation Method) 13
3.1.4 多目標單形法(MS, Multi-Objective Simplex Method) 15
3.2 有偏好多目標規劃法 15
3.2.1 目標規劃(Goal Programming) 15
3.2.2 妥協規劃法(Compromise Programming Method) 17
3.2.3 效用函數法(UF, Utility Function) 18
3.3 互動多目標規劃法 19
3.3.1 逐步法(The Step Method) 19
3.3.2 互動柴比雪夫法(The Interactive Weighted Tchebycheff Method) 20
4. 多目標演化式演算法 23
4.1 聚合法(Aggregation-based Approach) 24
4.2 優先順序法(Criterion-based Approach) 26
4.3 非劣解法(Non-dominated Approach) 26
4.4 寬鬆非劣解基因演算法(RPGA, Relaxed Pareto Genetic Algorithm) 29
4.4.1 適應值計算 33
4.4.2 目標值估算 35
4.4.3 選擇(Selection) 35
4.4.4 交配(Crossover) 37
4.4.5 突變(Mutation) 37
4.4.6 寬鬆非劣解集合(Relaxed Pareto Pool) 38
5. 實驗結果 41
5.1 多目標資源分配問題 41
5.2 多目標資源分配問題與最佳解實驗結果比較 45
5.3 部隊射擊訓練流路排定問題 51
5.4 SLFT實驗結果 58
6. 結論 62
參考文獻 63
自傳 67
[1] 陳善泰、廖大發,“改良式多目標最佳化演算法-個人化排課問題之研究”,第十屆人工智慧與應用研討會論文集,高雄,2005。
[2] 廖大發、陳善泰、唐啟儀,“多目標最佳化演算法應用於射擊流路排定之研究”,第十四屆國防科技研討會論文集,桃園,2005。
[3] 許志義,多目標決策,五南圖書出版公司,台北,第3-122頁,2003。
[4]Thomas, H., “Global Multiobjective Optimization Using Evolutionary Algorithms,” Journal of Heuristics, Vol. 6, 2000, pp. 347-360.
[5] Osman, M. S., Abo-Sinna, M. A., and Mousa, A. A.,” An Effective Genetic Algorithm Approach to Multiobjective Resource Allocation Problems (MORAPs),” Applied Mathematics and Computation, vol. 163, pp. 755-768, 2005.
[6] Hsiao, Y. T., Chuang, C. L., and Jiang, J. A. “A Hybrid of ε-Constraint and Particle Swarm Optimization for Designing of PID Controllers,” IEEE International Conference on Systems, Man and Cybernetics, vol. 4, pp. 3063-3070, 2005.
[7] Celli, G., Ghiani, E., Mocci, S., and Pilo, F., “A Multiobjective Evolutionary Algorithm for the Sizing and Siting of Distributed Generation,” IEEE Transactions on Power Systems, vol. 20, no.2, pp. 750-757, 2005.
[8] Das, D.B., and Patvardhan, C., “A New Approach for Security Constrained Economic Emission Dispatch in Power Systems,” IEEE Region 10 International Conference on Global Connectivity in Energy, Computer, Communication and Control, vol. 2, pp. 470-473, 1998.
[9] Lins, M. E., Angulo-Meza, L., and Silva A. M., "A Multi-Objective Approach to Determine Alternative Targets in Data Envelopment Analysis," Journal of the Operational Research Society, vol. 55, pp. 1090-1101, 2004.
[10] Jaam, J. M., Rebaiaia, M. L., and Hasnah, A. M., "Modelling the Timetabling Problem Using Goal Programming," Journal of Computer Science, pp. 64-71, 2005.
[11] Latinopoulos, D., and Mylopoulos, Y., "Optimal Allocation of Land and Water Resources in Irrigated Agriculture by Means of Goal Programming: Application in Loudias river basin," Global NEST Journal, Vol. 7, No 3, pp 264-273, 2005.
[12] Chen. W., Wiecek, M. and Zhang, j., "Quality Utility: A Compromise Programming Approach to Robust Design," ASME Journal of Mechanical Design, vol. 2, no 121, pp. 179-187, 1999.
[13] Parra, M. A., Terol, A. B., Gladish, B. P. and Rodriguez, M.V., "Solving a Multiobjective Possibilistic Problem Through Compromise Programming," European Journal of Operational Research, vol. 164, pp. 748–759, 2005.
[14] Karkkainen, A. S., Miettinen, K., and Vuori, J., "Best Compromise Solution For a New Multiobjective Scheduling Problem," Computers & Operations Research, vol. 33, pp. 2353–2368, 2006.
[15] Zienkiewicz, O. C., Operation Research, Thomson books/cole, Belmont, pp. 776-778, 2004.
[16]Bhagwan, D. D., and Patvardhan, C., “Useful Multi-Objective Hybrid Evolutionary Approach to Optimal Power Flow,” IEE Proceedings on Generation, Transmission and Distribution, vol. 150, pp.275-282, 2003.
[17]Hong, Y. Y., and Ho, S. Y,. “Determination of Network Configuration Considering Multiobjective in Distribution Systems Using Genetic Algorithms,” IEEE Transactions on Power Systems, vol. 20, no. 2, pp. 1069-1069, 2005.
[18]Balasubramaniam, N., Sanjoy, D., and Daniel, S., “An Evolutionary Approach to Designing Complex Spreading Codes for DS-CDMA,” IEEE Transactions on wireless communications, vol. 4, no. 5, pp. 2051-2066, September 2005.
[19]Neelakantam V. V., Tapabrata, R., and Gan Y. B.,“Multilayer Dielectric Filter Design Using a Multiobjective Evolutionary Algorithm,” IEEE Transactions on antennas and propagation, vol. 53, no. 11, pp. 3625-3632, 2005.
[20]Shin, S. Y., Lee, I. H., Kim, D., and Zhang, B. T., “Multiobjective Evolutionary Optimization of DNA Sequences for Reliable DNA Computing,” IEEE Transactions on evolutionary computation, vol. 9, no. 2, pp. 143-158, APRIL 2005.
[21]Kuwahara, Y., “Multiobjective Optimization Design of Yagi–Uda Antenna,” IEEE Transactions on antennas and propagation, vol. 53, no. 6, pp. 1984-1992, 2005.
[22]Thomas, H., and Stefan, N., “A Multiobjective Evolutionary Algorithm for Scheduling and Inspection Planning in Software Development Projects,” European Journal of Operational Research, vol. 167, pp. 663–678, 2005.
[23]Gen, M., Kumar, A., and Kim, J. R., “Recent Network Design Techniques Using Evolutionary Algorithms,” International Journal of Production Economics, vol. 98, pp. 251–261, 2005.
[24] Abido, M. A., and Bakhashwain, J. M., “A novel Multiobjective Evolutionary Algorithm for Optimal Reactive Power Dispatch Problem,” 10th IEEE International Conference on Electronics, Circuits, and Systems, Sharjah, United Arab Emirates, pp. 1054-1057, December 14–17, 2003.
[25]Eckart, Z., Marco, L. and Stefan, B., “A Tutorial on Evolutionary Multiobjective Optimization,” Meta heuristics for Multiobjective Optimization, Springer-Verlag, Berlin, Germany, pp. 3-38, 2004.
[26]Eckart, Z., Marco, L., and Lothar, T., “SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization,” International Center for Numerical Methods in Engineering, Barcelona, Spain, pp. 95-100, 2002.
[27]David W. C., Knowles, J. D., and Oates, M. J., "The Pareto Envelope-based Selection Algorithm for Multiobjective Optimization," Proceedings of the Parallel Problem Solving from Nature VI Conference, Springer, Paris, France, pp. 839-848, 2000.
[28]Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., "A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II," IEEE Transaction on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
[29]Knowles J. D. and Corne D. W., “the Pareto archived evolution strategy: A New Baseline Algorithm for Pareto Multiobjective Optimisation,” In Congress on Evolutionary Computation, vol. 1, Washington, D.C., pp. 98-105, July, 1999.
[30] Ricardo S. M., Sancho S. S., Mario D. C., Carlos B. C., “A Two-phase Heuristic Evolutionary Algorithm for Personalizing Course Timetables: A Case Study in A Spanish University,” Computers & Operations Research, Vol. 32, pp. 1761–1776, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top