請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7227
標題: | 由供應面向探討採用最佳混合之選擇重組基因演算法之族群大小 Population Sizing for Selecto-Recombinative Genetic Algorithms Using Optimal Mixing in The View of Supply |
作者: | Yi-Yun Liao 廖翊雲 |
指導教授: | 于天立 |
關鍵字: | 基因演算法,最佳混合,族群大小,初始供應, Genetic Algorithms,Optimal Mixing,Population Sizing,Initial Supply, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 使用最佳混合之基因演算法在實務上有不錯的表現,但在理論方面的支持卻不足。本論文於供應面向下探討採用最佳混合的族群大小。更精確的來說,進行了對於供應包括期望值以及下界等較精確的分析。此外,考慮使用剩餘族群重組一隨機生成之染色體使之達到全域最佳,在此情形下用以提供由神諭機選出的合適片段之緊的族群大小之邊界也被導出。在神諭機引導下的全域族群大小上界也被推導。最後,對於有環狀拓樸結構適應函數之問題,緊的族群大小之邊界也被導出。基於環狀拓樸證明中的概念,一類特定的問題拓樸結構,層狀結構,被定義並且對於可將適應函數視爲層狀結構之問題,族群大小之上界也被導出。環面、超立方以及小世界結構作爲層狀結構之例子被舉出以展示層狀結構的可應用性。 Genetic algorithms using optimal mixing have shown promising results, but lack theoretical supports. This thesis investigates population sizing from the supply aspect under the optimal mixing scenario. Specifically, more precise analyses on supply, including the expectation and the lower bound, are made. Furthermore, considering recombining one randomly generated chromosome with the rest of the population to achieve the global optimum, the tight bounds on the size of the population providing proper fragments chosen by restricted oracles are derived. A global upper bound on the size of the population with the guide of an oracle is also derived. Finally, for problem dependent cases, tight bound on the size of the population on problems with fitness functions with ring topologies is derived. Based on the intuition in the proof of the ring topologies case, a category of problem topologies, layered structures, is defined, and upper bounds on the size of the population on problems with fitness functions that can be viewed as layered structures are derived. Examples of layered structures, such as torus and hypercube, are provided to show the applicability of the layered structures. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7227 |
DOI: | 10.6342/NTU201902839 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf | 1.25 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。