跳到主要內容

臺灣博碩士論文加值系統

(3.235.185.78) 您好!臺灣時間:2021/07/27 17:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:童宇凡
研究生(外文):Yu-Fan Tung
論文名稱:採用最佳混合之演化式演算法之收斂複雜度理論探討
論文名稱(外文):Theoretical Perspective of Convergence Complexity of Evolutionary Algorithms Adopting Optimal Mixing
指導教授:于天立
指導教授(外文):Tian-Li Yu
口試委員:顏嗣鈞李宏毅陳穎平
口試委員(外文):Hsu-Chun YenHung-Yi LeeYing-Ping Chen
口試日期:2015-06-23
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:51
中文關鍵詞:最佳混合收斂複雜度族群大小收斂時間適應度函數評估次數
外文關鍵詞:Optimal MixingConvergence ComplexityPopulation SizingConvergence TimeNumber of Function Evaluations
相關次數:
  • 被引用被引用:0
  • 點閱點閱:150
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於最佳混合演化式演算法的強健性,少量的族群大小需求,以及在適應度函數評估次數上的表現,此種演算法最近吸引學術界相當多注意。透過探討最佳混合,亦即最佳混合演算法中的變異運算子的機制,此篇論文著重於研究此類演算法在各種交換遮罩下的收斂表現與行為。對於單層交換遮罩,從初始供應的觀點,我們能夠導出所需要的族群大小。透過研究解答的子片段,我們能導出預估的收斂時間。由估計執行評估的機率可以得到適應度函數評估次數的上下界。基於這些結果,透過討論了交替競爭及局部搜索的影響,我們將先前的結果修正至符合多層遮罩及重疊遮罩的情形。所導出的分析模型指出了以下幾點發現。對於可完全分割的問題,使用樹狀結構的遮罩所需的評估次數,至多為單層完美模型的三倍。在較複雜的問題,及子問題較大時,樹狀結構顯得更有優勢。即使具有重疊性質的問題,仍然可以使用不重疊的遮罩解決,然而為了維持初始供應,需要相當大的族群大小,因此使得樹狀結構遮罩相形之下更顯優勢。

The optimal mixing evolutionary algorithms (OMEAs) have recently drawn much attention for their robustness, small size of required population, and efficiency in terms of number of function evaluations (NFE). To fully understand their performances, in this thesis the convergence behaviors for OMEAs are studied by investigating the mechanism of optimal mixing, the variation operator in OMEAs. For the case of one-layer masks, the required population size is derived from the viewpoint of initial supply, while the convergence time is derived by analyzing the progress of subsolution growth. NFE is then asymptotically bounded with rational probability by estimating the probability of performing evaluations. Based on these results the discussion extends to multi-layer masks and overlapping structures, which can be approximated back to the case of one-layer masks with modifications reasoned by cross competition and local search. The derived analytical models indicate the following discoveries. For fully separable problems, mixing with tree-structured masks costs at most twice more evaluations than mixing with perfect models. By problem decomposition and reduction in population, tree-structured masks are more advantageous than disjoint masks on complicated problem structures and large-size subproblems. Although problems with overlapping structures may still decomposed by disjoint masks, the population becomes inefficiently large for adequate initial supply, and hence tree-structured masks usually provide as more suitable decomposition models for these cases.

口試委員會審定書i
致謝ii
中文摘要iii
Abstract iv
1 Introduction 1
2 Background 3
2.1 Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Model Building Evolutionary Algorithms . . . . . . . . . . . . . . . . 5
2.3 Family of Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 GOMEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 One-layer Masks 15
3.1 Population Sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Convergence Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Number of Function Evaluations . . . . . . . . . . . . . . . . . . . . . 21
4 Multi-layer Masks 26
4.1 Empirical Findings on Two-layer Masks . . . . . . . . . . . . . . . . . 26
4.2 Population Sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1 Effect of Cross Competition . . . . . . . . . . . . . . . . . . . 28
4.2.2 Effect of Local Search . . . . . . . . . . . . . . . . . . . . . . 30
4.2.3 Revised Population Sizing Model . . . . . . . . . . . . . . . . 31
4.3 Growth of Correct Patterns . . . . . . . . . . . . . . . . . . . . . . . 32
4.4 Number of Function Evaluations . . . . . . . . . . . . . . . . . . . . . 35
5 Overlaping Structures 39
5.1 Analysis of the Atrap Problem . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Comparison between Different FOSs . . . . . . . . . . . . . . . . . . 42
6 Conclusion 47
Bibliography 49

