請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7227
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 于天立 | |
dc.contributor.author | Yi-Yun Liao | en |
dc.contributor.author | 廖翊雲 | zh_TW |
dc.date.accessioned | 2021-05-19T17:40:23Z | - |
dc.date.available | 2022-09-01 | |
dc.date.available | 2021-05-19T17:40:23Z | - |
dc.date.copyright | 2019-10-09 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-08-09 | |
dc.identifier.citation | Bosman, P. A. N. and Thierens, D. (2012). Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12, pages 585–592, Philadelphia, Pennsylvania, USA. ACM.
Cover, T. T. and Thomas, J. A. (2006). Elements of information Theory. Wiley Interscience, New York, NY, USA. de Moivre, A. (1711). De mensura sortis: seu, De probabilitate eventuum in ludis a casu fortuito pendentibus, pages 213–264. Clements, London, England. Deb, K. and Goldberg, D. E. (1993). Analyzing deception in trap functions. In Foundations of Genetic Algorithms, volume 2, pages 93 – 108. Morgan Kaufmann. Goldberg, D. E., Deb, K., and Clark, J. H. (1992). Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6. Goldberg, D. E., Deb, K., and Thierens, D. (1993). Toward a better understanding of mixing in genetic algorithms. Journal of the Society of Instrument and Control Engineers, 32(1):10–16. Goldberg, D. E., Sastry, K., and Latoza, T. (2001). On the supply of building blocks. In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO ’03, pages 336–342, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. Harik, G., CantúPaz, E., Goldberg, D. E., and Miller, B. L. (1997). The gambler’s ruin problem, genetic algorithms, and the sizing of populations. In Proceedings of 1997 IEEE International Conference on Evolutionary Computation, ICEC ’97, pages 7–12, Indianapolis, IN, USA. IEEE. Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, Michigan, USA. Hsu, S.H. and Yu, T.L. (2015). Optimization by pairwise linkage detection, incremental linkage set, and restricted / back mixing: DSMGA-II. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO ’15, pages 519–526, Madrid, Spain. ACM. Liao, Y.Y., Hsu, H.W., Juang, Y.L., and Yu, T.L. (2019). On the investigation of population sizing of genetic algorithms using optimal mixing. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’19, pages 820–828, Prague, Czech Republic. ACM. Luong, N. H., Poutré, H. L., and Bosman, P. A. N. (2018). Exploiting linkage information and problemspecific knowledge in evolutionary distribution network expansion planning. Evolutionary Computation, 26(3):471–505. Mühlenbein, H. and Paaß, G. (1996). From recombination of genes to the estimation of distributions i. binary parameters. In Voigt, H.M., Ebeling, W., Rechenberg, I., and Schwefel, H.P., editors, Parallel Problem Solving from Nature — PPSN IV, pages 178–187, Berlin, Heidelberg. Springer. Orphanou, K., Thierens, D., and Bosman, P. A. N. (2018). Learning Bayesian network structures with GOMEA. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’18, pages 1007–1014, Kyoto, Japan. ACM. Pelikan, M., Sastry, K., and Goldberg, D. E. (2006). Sporadic model building for efficiency enhancement of hierarchical BOA. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO ’06, pages 405–412, Seattle, Washington, USA. ACM. Pelikan, M., Sastry, K., Goldberg, D. E., Butz, M. V., and Hauschild, M. (2009). Performance of evolutionary algorithms on nk landscapes with nearest neighbor interactions and tunable overlap. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, GECCO ’09, pages 851–858, Montreal, Québec, Canada. ACM. Thierens, D. (2010). The linkage tree genetic algorithm. In Parallel Problem Solving from Nature, PPSN XI, pages 64–273, Berlin, Heidelberg. Springer. Thierens, D. and Bosman, P. A. N. (2011). Optimal mixing evolutionary algorithms. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO ’11, pages 617–624, Dublin, Ireland. ACM. Tung, Y.F. (2015). Theoretical perspective of convergence complexity of evolutionary algorithms adopting optimal mixing. Master's thesis, National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Taipei 10617, Taiwan (R.O.C.). Virgolin, M., Alderliesten, T., Witteveen, C., and Bosman, P. A. N. (2017). Scalable genetic programming by gene-pool optimal mixing and input-space entropy-based buildingblock learning. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 1041–1048. ACM. Yu, T.L., Sastry, K., Goldberg, D. E., and Pelikan, M. (2007). Population sizing for entropy-based model building in discrete estimation of distribution algorithms. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO ’07, pages 601–608, London, England. ACM. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7227 | - |
dc.description.abstract | 使用最佳混合之基因演算法在實務上有不錯的表現,但在理論方面的支持卻不足。本論文於供應面向下探討採用最佳混合的族群大小。更精確的來說,進行了對於供應包括期望值以及下界等較精確的分析。此外,考慮使用剩餘族群重組一隨機生成之染色體使之達到全域最佳,在此情形下用以提供由神諭機選出的合適片段之緊的族群大小之邊界也被導出。在神諭機引導下的全域族群大小上界也被推導。最後,對於有環狀拓樸結構適應函數之問題,緊的族群大小之邊界也被導出。基於環狀拓樸證明中的概念,一類特定的問題拓樸結構,層狀結構,被定義並且對於可將適應函數視爲層狀結構之問題,族群大小之上界也被導出。環面、超立方以及小世界結構作爲層狀結構之例子被舉出以展示層狀結構的可應用性。 | zh_TW |
dc.description.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. | en |
dc.description.provenance | Made available in DSpace on 2021-05-19T17:40:23Z (GMT). No. of bitstreams: 1 ntu-108-R06921032-1.pdf: 1282354 bytes, checksum: 33300adff019700a87f607cb96991994 (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 口試委員會審定書i
誌謝iii 摘要v Abstract vii 1 Introduction 1 2 Background 5 2.1 Genetic Algorithms and Selecto-recombinative Genetic Algorithms 5 2.2 Optimal Mixing 8 2.3 Family of Subsets 8 2.4 Facetwise Models 10 2.5 Related Works 11 3 Oracles and Basic Supply Problem 13 3.1 Problem formulation 13 3.2 Oracle 14 3.3 Basic Supply Problem 16 3.3.1 Expectation 17 3.3.2 Lower bound 19 4 c-composite Oracles and Supply 23 4.1 Investigation on 1-composite oracles 24 4.1.1 Result with prior knowledge on the masks 24 4.1.2 General upper bound 27 4.2 General case for c-composite oracles 33 5 Results with Problems with Ring Topologies 37 5.1 Ring topology and reduction 37 5.2 Tight bounds on population size 40 6 Results with Problems beyond Ring Topologies 47 6.1 Layered structure 47 6.2 Results on torus topologies 51 6.3 Results on hypercube topologies 55 6.4 Results on small-world topologies 58 7 Conclusion 63 Bibliography 65 | |
dc.language.iso | en | |
dc.title | 由供應面向探討採用最佳混合之選擇重組基因演算法之族群大小 | zh_TW |
dc.title | Population Sizing for Selecto-Recombinative Genetic Algorithms Using Optimal Mixing in The View of Supply | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳穎平,雷欽隆,陳和麟 | |
dc.subject.keyword | 基因演算法,最佳混合,族群大小,初始供應, | zh_TW |
dc.subject.keyword | Genetic Algorithms,Optimal Mixing,Population Sizing,Initial Supply, | en |
dc.relation.page | 67 | |
dc.identifier.doi | 10.6342/NTU201902839 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2019-08-12 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf | 1.25 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。