請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34296完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 于天立 | |
| dc.contributor.author | Kai-Chun Fan | en |
| dc.contributor.author | 范凱鈞 | zh_TW |
| dc.date.accessioned | 2021-06-13T06:01:53Z | - |
| dc.date.available | 2011-07-28 | |
| dc.date.copyright | 2011-07-28 | |
| dc.date.issued | 2011 | |
| dc.date.submitted | 2011-07-26 | |
| dc.identifier.citation | [1] C. Aporntewan and P. Chongstitvatana. Building-block identification by simultaneity
matrix. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), pages 1566–1567, 2003. [2] T. B‥ack. Generalized convergence models for tournament- and (mu, lambda)- selection. In ICGA, pages 2–8, 1995. [3] S.-C. Chen and T.-L. Yu. Difficulty of linkage learning in estimation of distribution algorithms. In GECCO, pages 397–404, 2009. [4] C.-Y. Chuang and Y.-p. Chen. Likage identification by perturbation and decision tree induction. In IEEE Congress on Evolutionary Computation, pages 357–363, 2007. [5] E. D. de Jong, R. A.Watson, and D. Thierens. On the complexity of hierarchical problem solving. In GECCO, pages 1201–1208, 2005. [6] R. Etxeberria and P. Larra˝naga. Global optimization using bayesian networks. Proceedings of the Second Symposium on Arti cial Intelligence Adaptive Sys- tems, pages 332–339, 1999. [7] 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. [8] D. E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem. Genetic Algorithms and Simulated Annealing, pages 74–88, 1987. [9] D. E. Goldberg. Genetic algorithms in search, optimization and machine learn- ing. Reading, MA: Addison-Wesley, 1989. [10] D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002. [11] D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, vol. 6:333–362, 1992. [12] D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. Pro- ceedings of the Genetic and Evolutionary Computation Conference (GECCO- 2001), pages 336–342, 2001. [13] W. J. Gordon and R. F. Riesenfeld. Bernstein-b′ezier methods for the computeraided design of free-form curves and surfaces. J. ACM, 21(2):293–310, 1974. [14] G. R. Harik. Finding multimodal solutions using restricted tournament selection. In ICGA, pages 24–31, 1995. [15] G. R. Harik. Linkage learning via probabilistic modeling in the ecga. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL, February 1999. [16] G. R. Harik, E. Cantu-Paz, D. E. Goldberg, and B. L. Miller. The gambler’s ruin problem, genetic algorithms, and the sizing of populations. Proceedings of the IEEE International Conference on Evolutionary Computation, pages 7–12, 1997. [17] G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. Proceedings of the IEEE International Conference on Evolutionary Computa- tion, pages 523–528, 1998. [18] J. H. Holland. Adaptation in natural and arti cial systems. Ann Arbor, MI: University of Michigan Press, 1975. [19] H. Kargupta. The performance of the gene expression messy genetic algorithm on real test functions. In International Conference on Evolutionary Computa- tion, pages 631–636, 1996. [20] D. Knjazew and D. E. Goldberg. Omega - ordering messy ga: Solving permutation problems with the fast genetic algorithm and random keys. In GECCO, pages 181–188, 2000. [21] J.-T. Lee, K.-C. Fan, and T.-L. Yu. The essence of real-valued characteristic function for pairwise relation in linkage learning for edas. TEIL Report No. 2011002, National Taiwan University, Taipei, Taiwan, February 2011. [22] M. Munetomo and D. E. Goldberg. Designing a genetic algorithm using linkage identification by nonlinearity check. Technical report, 1998. [23] M. Munetomo and D. E. Goldberg. Identifying linkage groups by nonlinearity/non-monotonicity detection. Proceedings of the Genetic and Evo- lutionary Computation Conference (GECCO-1999), pages 433–440, 1999. [24] M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511–518, 2001. [25] M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pages 525–532, 1999. [26] M. Pelikan and H. M‥uhlenbein. The bivariate marginal distribution algorithm. Technical report, 1999. [27] C. R. Reeves and J. E. Rowe. Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory. Kluwer Academic Publishers, Norwell, MA, USA, 2002. [28] G.-C. Rota. The number of partitions of a set. The American Mathematical Monthly, 71(5):498–504, May 1964. [29] C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, vol. 27:379–423, 1948. [30] D. Thierens and D. E. Goldberg. Convergence models of genetic algorithm selection schemes. In PPSN, pages 119–129, 1994. [31] M. Tsuji, M. Munetomo, and K. Akama. Modeling dependencies of loci with string classification according to fitness differences. Proceedings of the Ge- netic and Evolutionary Computation Conference (GECCO-2004), pages 246– 257, 2004. [32] D. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Trans. Evolutionary Computation, 1(1):67–82, 1997. [33] T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-P. Chen. Genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic algorithm. In GECCO, pages 1620–1621, 2003. [34] T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for entropy-based model building in discrete estimation of distribution algorithms. In GECCO, pages 601–608, 2007. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34296 | - |
| dc.description.abstract | 加強版基因遺傳演算法(competent genetic algorithms) 透過各式各樣不同的機制來辨識基因之間是否存在鏈結(linkage) 並建立模型以解決問題。它們在真實世界中有著不少的應用，但是它們建立出來的模型是否為基因遺傳演算法真正所想要的卻不得而知。本論文提出以適應度函數的計算次數(number of function evaluation, Nfe) 作為評比模型效能的指標，並定義以最少Nfe 解決問題者為最佳模型。組成該模型的建構模塊(building blocks, BBs) 則定義為正確的建構模塊，且定義每一對屬於同一建構模塊的基因之間存在鏈結。基於以上的定義，我們檢視了一些現存用於偵測鏈結的指標函式，像是非線性(non-linearity)、熵(entropy)、同步性(simultaneity) 以及DMC。我們發現，這些指標函式先天上無法辨識某些問題的正確鏈結。於是本論文設計了一個新的指標函式：eNFE ，以補足它們的缺憾。eNFE 是根據建構模塊的新定義而設計，它藉由現存的基因遺
傳演算法理論來估測鏈結所需要的適應度函數計算次數。實驗證實eNFE 成功地幫助現存的指標函式辨識了之前無法正確辨識的鏈結。這個結果提供了一個探討模型建立與鏈結辨識的全新觀點。 | zh_TW |
| dc.description.abstract | Competent genetic algorithms (competent GAs) identify linkages between genes and build models via various mechanisms to solve problems. They have been applied
for real world applications, but whether the models given by them match what are really preferred to solve the problems is yet unknown. This thesis proposes using the number of function evaluation (Nfe) to measure the performance of models and defines the optimal model to be the one that consumes the fewest Nfe for GAs to solve a specific problem. Then the building blocks (BBs) that construct the optimal model are defined as the correct BBs, and correct linkages exist between any two genes which locate in the same BB. The capabilities of existing linkage-identification metrics, including non-linearity, entropy, simultaneity and DMC, are compared based on this definition. We find that all these metrics fail to identify correct linkages for some typical problems intrinsically. This thesis then proposes a new metric, named eNFE, directly based on the idea of Nfe to enhance the existing linkage-identification metrics. Experiment results show that eNFE is able to identify correct linkages for examined problems. The preliminary success suggests another view on learning linkage. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T06:01:53Z (GMT). No. of bitstreams: 1 ntu-100-R98921070-1.pdf: 1966002 bytes, checksum: ac53e63abaf5c359e4070aa7d14f6bea (MD5) Previous issue date: 2011 | en |
| dc.description.tableofcontents | Acknowledgement i
摘要ii Abstract iii Contents iv List of Figures vi List of Tables viii List of Abbreviations ix List of Symbols x 1 Introduction 1 2 Genetic Algorithm 3 2.1 General GA Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 New Method to Search Minimum NFE . . . . . . . . . . . . . . . . . 8 3 Competent GA 14 3.1 Building Block Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Linkage-identification Metrics . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 A Practical View on Building Blocks: the fewest NFE 20 4.1 New Definition for BBs . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 B-trap: the problem developed from B′ezier curve . . . . . . . . . . . 25 4.3 Non-linearity and Dependency . . . . . . . . . . . . . . . . . . . . . . 28 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Proposed Metric: eNFE 35 5.1 Assumption and Designing Ideas . . . . . . . . . . . . . . . . . . . . 36 5.2 Convergence Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3 Supplies of Correct Schemata . . . . . . . . . . . . . . . . . . . . . . 38 5.4 Ensure Converging to Correct Schemata . . . . . . . . . . . . . . . . 39 5.5 To Link or Not to Link . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6 Experiments and Discussions 44 6.1 DSMGA with Non-linear Models + eNFE . . . . . . . . . . . . . . . 45 6.2 Another Meaning of eNFE: Model-switching Time . . . . . . . . . . . 47 6.3 DMC + eNFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.4 DSMGA + eNFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7 Conclusions 53 Bibliography 55 | |
| dc.language.iso | en | |
| dc.subject | 適應度函數的計算次數 | zh_TW |
| dc.subject | 基因遺傳演算法 | zh_TW |
| dc.subject | 鏈結辨識 | zh_TW |
| dc.subject | 建構模塊 | zh_TW |
| dc.subject | 模型建立 | zh_TW |
| dc.subject | Linkage Learning | en |
| dc.subject | Population | en |
| dc.subject | Convergence Time | en |
| dc.subject | Building Block | en |
| dc.subject | Genetic Algorithm | en |
| dc.title | 利用估計適應度函數的計算次數辨識問題結構: 由實務觀點定義建構模塊 | zh_TW |
| dc.title | Linkage Identification by NFE Estimation: A Practical View of Building Blocks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 99-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 張時中,陳穎平 | |
| dc.subject.keyword | 基因遺傳演算法,鏈結辨識,建構模塊,模型建立,適應度函數的計算次數, | zh_TW |
| dc.subject.keyword | Genetic Algorithm,Linkage Learning,Building Block,Convergence Time,Population, | en |
| dc.relation.page | 58 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2011-07-26 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-100-1.pdf 未授權公開取用 | 1.92 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。