Population sizing for inductive linkage identification

Abstract

Variable interdependency, referred to as linkage in genetic algorithms (GAs), has been among the most useful information in evolutionary optimisation. With the aid of linkage information, efficient evolution can be attained by GAs. Among variants of advanced GAs, linkages are either explicitly identified, as in perturbation-based methods, or implicitly extracted, as in estimation of distribution algorithms (EDAs). As linkage discovery can be considered a matter of information extraction, Shannon's entropy, a renowned metric, has been widely adopted in modern GAs. Despite the validation of theoretical bounds, which is not algorithm-specific, on evaluation complexity of linkage problems, a representative population sizing model for discrete EDAs has been developed based on the distribution of entropy measurement. On the other hand, though entropy metrics have been adopted in recent perturbation-based methods, relevant complexity analysis on these methods is still absent. In this article, we propose a population sizing model for a recently developed linkage identification method, called inductive linkage identification (ILI). The proposed model takes the entropy-based classification algorithm into account and is capable of providing an accurate estimation of population requirement. The adopted modelling approach is different than that for discrete EDAs and may give researchers insights into entropy-based linkage discovery approaches.

Keywords:

• inductive linkage identification
• perturbation-based methods
• building blocks
• population sizing
• decision trees
• genetic algorithms

Acknowledgements

This work was supported in part by the National Science Council of Taiwan under Grant NSC 99-2221-E-009-123-MY2. The authors are grateful to the National Center for High-performance Computing for computer time and facilities.