學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
6 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 以文化基因演算法求解大型多目標且具時窗限制之車輛路由問題(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 以限制多目標演化演算法求解具時窗限制之車輛路由問題(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做比較，並找到一個最適合此多目標最佳化問題的限制處理機制。最後本論文列出目前找到的多目標最佳解，以供之後做比較。