Contributions: We prove that FDA with truncation selection converges globally for optimization of a class of additively decomposable functions (ADF). Our results imply that the utilization of appropriately selected dependence relationships is su±cient to guarantee the global convergence of estimation of distribution algorithms (EDAs) for optimization of ADFs.

Qingfu Zhang, “On Stability of Fixed Points of Limit Models of Univariate Marginal Distribution Algorithm and Factorized Distribution Algorithm”, IEEE Transactions on Evolutionary Computation, Vol. 8, No. 1, pp: 80-93, February, 2004.

Abstract: This paper aims to study the advantages of using higher-order statistics in Estimation Distribution of Algorithms (EDAs). We study two EDAs with 2-tournament selection for discrete optimization problems. One is the Univariate Marginal Distribution Algorithm (UMDA) using only first-order statistics and the other is the Factorized Distribution Algorithm (FDA) using higher-order statistics. We introduce the heuristic functions and the limit models of these two algorithms and analyze stability of these limit models. It is shown that the limit model of UMDA can be trapped at any local optimal solution for some initial probability models. However, degenerate probability density functions (pdfs) at some local optimal solutions are unstable in the limit model of FDA. In particular, the degenerate pdf at the global optimal solution is the unique asymptotically stable point in the limit model of FDA for the optimization of an additively decomposable function. Our results suggest that using higher-order statistics could improve the chance of finding the global optimal solution.

Qingfu Zhang, Heinz Mühlenbein, “On the Convergence of a Class of Estimation of Distribution Algorithms”, IEEE Transactions on Evolutionary Computation, Vol. 8, No. 2, pp: 127-136, April, 2004.

Abstract: We investigate the global convergence of estimation of distribution algorithms (EDAs). In EDAs, the distribution is estimated from a set of selected elements, i.e., the parent set, and then the estimated distribution model is used to generate new elements. In this paper, we prove that: (1) if the distribution of the new elements matches that of the parent set exactly, the algorithms will converge to the global optimum under three widely-used selection schemes, and (2) a factorized distribution algorithm (FDA) converges globally under proportional selection

Theory of Estimation of Distribution Algorithms