Convergence Time for Linkage Model Building in Estimation of Distribution Algorithms
Date Issued
2009
Date
2009
Author(s)
Yang, Hau-Jiun
Abstract
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.
Subjects
Estimation of Distribution Algorithms
Model Building
Linkage Learning
Convergence Time
Genetic Algorithms
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96921057-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):03fffb4991e2583515e5786e08831a40