Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7227
Title: | 由供應面向探討採用最佳混合之選擇重組基因演算法之族群大小 Population Sizing for Selecto-Recombinative Genetic Algorithms Using Optimal Mixing in The View of Supply |
Authors: | Yi-Yun Liao 廖翊雲 |
Advisor: | 于天立 |
Keyword: | 基因演算法,最佳混合,族群大小,初始供應, Genetic Algorithms,Optimal Mixing,Population Sizing,Initial Supply, |
Publication Year : | 2019 |
Degree: | 碩士 |
Abstract: | 使用最佳混合之基因演算法在實務上有不錯的表現,但在理論方面的支持卻不足。本論文於供應面向下探討採用最佳混合的族群大小。更精確的來說,進行了對於供應包括期望值以及下界等較精確的分析。此外,考慮使用剩餘族群重組一隨機生成之染色體使之達到全域最佳,在此情形下用以提供由神諭機選出的合適片段之緊的族群大小之邊界也被導出。在神諭機引導下的全域族群大小上界也被推導。最後,對於有環狀拓樸結構適應函數之問題,緊的族群大小之邊界也被導出。基於環狀拓樸證明中的概念,一類特定的問題拓樸結構,層狀結構,被定義並且對於可將適應函數視爲層狀結構之問題,族群大小之上界也被導出。環面、超立方以及小世界結構作爲層狀結構之例子被舉出以展示層狀結構的可應用性。 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 |
Fulltext Rights: | 同意授權(全球公開) |
Appears in Collections: | 電機工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-108-1.pdf | 1.25 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.