Sensibility of linkage information and effectiveness of estimated distributions

Chung Yao Chuang, Ying-Ping Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


The probabilistic model building performed by estimation of distribution algorithms (EDAs) enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, it may not be possible to completely and accurately identify the whole problem structure by probabilistic modeling due to certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems consisting of structures with unequal fitness contributions. Based on the illustrative example, we introduce a notion that the estimated probabilisticmodels should be inspected to reveal the effective search directions and further propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented on the extended compact genetic algorithm (ECGA) and experiments are performed on several sets of additively separable problems with different scaling setups. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire problem structure cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.

Original languageEnglish
Pages (from-to)547-579
Number of pages33
JournalEvolutionary Computation
Issue number4
StatePublished - 10 Dec 2010


  • Effective distribution
  • Estimation of distribution algorithm
  • Evolutionary computation
  • Extended compact genetic algorithm
  • Linkage sensibility
  • Model pruning
  • Probabilistic model
  • Sensible linkage

Fingerprint Dive into the research topics of 'Sensibility of linkage information and effectiveness of estimated distributions'. Together they form a unique fingerprint.

Cite this