On the convergence of a factorized distribution algorithm with truncation selection

We investigate the global convergence of a factorized distribution algorithm (FDA) with truncation selection. Like conventional genetic algorithms, FDAs maintain and successively improve a population of solutions. In FDAs, a distribution model is built based on the statistical information extracted from a set of selected solutions in the current population, and then the model thus built is used to generate new solutions for the next generation. The variable-dependence structure of the distribution model in FDAs is determined by the variable-interaction structure of the objective function. We prove that the 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 sufficient to guarantee the global convergence of estimation of distribution algorithms (EDAs) for optimization of ADFs. © 2004 Wiley Periodicals, Inc.