估計分配演算法的模型建構收斂時間

Convergence Time for Linkage Model Building in Estimation of Distribution Algorithms

楊皓鈞(Hau-Jiun Yang)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.02612

摘要

本論文提出了一個分佈估計演算法(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.

並列關鍵字

Estimation of Distribution Algorithms ； Model Building ； Linkage Learning ； Convergence Time ； Genetic Algorithms

參考文獻

[1] S. Baluja and S. Davies. Combining multiple optimization runs with optimal

dependency trees. Technical report, 1997.

[2] T. Blickle and L. Thiele. A mathematical analysis of tournament selection. In

9{16. Morgan Kaufmann, 1995.

probability densities. In Advances in Neural Information Processing Systems,