學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
10 results
Search Results
Item 求解高維多目標最佳化問題的演化演算法效能評析(2024) 曾則儒; Tseng, Tser-Ru演化演算法在求解多目標最佳化問題有很好的表現，也被廣泛使用於各領域的實際應用問題。然而當決策變數的個數增加至數百個甚至數千個時，指數成長的搜尋空間會對多目標演化演算法的求解能力形成嚴峻的挑戰；因此，近年來演化計算領域有越來越多的學者投入高維多目標演化演算法的設計。然而，我們發現到此領域的研究文獻在評估演算法效能時未能使用統一的實驗設定，此舉可能造成實驗結果的偏頗與失真。本論文自文獻中挑選八個具有代表性的高維多目標演化演算法，使用兩套公開測試函式集 LSMOP 與 LMF，檢視這些演算法在四種問題維度和四種計算資源所組合的十六種實驗環境下的求解效能。經由公平且完整的實驗測試，我們得以正確評比演算法的效能與特質，也對各種演算法設計的異同處與其對於求解效能的影響提出解釋與探討。Item 以 AGE-MOEA-II與改良版環境選擇求解多目標最佳化問題(2024) 張家慈; Chang, Chia-Tzu多目標最佳化問題是現實應用的常見形式，求解問題時需要同時考慮多個目標之間的取捨關係。多目標演化演算法是求解多目標最佳化問題的常用方法，這類演算法中的關鍵機制就是平衡解族群的收斂性和多樣性。在近年發表的演算法中，AGE-MOEA-II 演算法通過估計柏拉圖前緣的形狀，並依形狀來定義解的多樣性和收斂性，展現了出色的效能表現。然而AGE-MOEA-II 仍有其值得改進之處，本論文結合了其它現有演算法的設計，一方面刪減無益於收斂性的解個體，一方面修改其應對凸型柏拉圖前緣時的多樣性評估機制。我們使用 13 個公開測試函式進行實驗，實驗結果顯示本論文所引入的機制可有效提升求解品質；與六個現有演算法相比，本論文所提出的改良版 AGE-MOEA-II 在兩項常見的效能指標 IGD 與 HV 都有更好的表現。Item 以多目標與限制最佳化觀點求解非固定主場運動排程問題：以中華職棒大聯盟為例(2019) 陳重堯; Chen, Chung-Yao在國內外職業運動賽事中，每年都需要為比賽排出新的賽程。而賽程的安排會間接影響到進場的觀眾人數、廣告的安排、贊助商的贊助、球員的實力發揮以及休息時間；賽程的安排不當將導致職業賽事聯盟的收益降低。賽程的安排需考量隊伍的移動距離、對戰組合的話題性及公平性，所以賽程的安排是一件極為複雜的事情，運動排程也被認為是高度複雜的組合問題。在2013年，石大維的碩士論文將競賽旅程問題的單目標最佳化問題，發展為多目標最佳化問題。本論文為了更貼近真實情形，以中華職棒季賽賽程去探討最佳化旅行總距離和最長旅行距離的多目標最佳化問題。 本論文提出群體式彈性機率鄰域模擬退火法，使用彈性機率鄰域的選取方法去和隨機機率鄰域函式作比較，並且修改了群體式模擬退火法的流程，讓本論文的方法可以在一定的搜尋次數內，找到多目標最佳解。最後本論文也列出找到的多目標最佳解，並和真實的賽程去做比較，也提供決策者作參考。Item 電力調度之成本與汙染最佳化問題：模型、演算法與效能(2019) 許芳齊; Hsu, Fang-Chi本論文探討電力調度之成本與汙染最佳化問題 (Economic and Emission Dispatch, EED ) 是一個重要的多目標優化議題，由於火力發電廠在產生電能時將會排放出對環境有害的物質，使得排放調度在電力系統中佔有重要的角色。 近年來已經有許多篇解決 EED 問題的論文被提出，然而此領域的學者所使用的實驗測試資料或目標公式眾說紛紜，因此各篇文獻的結果評比會有不公平的隱憂存在，因此本論文將統整63篇年代約2003年至2017年的EED 論文，驗證其結果的正確性，提出問題模型與實驗測試資料，統整出各模型實例下已知最佳解，提供後續 EED 研究者有更好的參考方向與評估數據。探討各篇文獻在生產電能時的發電機組限制與電量守恆限制的處理方法，討論各篇演算法對於求解成本與汙染氣體排放量這兩個衝突目標的處理機制。 利用差分演化演算法搭配多目標演算法 NSGA-II 求解各問題模型的 EED問題，在實驗中利用效能指標 IGD 評估各種問題限制修復機制的優劣，試著找出最佳限制處理方法。其次也利用差分演化演算法搭配參數控制求解 EED 問題的最佳前緣，與統整的各模型實例下已知最佳解做比較。Item 以文化基因演算法求解大型多目標且具時窗限制之車輛路由問題(2014) 王維新; Wei-Hsin Wang具時間窗車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW) 為車輛路由問題(Vehicle Routing Problem)再加上時間窗限制，而車輛路由問題係為一個派車站派出多輛車輛服務顧客點，在生活實務上已經有相當廣泛的運用，包括宅配、垃圾回收車路線規劃、銀行運鈔車及定點巡邏車路線規劃。 本論文以具時窗限制之車輛路由問題為主題，其求解目標為最小化車輛數和總行駛距離，由柏拉圖最佳化觀點求解，提出文化基因演算法的求解方法。此文化基因演算法採用共生關係，即為允許違反限制解存在於族群中，初始解產生時會產生合法解與違反限制解，再由基因演算法以多目標進行最佳化。基因演算法產生交配產生的子代會使用突變策略進行修復與改善，接著區域搜尋法對產生的子代進行目標的最佳化或是對族群的多樣性加以擾動，藉此產生的子代會依一定比例讓違反限制解存活於族群中。 測試問題集是以Gehring與Homberger (1999)建立的200個顧客點大型問題集，問題集中有6大類共56個問題。本研究以多目標求解問題的過程中，探討不可行解存在於族群中對於文化基因演算法中族群演化造成的影響。Item 以變化分配島嶼式MOEA/D求解多目標問題(2013) 李鼎基在日常生活中，我們時常面臨最佳化問題，例如最小化交通的時間與成本，這兩項目標存在著衝突，此類問題稱為多目標最佳化問題，因應每人需求不同，會有不同的最佳解。一般解多目標最佳化問題是找出一組最佳解集合，集合中會有不同的目標取捨方式供使用者挑選，然而解決此類問題是相當耗時的，為了在有效時間內找出不錯的解，使用演化式演算法是廣受好評的方式。 演化式演算法本身存在著許多可切割平行的要素，因此許多平行架構的演化式演算法因應而生，本論文嘗試將知名的多目標演化式演算法 MOEA/D 進行平行化，除了基本的平行要素外，尚有其他因平行化被破壞的 MOEA/D 之要素需要修補。本論文針對17個多目標最佳化問題進行測試，並慢慢調整島嶼式 MOEA/D，一一討論各要素之影響，最後與 MOEA/D 進行比較成效與差異性，並且運用 OpenMP 進行平行加速。Item 以混合演化式演算法求解多目標且具時窗限制之車輛路由問題(2011) 許巍懷車輛路由問題旨在尋求車輛與客戶之間最佳分配與移動路線，在已知客戶需求 (如運送量和服務時窗限制) 和車輛容量的情況下，由派車站發車前往服務客戶，最後返回派車站。車輛路由問題在實務上已有廣泛應用，如物品宅配、校車動線、計程車載客、銀行運鈔車補給、郵務信件遞送等等。 本論文以具時窗限制之車輛路由問題為主題，其求解目標為最小化車輛數和總行駛距離，由柏拉圖最佳化觀點求解，提出一混合基因演算法和禁忌搜尋的求解方法。初始解經由禁忌搜尋將目標專於車輛數目最小化，再由基因演算法以多目標進行最佳化。並以改良式的交配和突變策略增加解的品質；在演化一定代數後由禁忌搜尋法對族群中非凌越解集進行深度搜尋以最小化行駛距離。 測試問題集是Solomon建立的6大類共56個問題。本研究以多目標求解問題，對於文獻所提出的67個近似最佳解集合更新了34個，另外有2大類的問題可以達到車輛數與總距離的最佳解。Item 以限制多目標演化演算法求解具時窗限制之車輛路由問題(2013) 翁仁一; Ren-Yi Wong「時窗限制車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW)」在原有的車輛路由問題 (Vehicle Routing Problem, VRP) 上增添時間的限制，增加了題目的難度，但也更符合現實生活中的需求。此問題的研究已有20多年歷史。過去的精確演算法對於如此困難的問題，往往不能求解規模龐大的輸入。近年許多研究偏好採用多目標最佳化的方式解決，但因此問題的時窗限制較難修復，較少人會提及不合法解的處理。 本研究修改自現有的MOEA-EO [14]。在交換最佳的路由時，總是選擇客戶數目最多的，以祈刪除最多的客戶以減少路由數目。在限制處理上，環境的選擇會依據解的合法性，使用不同的凌越關係來分級。合法的解會使用傳統的解題目標來分級，不合法的解會使用限制的違反量來分級。最後會以交互的方式篩選出可以存活到下一代的個體，適當保留不合法的個體以增加搜尋的廣度。 本演算法對於客戶數目較少的問題已有不錯的表現。在Solomon 25個客戶的問題中，更新了9個最佳解。Item 以多目標與限制最佳化觀點求解競賽旅程問題(2013) 石大維運動時間表問題 (Sport Timetabling Problem) 一直以來都是一個相當困難的問題，其影響的因素五花八門，像是運動員的需求、場館間的距離、商業和廣告的考量等等。其中針對球隊旅行產生了競賽旅程問題 (Traveling Tournament Problem)，本論文針對這樣的問題做研究。該問題原本為一個單目標最佳化問題，本論文將此問題發展為多目標最佳化問題，藉由此方式讓使用者能夠有多元的選擇，例如選擇一個總距離並非最短，但是能讓所有的隊伍移動距離較為平均的解。 本論文提出群體式多鄰域模擬退火法 (Population-based Multi Neighborhood Simulated Annealing, PMNSA) ，其中使用變動鄰域搜尋法 (Variable Neighborhood Search) 與隨機選擇鄰域函式做比較，希望能找到一種效能較好的做法，接著使用模擬退火法 (Simulated Annealing) 以及群體式的 (population-based) 概念去搜尋，另外也改良過去競賽旅程問題所使用的鄰域函式，並比較其改良前後搜尋解空間的能力，藉由此方式提高搜尋的效能。在限制處理機制的部分採用原先單目標常用的懲罰函數 (penalty function) 以及ϵ-constraint做比較，並找到一個最適合此多目標最佳化問題的限制處理機制。最後本論文列出目前找到的多目標最佳解，以供之後做比較。Item 應用適應性多目標差分演化演算法求解電力調度之成本與污染最佳化問題(2018) 林中儀; Lin, Zhong-Yi生活在21世紀的人類生活已經不能沒有電力，而目前的台灣也飽受空氣汙染的影響，電力調度之成本與污染最佳化問題探討的是如何分配機組的發電量以達到用最少成本與最低的汙染氣體排放量來提供所需之電力，在綠能還不穩定且核能無法得到共識的現在，火力發電為主流的國家都會面臨這個問題。 本研究利用差分演化演算法搭配多目標框架MOEA/D嘗試解決這個問題，在所做的實驗中探討各種參數與策略的效果，試著找出最佳的設定。既有論文在比較其提出方法之優劣時多半未採用多目標演算法領域常用的指標，本研究會利用多目標演算法常用的效能指標來評估好壞並且釋出完整的求解資料以供後面的研究者可以進行比較。