Convergence Time for Linkage Model Building in Estimation of Distribution Algorithms

This paper proposes a convergence time model for linkage model building in estimation of distribution algorithms (EDAs). The model utilizes the result of population sizing for EDAs in previous work. By investigating the building-block identification rate of linkage model. We give a recurrence relation to express the proportion of identified building block in each generation. The recurrence fails to yield a closed form solution due to varying identification rate. Therefore, we derive upper and lower bounds instead by assuming rapid allelic convergence and fixed identification rate respectively. Specifically, The linkage model convergence time is bounded by Ω(ln(m)) and O(m), where m is the number of building blocks. Empirically, experiment results agree with the proposed bounds.