學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
5 results
Search Results
Item 參數調整機制於多目標演化式演算法之效能剖析(2012) 林裕傑在現實生活中，我們常常需要解決一些具有多個目標需要考量的問題，並且這些目標通常是互相衝突的，這些問題稱為多目標問題，而多目標最佳化問題的目標便是找出能最佳化這些目標的解集合。演化式演算法 (evolutionary algorithm) 是求解這類問題的常見演算法，其概念為利用族群演化的方式來尋找最佳解集合。MOEA/D 為其中一種知名的演算法，利用將多目標問題拆成單目標來求解的作法可以獲得良好的結果，而 MOEA/D-AMS 與 MOEA/D-APC 便是以該演算法為基礎所改良，其中 MOEA/D-APC 參考了差分演化 (differential evolution) 產生子代的作法，該演算法擁有兩個控制參數 F 與 CR，這兩個參數值是影響子代品質的關鍵，因此 MOEA/D-APC 加入了讓參數隨演化過程調整的機制，經過實驗證明效能有所改善，但仍然在少部分問題上輸給其他的DE演算法。 本論文挑出八個具有不同參數調整機制的DE演算法，利用 MOEA/D-AMS為主體分別結合這八種演算法與 MOEA/D-APC 的參數調整機制，藉由對17個測試問題進行實驗與分析，討論不同調整機制對效能的影響，並將主要目標放在探討 MOEA/D-APC 的弱項及改進方案上。Item 具適應性參數調整機制之多目標演化式演算法(2011) 陳政南; Chen Cheng-Nan現實生活中的決策問題如投資股票時需要考慮多個目標 (風險和收益)，而這些目標通常是互相衝突的，多目標最佳化問題就是要找出同時最佳化這些目標的解集合。求解多目標問題相當困難且耗費時間，而演化式演算法 (evolutionary algorithm) 利用族群演化的特性能在單一回合就能找出近似最佳解集合，因此非常適合求解多目標問題。現今已有非常多成功的應用，但為了在求解各種不同問題時都能有良好的效能，通常需要對演算法參數進行調校，如何減少使用者調校參數的負擔，是一個十分重要的課題。 本論文針對MOEA/D-AMS 演算法中的重要參數進行動態調整，差分演化算子(differential evolution operator)的控制參數 F 和 CR 會影響子代和親代的距離和方向，本論文所使用的方法是收集演化過程中成功產生優於親代的子代所使用的參數組合，基於這些參數組合來調整往後演化所使用的參數，目的是希望讓演算法在面對不同問題的狀態時，都依然能有良好的機率產生優於親代的子代，最後實驗結果會針對演算法在17個多目標問題的效能做評比，以及具動態參數調整的演算法在處理不同型態問題時的分析和討論。Item 以融合新式親代選擇機制之MOEA/D求解多目標最佳化問題(2010) 賴永斌; Lai Yung-Pin本論文提出一個融入新式親代選擇機制的MOEA/D演算法，用來求解多目標最佳化問題，新式親代選擇機制由三個機制組成：密集度評估機制、收斂評估機制、交配池選擇機制，使用此機制來改良MOEA/D演算法，增進演化效能，使用密集度跟收斂評估機制來分配計算資源，使計算資源不致浪費在無謂的演化上，充分的利用計算資源來達到更有效的演化，使用交配池選擇機制來改變交配池成員，原本MOEA/D演算法的設計是選擇固定成員當成交配池，而有少許機會可以選擇整個族群當成交配池，或許由固定成員進行交配在某些問題上很難逼近Pareto Front，所以我們使用交配池選擇機制來改變交配池成員，由此本論文提出一個新式親代選擇機制架構在MOEA/D演算法中，由實驗結果得知，此機制對於複雜的多目標最佳化問題可以得到很好的效能。Item 多目標演化式演算法之多狀態適應性參數調整機制(2013) 陳冠廷多目標最佳化問題在現實生活中隨處可見，像是生產排程與規劃問題，目標通常是讓生產效能最大化而耗費成本最低。此類問題的目標通常是相互衝突的，因而求解此類最佳化問題的解集合是相當困難又耗時的。演化式演算法 ( evolutionary algorithm ) 利用族群演化的特性求取 (近似) 最佳解集合，相當適合在多目標最佳化這種類型問題上使用，因此已被廣泛使用與發展。可是演化式演算法在不同的問題上需要不同的參數設定，才能獲得較佳的效能。所以如何讓使用者在參數調校的負擔減少，是一個十分重要的項目。 本論文針對 MOEA/D-AMS 演算法中的差分式演算法主要參數 F 與 CR執行動態調整，兩者分別影響子代和親代的差異程度與選擇子代的基因交配機率。本論文使用MOEA/D-AMS 收斂度評估機制作演化時期參考分類個體，佐以三種狀態參數調整機制去對應個體不同演化時期的調整。目的是希望族群中的個體能夠在不同演化時期獲得最恰當的調整方法來增進效能。最後實驗部分則會評比演算法在17個多目標問題的效能，與其他具動態參數調整機制在處理不同型態問題時的分析和討論。Item 以分解型演化演算法求解多目標資源限制專案排程問題(2017) 王映萱; Wang, Ying-Suan目前求解資源限制專案排程問題 (Resource-Constrained Project Scheduling Problem, RCPSP) 的文獻，大多注重於求解單目標問題，又以專案完工時間 (makespan) 當作目標為大多數。而在實務中，專案經理對專案考慮的目標往往是多方面的，除了專案完工時間之外，也須考量如何在讓所有的工作在所規定的時間內完成，避免工作的延遲導致成本的大幅提高。因此本研究針對最小化專案完工時間以及最小化總延遲時間 (total tardiness) 兩項目標進行求解。 本研究提出MOMA/D-IGR來求解此問題，改良自MOEA/D [7]，為了增加族群的多樣性，在環境選擇機制上，讓子代可取代的個數限制為一個，並且不讓相同個體進行取代更新。接著提出四種區域搜尋策略，希望能讓族群中的個體分採用求解方向對應之區域搜尋方法。實驗的測試問題採用Xiao等人 [15] 所提出的測試問題集，並與Xiao等人 [15] 所提出的6種演算法進行比較，分別為SPEA2、SPEA2-EM、NSGAII、NSGAII-EM、MOEA/D 以及MOEA/D-EM。實驗結果顯示MOMA/D-IGR能得出最好的效果。