Convergence Time for Linkage Model Building in Estimation of Distribution Algorithms

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 Ω(ln(m)) and O(m), where m is the number of building blocks ant 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