Population sizing for inductive linkage identification

Jih Yiing Lin, Ying-Ping Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalInternational Journal of Systems Science
Volume44
Issue number1
DOIs
StatePublished - 1 Jan 2013

Keywords

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

Fingerprint Dive into the research topics of 'Population sizing for inductive linkage identification'. Together they form a unique fingerprint.

Cite this