Cover-Encodings of Fitness Landscapes

Konstantin Klemm, Anita Mehta, Peter F. Stadler

Research output: Contribution to journalArticle

Abstract

The traditional way of tackling discrete optimization problems is by using local search on suitably defined cost or fitness landscapes. Such approaches are however limited by the slowing down that occurs when the local minima that are a feature of the typically rugged landscapes encountered arrest the progress of the search process. Another way of tackling optimization problems is by the use of heuristic approximations to estimate a global cost minimum. Here, we present a combination of these two approaches by using cover-encoding maps which map processes from a larger search space to subsets of the original search space. The key idea is to construct cover-encoding maps with the help of suitable heuristics that single out near-optimal solutions and result in landscapes on the larger search space that no longer exhibit trapping local minima. We present cover-encoding maps for the problems of the traveling salesman, number partitioning, maximum matching and maximum clique; the practical feasibility of our method is demonstrated by simulations of adaptive walks on the corresponding encoded landscapes which find the global minima for these problems.

Original languageEnglish
Pages (from-to)2154-2176
Number of pages23
JournalBulletin of Mathematical Biology
Volume80
Issue number8
DOIs
Publication statusPublished - Aug 1 2018

Keywords

  • Adaptive walk
  • Coarse-graining
  • Combinatorial optimization
  • Genotype–phenotype map
  • Oracle function

ASJC Scopus subject areas

  • Neuroscience(all)
  • Immunology
  • Mathematics(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Environmental Science(all)
  • Pharmacology
  • Agricultural and Biological Sciences(all)
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Cover-Encodings of Fitness Landscapes'. Together they form a unique fingerprint.

  • Cite this