用限制競爭式取代法與模型關聯法改進在排列問題上的模型適應

Improving Model Adaptation for Permutation Problems by RTR with Model-associated Method

吳家輝(Jia-Hui Wu)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.00303

摘要

本論文提供了針對排列問題利用限制競爭式取代法改善分配估計演算法的效能並提出限制競爭式取代法的距離量測選擇方法。限制競爭式取代法是在分配估計演算法領域中著名的小生境技術，它需要距離量測方法來評量兩個解之間的距離，但是排列問題的特徵各不相同，為其開發的距離只能正確衡量一部份的問題，在這篇論文中我們會簡單的介紹限制競爭式取代法與模型適應方法，定義三種排列的距離測量方式，然後基於模型適應方法選擇的模型來選擇限制競爭式取代法所用的距離測量方式並探討限制錦標替代法設定的視窗大小以及改進模型自適應中的報酬策略設定。在我們的實驗中，結果顯示了使用限制競爭式取代法可以增進解排列問題效能。在實驗中的，本研究方法改進了原有的方法平均十六個百分比的效能。

關鍵字

分配估計演算法 ； 模型適應 ； 排列問題 ； 距離選擇 ； 小生境技術 ； 限制競爭式取代法

並列摘要

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.

並列關鍵字

EDA ； permutation problem ； model adaptation, ； distance choosing ； niching ； RTR

參考文獻

scheduling problems with setup times or costs. European Journal of Operational

using variance estimates in multi-armed bandits. Theoretical Computer Science,

410(19):1876–1902, 2009.

[4] P. Auer. Using confidence bounds for exploitation-exploration trade-offs. The

Journal of Machine Learning Research, 3:397–422, 2003.