爬山演算法對分佈估計演算法的影響

Abstract

把全域搜尋和區域搜尋做混合是一種常見的加速最佳化問題之方 法。在二元問題上，離散爬山演算法是一種常見的區域搜尋方法。對 於分佈估計演算法來說，爬山演算法加強了有關聯基因之間的信號， 這讓模塊更精確的被建立。不僅如此，爬山演算法同時降低了問題內 基因之間的變異程度，讓決策制定更加精確。因此，爬山演算法可以 降低分佈估計演算法被執行時所需要的最小群體大小和收斂時間。但 是，執行爬山演算法本身也會耗費額外的時間。本篇論文提出一個兩 階段的爬山演算法來加速分佈估計演算法，第一個階段是執行以基因 為基礎的爬山演算法，第二階段則是執行以模塊為基礎的爬山演算 法。為了確定演算法的總執行時間是下降的，我們分別去計算使用以 基因為基礎的爬山演算法與不使用的時間複雜度。在兩種測試問題 上，兩種不同的以基因為基礎的爬山演算法被用來做測試。理論推導 以及在延伸式精簡基因演算法和相依關係結構矩陣基因演算法上的實 驗結果，都證明了其中一種基因為基礎的爬山演算法可以加速分佈估 計演算法的執行時間。當進一步和以模塊為基礎的爬山演算法做結合 以後，我們使用另外三種測試問題做測試。實驗結果顯示相依關係結 構矩陣基因演算法同時加入以基因為基礎的爬山演算法和以模塊為基 礎的爬山演算法，執行效率會比只加入以基因為基礎的爬山演算法來 的高。

Hybridization of global and local searches is a well-known technique for optimization algorithms. Discrete hill climbing is one of the local search methods on binary problems. On estimation of distribution algorithms (EDAs), hill climbing strengthens the signals of dependencies on correlated variables and improves the quality of model building. Moreover, hill climbing reduces the variance in the problem, which makes decision making more accurately. Therefore, hill climber reduces the required population size and convergence time for EDAs. However, hill climbing also consumes extra computational time. In this thesis, a two-stage hill climbing algorithm is proposed to improve the efficiency of EDAs. Gene-wise hill climbers are performed first, follow by building-block-wise hill climbers. To make sure the overall performance is improved, on gene-wise hill climbers, analytical models are developed to investigate the effects of combining two different gene-wise hill climbers with the extended compact genetic algorithm and the dependency structure matrix genetic algorithm. By using the one-max problem and the 5-bit non-overlapping trap problem as the test problems, the performances of different hill climbers are compared. Both analytical models and experiments reveal that the greedy hill climber reduces the number of function evaluations for EDAs to find the global optimum. After combining with building-blockwise hill climbers, experiments on the 5-bit non-overlapping trap problem, Cyclictrap, and NK-landscape are performed on the dependency structure matrix genetic algorithm with MinCut+ crossover method. Experiment results show that the number of function evaluations on the dependency structure matrix genetic algorithm with both gene-wise hill climbers and buildingblock- wise hill climbers is less than which only with gene-wise hill climbers.