Solving multi-structured problems by introducing linkage kernels into GOMEA

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Model-Based Evolutionary Algorithms (MBEAs) can be highly scal- able by virtue of linkage (or variable interaction) learning. This re- quires, 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 struc- tures. 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 ad- vantages 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 publicationProceedings of the Genetic and Evolutionary Computation Conference
EditorsJ.E. Fieldsend
PublisherACM Press
Pages703-711
ISBN (Print)978-1-4503-9237-2
DOIs
Publication statusPublished - 2022

Keywords

  • Evolutionary Algorithms
  • Linkage Learning
  • Kernels
  • 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