增進分佈估計演算法模型正確性的小生境技術

Abstract

本論文探討在分佈估計演算法中取代方式對於假相關性數量的影響，且提出一個新的小生境技術。限制競爭式取代法是一個在分佈估計演算法領域中被廣泛使用的小生境技術。然而，限制競爭式取代法引發了變數間的假相關性，這項缺點會降低分佈估計演算法的成效。本論文使用以建構模塊為基礎定義了新的距離函式「單一小生境距離」（one-niche distance）。對於部份提供明確連結群組的分佈估計演算法，如延伸式精簡基因演算法，單一小生境距離可以直接應用於限制競爭式取代法。實驗結果顯示，在延伸式精簡基因演算法上，單一小生境距離成功地為限制競爭式取代法減低了假相關性的生成。修改過後的限制競爭式取代法仍然在族群中保留了足夠多具差異性的體。使用修改過的限制競爭式取代法的延伸式精簡基因演算法比起使用傳統限制競爭式演算法能處理更大規模的問題。另外，在具高度欺騙性的問題上，實驗顯示修改過的限制競爭式取代法從貪婪爬山演算法獲益更多且表現優於限制競爭式取代法。對於沒有提供明確連結群組的分佈估計演算法，如階層式貝式最佳化演化法，本論文提出了相關性結構矩陣限制競爭式取代法（DSMRTR）。此取代法建立一個相關性結構矩陣，藉由互補差距（differential mutual complement）估計單一小生境距離。實驗顯示，對於階層式貝式最佳化演化法，相關性結構矩陣限制競爭式取代法比起限制競爭式取代法引發較少的假相關性，同時保持了足夠的多樣性。本論文顯示出，在某些狀況下，當取代法有考慮模型建構時，可以讓分佈估計演算法有更好的表現。因此，比起依循為傳統基因演算法所做的設計，為分佈估計演算法發展新的運算子是有前景的。

This thesis investigates the effects of replacement strategies on the quantity of spurious dependencies and proposes a new niching scheme for estimation of distribution algorithms (EDAs). The restricted tournament replacement (RTR) is a well-known niching scheme in the field of EDAs. However, RTR induces spurious dependencies among variables, which impair the performances of EDAs. The work in this thesis utilizes building-block-wise distances to define a new distance metric, the one-niche distance. For those EDAs which provide explicit linkage information, such as ECGA, the one-niche distances can be directly incorporated into RTR. Experimental results show that the one-niche distance metric successfully improves RTR for ECGA with respect to the reduction of spurious dependencies. The modified RTR also maintains enough diverse individuals in the population. ECGA with the modified RTR shows higher scalability than that with the traditional RTR. Moreover, experiments show that the modified RTR gains more benefits from the greedy hill climber and outperforms RTR on highly deceptive problems. For EDAs without explicit linkage information such as hBOA, this thesis proposes DSMRTR, which constructs a dependency structure matrix via the differential mutual complement to estimate the one-niche distances. Experiments show that DSMRTR induces fewer spurious dependencies than RTR does while maintaining enough diversity for hBOA. The work in this thesis reveals that the replacement operator of EDAs yields better performances in some conditions when it takes model building into account. In the future, it is thus promising to develop different operators for EDAs instead of following the designs originally for traditional genetic algorithms.