于天立Yu, Tian-Li臺灣大學:電機工程學研究所楊皓鈞Yang, Hau-JiunHau-JiunYang2010-07-012018-07-062010-07-012018-07-062009U0001-2307200921150200http://ntur.lib.ntu.edu.tw//handle/246246/188143本論文提出了一個分佈估計演算法(estimation of distribution algorithms)的模型建構收斂時間的模型。該模型利用了之前分佈估計演算法的人口規模調整(population sizing)的結果。我們給了一個遞迴關係式用來表示每一個世代被認出的積木(building block)的比例，而且我們用這個遞迴關係式來推導出收斂時間的上限跟下限。因為在每個世代的連接認出機率(linkage identification rate)在改變，所以收斂時間的上限很難找出一個封閉形式(closed form)，另外藉由假設等位基因的(allelic)快速收斂來推導出連接認出機率。因此，我們用了一些算術上的假設來使的上限成立。我們另外也假設了固定的連接認出機率來推導出下限。最後我們可以發現收斂時間可以被ln m和O(m)限制住，其中$m$是表示積木的數目而且m是跟問題的大小成正比。在延伸式精簡基因演算法(ECGA)跟相依關係結構矩陣基因演算法(DSMGA)的實驗結果可以驗證本論文提出的模型。最後，我們藉由觀察基因演算法的收斂時間來試圖解釋如何得到一個更嚴格的限制。This thesis proposes a convergence time model for model building in estimation of distribution algorithms (EDAs). The model utilizes the result of population sizing for EDAs in previous work. We give a recurrence relation to express the proportion of identified building blocks in each generation and use the recurrence function to model upper and lower bounds. The upper bound fails to yield a closed form solution due to the varying linkage identification rate, and the linkage identification rate is derived by assuming rapid allelic convergence. Therefore, we use some arithmetic approximations to keep the upper bound hold. We also derive lower bounds by assuming fixed identification rate. Specifically, The linkage model convergence time is bounded by O(ln m) and O(m), where m is the number of building blocks and it is proportional to problem size. Empirically, experiment results on ECGA and DSMGA agree with the proposed bounds. Finally, we give an insight for a tighter bound by observing the allelic convergence time.中文摘要 iiBSTRACT iiiist of Figures iiiist of Abbreviation iv Introduction 1 Simple GA & GA theory 3.1 Introduction to simple GAs . . . . . . . . . . . . . . . . . . . . . . . 3.2 Building block, decomposable problem and deceptive problem . . . . 6.3 Population sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Race between innovation time and takeover time . . . . . . . . . . . . 10.5 Convergence time model . . . . . . . . . . . . . . . . . . . . . . . . . 10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 An Introduction to EDAs 13.1 Estimation of distribution algorithms . . . . . . . . . . . . . . . . . . 13.2 From cGA to ECGA . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.3 DSMGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.4 Population sizing for EDAs . . . . . . . . . . . . . . . . . . . . . . . 17.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19i Linkage-Identi?cation Abilities for EDAs 21.1 Starting linkage-identi?cation probability . . . . . . . . . . . . . . . . 21.2 Modeling linkage-identi?cation probability . . . . . . . . . . . . . . . 24.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Convergence Time for Linkage Model 28.1 Recurrence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28.2 Modeling the upper bound . . . . . . . . . . . . . . . . . . . . . . . . 29.3 Modeling the lower bound . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Experiments and discussions . . . . . . . . . . . . . . . . . . . . . . . 31.5 Insight for tighter bounds . . . . . . . . . . . . . . . . . . . . . . . . 36.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Summary and Conclusions 40510260 bytesapplication/pdfen-US估計分配演算法模型建構連接學習收斂時間基因演算法Estimation of Distribution AlgorithmsModel BuildingLinkage LearningConvergence TimeGenetic Algorithmsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188143/1/ntu-98-R96921057-1.pdf