電機資訊學院: 電機工程學研究所指導教授: 于天立童宇凡Tung, Yu-FanYu-FanTung2017-03-062018-07-062017-03-062018-07-062015http://ntur.lib.ntu.edu.tw//handle/246246/276256由於最佳混合演化式演算法的強健性，少量的族群大小需求，以及在適應度函數評估次數上的表現，此種演算法最近吸引學術界相當多注意。透過探討最佳混合，亦即最佳混合演算法中的變異運算子的機制，此篇論文著重於研究此類演算法在各種交換遮罩下的收斂表現與行為。對於單層交換遮罩，從初始供應的觀點，我們能夠導出所需要的族群大小。透過研究解答的子片段，我們能導出預估的收斂時間。由估計執行評估的機率可以得到適應度函數評估次數的上下界。基於這些結果，透過討論了交替競爭及局部搜索的影響，我們將先前的結果修正至符合多層遮罩及重疊遮罩的情形。所導出的分析模型指出了以下幾點發現。對於可完全分割的問題，使用樹狀結構的遮罩所需的評估次數，至多為單層完美模型的三倍。在較複雜的問題，及子問題較大時，樹狀結構顯得更有優勢。即使具有重疊性質的問題，仍然可以使用不重疊的遮罩解決，然而為了維持初始供應，需要相當大的族群大小，因此使得樹狀結構遮罩相形之下更顯優勢。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.1783313 bytesapplication/pdf論文公開時間: 2016/7/31論文使用權限: 同意有償授權(權利金給回饋學校)最佳混合收斂複雜度族群大小收斂時間適應度函數評估次數Optimal MixingConvergence ComplexityPopulation SizingConvergence TimeNumber of Function Evaluationsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/276256/1/ntu-104-R02921044-1.pdf