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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6118217 (Why is no real title available?)
- scientific article; zbMATH DE number 5504153 (Why is no real title available?)
- scientific article; zbMATH DE number 2087177 (Why is no real title available?)
- A fast algorithm for the maximum clique problem
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Combinatorial landscapes
- Design of modern heuristics. Principles and application.
- Easily searched encodings for number partitioning
- Fast Fourier transform for fitness landscapes
- Handbook of product graphs
- Matching theory
- Renormalization group and critical phenomena. I: Renormalization group and the Kadanoff scaling picture
- Representations for genetic and evolutionary algorithms. With a foreword by David E. Goldberg.
- Saddles and Barrier in Landscapes of Generalized Search Operators
- The number of spanning forests of a graph
- The traveling salesman problem and its variations.
- The traveling salesman problem. A computational study.
- Theory and principled methods for the design of metaheuristics
Cited in
(3)
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)
