Cover-encodings of fitness landscapes

DOI10.1007/S11538-018-0451-1zbMATH Open1398.92179arXiv1806.05248OpenAlexW2808596446WikidataQ89287615 ScholiaQ89287615MaRDI QIDQ1786928FDOQ1786928

Authors: Konstantin Klemm, Anita Mehta, Peter F. Stadler 

Publication date: 25 September 2018

Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1806.05248

Recommendations

• Rugged and elementary landscapes
• Evolutionary Computation in Combinatorial Optimization
• Easily searched encodings for number partitioning
• scientific article; zbMATH DE number 1488085
• scientific article; zbMATH DE number 1617336

zbMATH Keywords

combinatorial optimizationadaptive walkcoarse-graininggenotype-phenotype maporacle function

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Problems related to evolution (92D15)

Cites Work

• The traveling salesman problem. A computational study.
• Title not available (Why is that?)
• Matching theory
• Combinatorial landscapes
• Handbook of product graphs
• Renormalization group and critical phenomena. I: Renormalization group and the Kadanoff scaling picture
• A fast algorithm for the maximum clique problem
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Representations for genetic and evolutionary algorithms. With a foreword by David E. Goldberg.
• The number of spanning forests of a graph
• Easily searched encodings for number partitioning
• The traveling salesman problem and its variations.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory and principled methods for the design of metaheuristics
• Design of modern heuristics. Principles and application.
• Fast Fourier transform for fitness landscapes
• Saddles and Barrier in Landscapes of Generalized Search Operators

Cited In (3)

• Title not available (Why is that?)
• Optimisation via encodings: a renormalisation group perspective
• Evolutionary Computation in Combinatorial Optimization

This page was built for publication: Cover-encodings of fitness landscapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786928)