Solving multi-structured problems by introducing linkage kernels into GOMEA

Arthur Guijt, Dirk Thierens, Tanja Alderliesten, Peter A.N. Bosman

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

44 Downloads (Pure)

Abstract

Model-Based Evolutionary Algorithms (MBEAs) can be highly scalable by virtue of linkage (or variable interaction) learning. This requires, however, that the linkage model can capture the exploitable structure of a problem. Usually, a single type of linkage structure is attempted to be captured using models such as a linkage tree. However, in practice, problems may exhibit multiple linkage structures. This is for instance the case in multi-objective optimization when the objectives have different linkage structures. This cannot be modelled sufficiently well when using linkage models that aim at capturing a single type of linkage structure, deteriorating the advantages brought by MBEAs. Therefore, here, we introduce linkage kernels, whereby a linkage structure is learned for each solution over its local neighborhood. We implement linkage kernels into the MBEA known as GOMEA that was previously found to be highly scalable when solving various problems. We further introduce a novel benchmark function called Best-of-Traps (BoT) that has an adjustable degree of different linkage structures. On both BoT and a worst-case scenario-based variant of the well-known MaxCut problem, we experimentally find a vast performance improvement of linkage-kernel GOMEA over GOMEA with a single linkage tree as well as the MBEA known as DSMGA-II.

Original languageEnglish
Title of host publicationGECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery (ACM)
Pages703-711
Number of pages9
ISBN (Electronic)9781450392372
DOIs
Publication statusPublished - 2022
Event2022 Genetic and Evolutionary Computation Conference, GECCO 2022 - Virtual, Online, United States
Duration: 9 Jul 202213 Jul 2022

Publication series

NameGECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

Conference

Conference2022 Genetic and Evolutionary Computation Conference, GECCO 2022
Country/TerritoryUnited States
CityVirtual, Online
Period9/07/2213/07/22

Keywords

  • Evolutionary Algorithms
  • Kernels
  • Linkage Learning
  • Local Neighborhood

Fingerprint

Dive into the research topics of 'Solving multi-structured problems by introducing linkage kernels into GOMEA'. Together they form a unique fingerprint.

Cite this