[1] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced
improvements in genetic algorithms. Proceedings of the Genetic and Evolution-
ary Computation Conference (GECCO-2012), pages 585–592, 2012.
[2] P. A. Bosman and D. Thierens. More concise and robust linkage learning by
filtering and combining linkage hierarchies. Proceedings of the Genetic and
Evolutionary Computation Conference (GECCO-2013), pages 359–366, 2013.
[3] K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Proceedings
of the Second Workshop on Foundations of Genetic Algorithms (FOGA-1992),
2:98–108, 1992.
[4] D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the
sizing of populations. Complex Systems, 6:333–362, 1991.
[5] D. E. Goldberg, K. Deb, and D. Thierens. Toward a better understanding of
mixing in genetic algorithms. Urbana, 51:61801, 1992.
[6] 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.
[7] B. W. Goldman and D. R. Tauritz. Linkage tree genetic algorithms: variants
and analysis. Proceedings of the Genetic and Evolutionary Computation Con-
ference (GECCO-2012), pages 625–632, 2012.
[8] G. Harik. Linkage learning via probabilistic modeling in the ECGA. Urbana,
51(61):801, 1999.
[9] G. Harik, E. Cant′u-Paz, D. E. Goldberg, and B. L. Miller. The gambler’s
ruin problem, genetic algorithms, and the sizing of populations. Evolutionary
Computation, 7(3):231–253, 1999.
49
[10] G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm.
Evolutionary Computation, 3(4):287–297, 1999.
[11] M.Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms:
Fitness landscapes and GA performance. Proceedings of the First European
Conference on Artificial Life, pages 245–254, 1992.
[12] H. M‥uhlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder
genetic algorithm: I. Continuous parameter optimization. Evolutionary Com-
putation, 1(1):25–49, 1993.
[13] M. Pelikan and K. Sastry. BOA: The Bayesian optimization algorithm. Proceed-
ings of the Genetic and Evolutionary Computation Conference (GECCO-1999),
1999.
[14] M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization
algorithm. International Journal of Approximate Reasoning, 31(3):221 –
258, 2002.
[15] K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algo-
rithms. PhD thesis, University of Illinois at Urbana-Champaign, 2001.
[16] D. Thierens. Linkage tree genetic algorithm: First results. Proceedings of the
12th Annual Conference Companion on Genetic and Evolutionary Computa-
tion, pages 1953–1958, 2010.
[17] D. Thierens and P. A. Bosman. Optimal mixing evolutionary algorithms. Pro-
ceedings of the Genetic and Evolutionary Computation Conference (GECCO-
2011), pages 617–624, 2011.
[18] D. Thierens and P. A. Bosman. Hierarchical problem solving with the linkage
tree genetic algorithm. Proceedings of the Genetic and Evolutionary Computa-
tion Conference (GECCO-2013), pages 877–884, 2013.
[19] D. Thierens and D. Goldberg. Convergence models of genetic algorithm selection
schemes. In Parallel problem solving from nature—PPSN III, pages
119–129. Springer, 1994.
[20] D. Thierens and D. E. Goldberg. Mixing in genetic algorithms. Proceedings of
the Fifth International Conference on Genetic Algorithms (ICGA-1993), pages
38–47, 1993.
50
[21] S.-M. Wang, Y.-F. Tung, and T.-L. Yu. Investigation on efficiency of optimal
mixing on various linkage sets. Proceedings of the 2014 IEEE International
Conference on Evolutionary Computation, pages 2475–2482, 2014.
[22] 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. Proceedings of the Genetic and Evolutionary
Computation Conference (GECCO-2003), pages 1620–1621, 2003.
[23] T.-L. Yu, K. Sastry, and D. E. Goldberg. Linkage learning, overlapping building
blocks, and systematic strategy for scalable recombination. Proceedings of
the Genetic and Evolutionary Computation Conference (GECCO-2005), pages
1217–1224, 2005.
[24] T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing
for entropy-based model building in discrete estimation of distribution algorithms.
Proceedings of the Genetic and Evolutionary Computation Conference
(GECCO-2007), pages 601–608, 2007.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top