于天立Yu, Tian-Li臺灣大學:電機工程學研究所陳思誠Chen, Si-ChengSi-ChengChen2010-07-012018-07-062010-07-012018-07-062009U0001-1308200918572900http://ntur.lib.ntu.edu.tw//handle/246246/188149本論文探討分佈估測演算法(Estimation of Distribution Algorithms)在基因成對獨函數(allelic pairwise independent functions)上之延展性，以及此類函數例如奇性函數(parity function)、奇偶與陷阱函數(parity-with-trap function)、沃爾什碼函數(Walsh-code function)對於鍊結學習(linkage learning)難度之影響。對於佈估測演算法而言，奇偶性函數被認為是難解的函數，但是在我們的實驗中證奇偶性函數可被精簡基因演算法(Compact Genetic Algorithms)在多項式時間之解出，並且困難度更高之奇偶與陷阱函數也被延伸式精簡基因演算法(Extendedompact 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.謝辭 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iibstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiontents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivist of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viist of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Motivation and Objective . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Road Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Simple Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Building Block Hypothesis and Deceptive Problems . . . . . . . . . . . . 5.3 Framework of EDAs . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Compact GA and Extended Compact GA . . . . . . . . . . . . . . . . . . . 8.4.1 Compact GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.2 Extended Compact GA . . . . . . . . . . . . . . . . . . . . . . . . . 10.5 Previous Works on Parity Functions . . . . . . . . . . . . . . . . . . 12 Performance of CGA on CPF . . . . . . . . . . . . . . . . . . . . . . . . 14.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . 14.1.1 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2 Experimental Result and Discussions . . . . . . . . . . . . . . . . . . 16 Scalability Model of CGA . . . . . . . . . . . . . . . . . . . . . . . . 17.1 CPF with Single Building Block . . . . . . . . . . . . . . . . . . . . 17.2 Scalability with Multiple BBs . . . . . . . . . . . . . . . . . . . . . 21 Performance of ECGA on CP/TF . . . . . . . . . . . . . . . . . . . . . . 23.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . 23.2 Experimental Result and Discussions . . . . . . . . . . . . . . . . . . 25 Effects of Different Probabilistic Models on ECGA . . . . . . . . . . . . 27.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . 27.2 Experimental Result and Discussions . . . . . . . . . . . . . . . . . . 28 Allelic Pairwise Independent Functions . . . . . . . . . . . . . . . . . 32.1 Walsh Functions and Walsh Codes . . . . . . . . . . . . . . . . . . . . 33.2 Walsh-code functions and Experimental Design . . . . . . . . . . . . . 34.3 Experimental Result and Discussion . . . . . . . . . . . . . . . . . . 35 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36423416 bytesapplication/pdfen-US基因演算法鍊結學習分佈估測演算法奇偶性函數Genetic AlgorithmsLinkage LearningEstimation of Distribution AlgorithmsParity Functionthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188149/1/ntu-98-R96921065-1.pdf