請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8965
標題: | 分佈估測演算法在基因成對獨立函數上之延展性探討 Scalability of Estimation of Distribution Algorithms On Allelic Pairwise Independent Functions |
作者: | Si-Cheng Chen 陳思誠 |
指導教授: | 于天立(Tian-Li Yu) |
關鍵字: | 基因演算法,鍊結學習,分佈估測演算法,奇偶性函數, Genetic Algorithms,Linkage Learning,Estimation of Distribution Algorithms,Parity Function, |
出版年 : | 2009 |
學位: | 碩士 |
摘要: | 本論文探討分佈估測演算法(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8965 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf | 413.49 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。