臺灣博碩士論文加值系統

(18.205.192.201) 您好！臺灣時間：2021/08/06 06:07

:::

詳目顯示

:

• 被引用:0
• 點閱:55
• 評分:
• 下載:0
• 書目收藏:0
 本論文提供了針對排列問題利用限制競爭式取代法改善分配估計演算法的效能並提出限制競爭式取代法的距離量測選擇方法。限制競爭式取代法是在分配估計演算法領域中著名的小生境技術，它需要距離量測方法來評量兩個解之間的距離，但是排列問題的特徵各不相同，為其開發的距離只能正確衡量一部份的問題，在這篇論文中我們會簡單的介紹限制競爭式取代法與模型適應方法，定義三種排列的距離測量方式，然後基於模型適應方法選擇的模型來選擇限制競爭式取代法所用的距離測量方式並探討限制錦標替代法設定的視窗大小以及改進模型自適應中的報酬策略設定。在我們的實驗中，結果顯示了使用限制競爭式取代法可以增進解排列問題效能。在實驗中的，本研究方法改進了原有的方法平均十六個百分比的效能。
 This thesis integrates the restricted tournament replacement (RTR) into estimation of distribution algorithms (EDAs) to effectively solve permutation problems and provides a method for choosing the distance measure of RTR. Since the semantics of permutation problems differ, the performance depends on distance-measure choosing. Inspired by RTR and the technique of the model adaptation for EDAs on permutation problems, the proposed method chooses the distance measure according to the selected model. We also investigate the setting of window size and modify reward policy by the feedback from our proposed method. Some experiments are used to test the efficiency of the proposed method. The results indicate that EDAs for permutation problems with RTR using the correct distance measure outperform the originals, semantic niching technique provides additional knowledge to learn the semantics of permutation problems and distance-measure choosing helps to model adaptation. Combining these features, our proposed method is close to the best performing model and may outperform any single models on problems without semantic model specially designed for that. In this thesis, our proposed method improves the performance by 16 percent in average.
 ContentsAcknowledgments i致謝ii中文摘要iiiAbstract iv1 Introduction 12 Permutation Problems 52.1 Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . 52.2 Capacitated Vehicle Routing Problem . . . . . . . . . . . . . . . . . . 72.3 Permutation Flow-Shop Scheduling Problem . . . . . . . . . . . . . . 82.4 Linear Ordering Problem . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 Quadratic Assignment Problem . . . . . . . . . . . . . . . . . . . . . 113 Related Work 133.1 Existing Semantic Models ForPermutation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1.1 The Edge-Histogram Matrix . . . . . . . . . . . . . . . . . . . 133.1.2 The Node-Histogram Matrix . . . . . . . . . . . . . . . . . . . 153.1.3 The Plackett-Luce model . . . . . . . . . . . . . . . . . . . . . 173.2 Model Adaptation for permutation problems . . . . . . . . . . . . . . 193.2.1 Multi-armed Bandit Problem . . . . . . . . . . . . . . . . . . 193.2.2 Multi-armed bandit based model adaptation . . . . . . . . . . 213.3 Niching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3.1 Niching Techniques . . . . . . . . . . . . . . . . . . . . . . . . 233.3.2 Restricted Tournament Replacement . . . . . . . . . . . . . . 234 Methodology 264.1 Distance Measure of RTR forPermutation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2 Essence of Distance-measure Choosing . . . . . . . . . . . . . . . . . 314.3 Model-associated Method . . . . . . . . . . . . . . . . . . . . . . . . 334.4 Reward Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.5 Window Size of RTR forPermutation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6 Empirical Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 Conclusion 40Bibliography 41