Linkage learning by number of function evaluations estimation: Practical view of building blocks

摘要

Estimation of distribution algorithms (EDAs) identify linkages among genes and build models which decompose a given problem. EDAs have been successfully applied to many real-world problems; however, whether their models indicate the optimal way to decompose the given problem is rarely studied. This paper proposes using the number of function evaluations (~(Nfe)) as the performance measure of EDA models. As a result, the optimal model can be defined as the one that consumes the fewest ~(Nfe) on average for EDAs to solve a specific problem. Based on this concept, correct building blocks (BBs) can be defined as groups of genes that construct the optimal model. Similarly, linkages within a BB are defined as the correct linkages of which the specific problem consists. The capabilities of four commonly used linkage-learning metrics, nonlinearity, entropy, simultaneity and differential mutual complement, are investigated based on the above definitions. For certain partially separable problems, none of the above metrics yields difference that is statistically significant between linear and nonlinear gene pairs. Although an optimal threshold still exists to separate linear and nonlinear gene pairs, most existing EDA designs today have not yet characterize such threshold. Based on the idea of Nfe estimation, this paper also proposes a metric enhancer, named eNFE, to enhance existing linkage-learning techniques. Empirical results show that eNFE improves BB identification by eliminating spurious linkages which occur often in most existing EDAs.