對排列問題的演化式模型調適基於多臂吃角子老虎技術

Abstract

本篇論文提供了一種針對分配估計演算法解排列問題之模型適應方 法。分配估計演算法為演化式計算中的一支，特徵在於以機率模型表 示問題解與問題解中變數間的相依關係，同時也因其能解決廣泛的問 題而為人所知。但因排列問題特徵個不相同，為其開發的模型僅能各 自解決一部分問題。因此模型的選擇影響效能甚鉅。更甚者，存在某 些排列問題是存在的模型無法描述的。這些難題促使作者們嘗試了數 種模式適應架構。列舉法同時對所有模型採樣出新的子代,並留下最佳 者。列舉法在線性排序問題得到更好的效能。為了減少在不合適的模 型上浪費計算資源，貝氏法計算每個模型的品質。但因選擇階段與樣 板技術讓貝氏法傾向節點統計模型。基於與多臂吃角子老虎問題的相 似性，我們提出了基於多臂吃角子老虎技術的模型適應架構。該架構 混合了不同的模型並動態地決定使用什麼模型。為了證明此架構的潛 力，測試了幾種排列問題。結果顯示，在當前還沒有專門的模型的問 題，此架構得到相較於單一模型的分配估計演算法還好的效能。另一 方面，在已有專門模型的問題，效能也是最接近專門模型演算法。

This thesis has provided a framework of model adaptation for estimation of distribution algorithms (EDA) on permutation problems. Characterized by the use of probabilistic models to represent the solutions and the dependencies between the variables of the problem, EDAs are known as powerful evolutionary algorithms that have been widely used for diverse types of problems. However, since the semantics of permutation problems differs, each model developed for EDAs can only deal with a subset of permutation problems. The performance suffers from inappropriate model choice. Furthermore, permutation problem may go beyond the existing models can handle. Motivated by these difficulties mentioned above, several model adaptation frameworks, which incorporate multiple models and dynamically decide to use which model, are trialled. In the first trial, the enumeration method samples multiple models simultaneously and shows better performance on Linear Ordering Problem. To reduce the waste of sampling unpromising models, the Bayesian method has been proposed characterized by measuring the quality of each model. However, the Bayesian method tends to choose inappropriate model because of the selection and the template mechanism. Considering the similarity between model adaptation and multi-armed bandit problem, a multi-armed bandit based model adaptation framework has been proposed. In order to prove the potential of the proposed framework, different permutation problems have been tested. The results show that the proposed framework outperforms the other single model EDA on problems that don't have dedicated models like the vehicle routing problem with time window, and is close to the EDAs with dedicated models on the specific problem like the traveling salesman problem.