分佈估測演算法在基因成對獨立函數上之延展性探討

Abstract

本論文探討分佈估測演算法(Estimation of Distribution Algorithms)在基因成對獨 立函數(allelic pairwise independent functions)上之延展性，以及此類函數例如奇 偶性函數(parity function)、奇偶與陷阱函數(parity-with-trap function)、沃爾什 編碼函數(Walsh-code function)對於鍊結學習(linkage learning)難度之影響。對於 分佈估測演算法而言，奇偶性函數被認為是難解的函數，但是在我們的實驗中證 實奇偶性函數可被精簡基因演算法(Compact Genetic Algorithms)在多項式時間之 內解出，並且困難度更高之奇偶與陷阱函數也被延伸式精簡基因演算法(Extended Compact Genetic Algorithms)解出，縱然鍊結模型依然無法正確被認出。我們也 計算出了精簡基因演算法在奇偶性函數上之收斂時間(convergence time)模型，並 且此模型與前述之實驗結果吻合。此外，我們也討論了不同分佈估測演算法之性 能出現歧異之根本原因。最後，本論文提出了另一個可欺騙大多數分佈估測演算 法中鍊結學習機制之基因成對獨立函數，稱之為沃爾什編碼函數，然而此函數仍 然能被精簡基因演算法解出。

This thesis investigates the difficulty of linkage learning, an essential core, in EDAs. Specifically, it examines allelic-pairwise independent functions including the parity, parity-with-trap, and Walsh-code functions. While the parity function was believed to be difficult for EDAs in previous work, our experiments indicate that it can be solved by CGA within a polynomial number of function evaluations to the problem size. Consequently, the apparently difficult parity-with-trap function can be easily solved by ECGA, even though the linkage model is incorrect. A convergence model for CGA on the parity function is also derived to verify and support the empirical findings. Then the root cause of the different performances between different EDAs is also discussed. Finally, this thesis proposes a so-called Walsh-code function, which is more difficult than the parity function. Although the proposed function does deceive the linkage-learning mechanism in most EDAs, EDAs are still able to solve it to some extent.