請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/85923
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 于天立(Tian-Li Yu) | |
dc.contributor.advisor | 于天立(Tian-Li Yu | tianliyu@ntu.edu.tw | ), | |
dc.contributor.author | Chih-Kai Yang | en |
dc.contributor.author | 楊智凱 | zh_TW |
dc.date.accessioned | 2023-03-19T23:29:06Z | - |
dc.date.copyright | 2022-09-27 | |
dc.date.issued | 2022 | |
dc.date.submitted | 2022-09-23 | |
dc.identifier.citation | [1] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2012), page 585–592, 2012. [2] C. Bron and J. Kerbosch. Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9):575–577, 1973. [3] P.-L. Chen, C.-J. Peng, C.-Y. Lu, and T.-L. Yu. Two-edge graphical linkage model for DSMGA-II. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2017), page 745–752, 2017. [4] J.-D. Cho, S. Raje, and M. Sarrafzadeh. Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for vlsi applications. IEEE Transactions on Computers, 47(11):1253–1266, 1998. [5] K.-C. Fan, J.-T. Lee, T.-L. Yu, and T.-Y. Ho. Interaction-detection metric with differential mutual complement for dependency structure matrix genetic algorithm. In IEEE Congress on Evolutionary Computation, pages 3010–3017, 2010. [6] J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975. [7] S.-H. Hsu and T.-L. Yu. Optimization by pairwise linkage detection, incremental linkage set, and restricted / back mixing: Dsmga-ii. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2015), page 519–526, 2015. [8] R. M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. [9] N. M. Kumar and P. K. Mallick. The Internet of Things: Insights into the building blocks, component interactions, and architecture layers. Procedia computer science, 132:109–117, 2018. [10] M. Lauria. cnfgen. https://github.com/MassimoLauria/cnfgen, 2022. Version 0.9.0. [11] H. Lee and T.-L. Yu. Off-line building block identification: Detecting building blocks directly from fitness without genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2012), 2012. [12] C.-Y. Lyu. Convergence complexity analysis of dependency structure matrix genetic algorithm ii. Master thesis, National Taiwan University, Taipei, Taiwan, 2017. [13] J. T. Mahoney and L. Qian. Market frictions as building blocks of an organizational economics approach to strategic management. Strategic Management Journal, 34(9):1019–1041, 2013. [14] M. Munetomo and D. E. Goldberg. Identifying linkage groups by nonlinearity/non-monotonicity detection. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), 1:433–440, 1999. [15] R. Olson. Visualization of two dimensions of a NK fitness landscape, 2013. [16] M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and MAXSAT. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), pages 1271–1282, 2003. [17] T. Peterka, R. Ross, A. Gyulassy, V. Pascucci, W. Kendall, H.-W. Shen, T.-Y. Lee, and A. Chaudhuri. Scalable parallel building blocks for custom data analysis. IEEE Symposium on Large Data Analysis and Visualization (LDAV-2011), pages 105–112, 2011. [18] C. R. Reeves and J. E. Rowe. Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory. Kluwer Academic Publishers, Norwell, MA, USA, 2002. [19] G. Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovaˇc, 1997. [20] T. Sandran, M. N. B. Zakaria, and A. J. Pal. A genetic algorithm approach towards compiler flag selection based on compilation and execution duration. Proceedings of the International Conference on Computer and Information Science (ICCIS-2012), 1:270–274, 2012. [21] R. Sedgewick and K. Wayne. Algorithms, 4th Edition. Addison-Wesley, 2011. [22] A. Shenfield and S. Rostami. Multi-objective evolution of artificial neural networks in multi-class medical diagnosis problems with class imbalance. IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB-2017), pages 1–8, 2017. [23] H. H. Szmant. Organic Building Blocks of the Chemical Industry. Wiley, 1989. [24] B. Tagtekin, B. H ̈oke, M. K. Sezer, and M. U. ̈Ozt ̈urk. FOGA: flag optimization with genetic algorithm. IEEE International Conference on Innovations in Intelligent Systems and Applications (INISTA-2021), 2021. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/85923 | - |
dc.description.abstract | 在基因遺傳演算法研究中,建構模塊常被用來概略性代表一優化問題的基本組成元素,並且在演化過程中需要盡量減少對其的干擾以在使用最少資源的情況下求得最佳解。但是,如此的說法並沒有一個完整且被認可的數學定義來表述,以至我們對建構模塊和優化問題的難度之間的關係一直缺乏更深入的理解。有鑑於此,在這篇論文中我們提出了上位效應建構模塊分析 (EBBA),為鏈結以及建構模塊等常見的名詞提供正式的數學定義。另外,透過 EBBA,我們導出一個新的度量來表示優化問題的難度,我們稱之為條件難度。條件難度存在於許多現實世界的優化問題中,且強烈的影響著這些問題的整體求解難度。因此,我們在此篇也提出了對既有的首連續一問題的延伸,稱之為首連續陷阱系列。最後,我們以數據說明優化問題的最大建構模塊大小及其求解難度之間存在正相關。藉此來顯示 EBBA 不僅能用於理論推導以及分析,也具備相當的應用價值。 | zh_TW |
dc.description.abstract | The term building blocks (BBs) has long been used to vaguely describe the basic components of any given problem such that each component requires the least disruption during the effort of obtaining optimal solutions for the problem. However, even with several previous attempts, there is still no universally approved definition of it. The result is a lack of deeper understanding of how BBs affect the difficulty of various problems. In this thesis, we present the epistatic building block analysis (EBBA), which aims at providing a clear definition of BBs and produces a novel fitness-based linkage model. On top of that, we introduce the conditional difficulty, a new aspect of problem difficulty that can be directly derived with the support of EBBA. Conditional difficulty is a pivotal property that dictates the observed difficulty of some pre-existing test problems, and quite possibly an abundance of real-world ones as well. Finally, we complement the practicality of EBBA by highlighting the strong correlation between sizes of largest BB derived from their constructed linkage models and their required numbers of function evaluations to be solved by DSMGA-IIe, which is among the current state-of-the-art model building genetic algorithms. | en |
dc.description.provenance | Made available in DSpace on 2023-03-19T23:29:06Z (GMT). No. of bitstreams: 1 U0001-2009202219003800.pdf: 4278446 bytes, checksum: 1cf10410844f29154b61220d28abd14e (MD5) Previous issue date: 2022 | en |
dc.description.tableofcontents | Abstract ii 摘要 iii Acknowledgements iv 1 Introduction 1 2 Background 4 3 Epistatic Building Block Anaylsis 10 3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Mapping and Subdomain . . . . . . . . . . . . . . . . . . . . . 10 3.1.2 Collection of Optimal Patterns . . . . . . . . . . . . . . . . . 11 3.2 The Linkage Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.1 Epistatic Relation . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.2 Epistasis and Maximal Epistasis . . . . . . . . . . . . . . . . . 13 3.3 Graphical Representation . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3.1 Binary Relation Matrix and Graph . . . . . . . . . . . . . . . 15 3.3.2 Finding Maximal Epistases on a Graph . . . . . . . . . . . . . 15 4 Deconstructing Classic Problems via EBBA 19 4.1 MkTrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 FTrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 CycTrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.4 OneMax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.5 LeadingOnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Conditional Difficulty and Leading Traps Series 36 5.1 Conditional Difficulty . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Revisiting OneMax and LeadingOnes . . . . . . . . . . . . . . . . . . 38 5.3 Leading Traps Series . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6 EBBA versus Problem Difficulty 46 6.1 Calculating Problem Difficulty . . . . . . . . . . . . . . . . . . . . . . 46 6.2 Nf e of NK-Landscape . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.3 Nf e of 2D Ising Spin Glass . . . . . . . . . . . . . . . . . . . . . . . . 49 6.4 Nf e of MAX-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.5 Nf e of MAX-CUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7 Discussions 59 7.1 Complexity for Calculating MES and Conditional Difficulty . . . . . . 59 7.2 Properties for Complementarily Identical Functions . . . . . . . . . . 61 8 Conclusion and Future Works 71 Bibliography 72 Appendices 76 Appendix A Sweep Algorithm 76 | |
dc.language.iso | en | |
dc.title | 藉由引入條件難度探討二元最佳化之問題難度 | zh_TW |
dc.title | Towards the understanding of problem difficulty for binary optimization: Introducing the conditional difficulty | en |
dc.type | Thesis | |
dc.date.schoolyear | 110-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳穎平(Ying-Ping Chen),雷欽龍(Chin-Laung Lei) | |
dc.subject.keyword | 建構模塊,基因遺傳演算法,問題難度,首連續一問題, | zh_TW |
dc.subject.keyword | Building Block,Genetic Algorithm,Problem Difficulty,Leading Ones, | en |
dc.relation.page | 77 | |
dc.identifier.doi | 10.6342/NTU202203669 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2022-09-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
dc.date.embargo-lift | 2022-09-27 | - |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-2009202219003800.pdf | 4.18 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。