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

Scalability of Estimation of Distribution Algorithms On Allelic Pairwise Independent Functions

陳思誠(Si-Cheng Chen)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.01122

摘要

本論文探討分佈估測演算法(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.

並列關鍵字

Genetic Algorithms ； Linkage Learning ； Estimation of Distribution Algorithms ； Parity Function

參考文獻

[4] D. Coffin and R. Smith. The limitations of distribution sampling for linkage learning. In Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pages 364–369, Sept. 2007.

[5] C. Echegoyen, R. Santana, J. A. Lozano, and P. Larranaga. The impact of exact probabilistic learning algorithms in edas based on bayesian networks. Linkage in Evolutionary Computation, pages 109–139, 2008.

[6] L. Emmendorfer and A. Pozo. A clustering-based approach for linkage learning applied to multimodal optimization. Linkage in Evolutionary Computation, pages 225–248, 2008.

[8] S. Forrest and M. Mitchell. What makes a problem hard for a genetic algorithm? some anomalous results and their explanation. In Machine Learning, pages 285–319, 1993.

[10] D. E. Goldberg. Genetic algorithms and walsh functions: Part i, a gentle introduction. In Complex Systems, volume 3, pages 129 – 152, 1989.