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

Fingerprint

Fitness Landscape
Encoding
fitness
Cover
Search Space
Costs and Cost Analysis
system optimization
heuristics
Local Minima
Heuristics
Optimization Problem
Maximum Clique
Travelling salesman
Maximum Matching
Discrete Optimization
Costs
Global Minimum
Trapping
cost
Walk

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

Cite this

Cover-Encodings of Fitness Landscapes. / Klemm, Konstantin; Mehta, Anita; Stadler, Peter F.

In: Bulletin of Mathematical Biology, Vol. 80, No. 8, 01.08.2018, p. 2154-2176.

Research output: Contribution to journalArticle

Klemm, K, Mehta, A & Stadler, PF 2018, 'Cover-Encodings of Fitness Landscapes', Bulletin of Mathematical Biology, vol. 80, no. 8, pp. 2154-2176. https://doi.org/10.1007/s11538-018-0451-1
Klemm, Konstantin ; Mehta, Anita ; Stadler, Peter F. / Cover-Encodings of Fitness Landscapes. In: Bulletin of Mathematical Biology. 2018 ; Vol. 80, No. 8. pp. 2154-2176.
@article{6cb4b9be63b245f08f75bcbcbb7ed86a,
title = "Cover-Encodings of Fitness Landscapes",
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.",
keywords = "Adaptive walk, Coarse-graining, Combinatorial optimization, Genotype–phenotype map, Oracle function",
author = "Konstantin Klemm and Anita Mehta and Stadler, {Peter F.}",
year = "2018",
month = "8",
day = "1",
doi = "10.1007/s11538-018-0451-1",
language = "English",
volume = "80",
pages = "2154--2176",
journal = "Bulletin of Mathematical Biology",
issn = "0092-8240",
publisher = "Springer New York",
number = "8",

}

TY - JOUR

T1 - Cover-Encodings of Fitness Landscapes

AU - Klemm, Konstantin

AU - Mehta, Anita

AU - Stadler, Peter F.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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.

AB - 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.

KW - Adaptive walk

KW - Coarse-graining

KW - Combinatorial optimization

KW - Genotype–phenotype map

KW - Oracle function

UR - http://www.scopus.com/inward/record.url?scp=85048369029&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048369029&partnerID=8YFLogxK

U2 - 10.1007/s11538-018-0451-1

DO - 10.1007/s11538-018-0451-1

M3 - Article

VL - 80

SP - 2154

EP - 2176

JO - Bulletin of Mathematical Biology

JF - Bulletin of Mathematical Biology

SN - 0092-8240

IS - 8

ER -