On the impact of linkage learning, gene-pool optimal mixing, and non-redundant encoding on permutation optimization

Arthur Guijt*, Ngoc Hoang Luong, Peter A.N. Bosman, Mathijs de Weerdt

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
40 Downloads (Pure)

Abstract

Gene-pool Optimal Mixing Evolutionary Algorithms (GOMEAs) have been shown to achieve state-of-the-art results on various types of optimization problems with various types of problem variables. Recently, a GOMEA for permutation spaces was introduced by leveraging the random keys encoding, obtaining promising first results on permutation flow shop instances. A key cited strength of GOMEAs is linkage learning, i.e., the ability to determine and leverage, during optimization, key dependencies between problem variables. However, the added value of linkage learning was not tested in depth for permutation GOMEA. Here, we introduce a new version of permutation GOMEA, called qGOMEA, that works directly in permutation space, removing the redundancy of using random keys. We additionally consider various linkage information sources, including random noise, in both GOMEA variants, and compare performance with various classic genetic algorithms on a wider range of problems than considered before. We find that, although the benefits of linkage learning are clearly visible for various artificial benchmark problems, this is far less the case for various real-world inspired problems. Finally, we find that qGOMEA performs best, and is more applicable to a wider range of permutation problems.

Original languageEnglish
Article number101044
JournalSwarm and Evolutionary Computation
Volume70
DOIs
Publication statusPublished - 2022

Keywords

  • Estimation-of-distribution algorithms
  • Genetic algorithms
  • Permutation problems

Fingerprint

Dive into the research topics of 'On the impact of linkage learning, gene-pool optimal mixing, and non-redundant encoding on permutation optimization'. Together they form a unique fingerprint.

Cite this