Optimisation via encodings: a renormalisation group perspective

DOI10.1088/1751-8121/AD07C9MaRDI QIDQ6068786zbMATH OpenFDO

Authors Konstantin Klemm, Anita Mehta, Peter F. Stadler

Publication date 13 November 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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

zbMATH Keywords

coarse-grainingcombinatorial optimizationrenormalisation groupsscale invariance

Mathematics Subject Classification ID

Computer science (68-XX) Biology and other natural sciences (92-XX)

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 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. The processes that are typically employed involve some form of coarse-graining, and we suggest here that they can be viewed as avatars of renormalisation group transformations.

Recommendations

• Cover-encodings of fitness landscapes
• Coarse-Graining Large Search Landscapes Using Massive Edge Collapse
• Rugged and elementary landscapes
• scientific article; zbMATH DE number 4133843
• Evolutionary Computation in Combinatorial Optimization

Cites work

• Combinatorial landscapes
• Cover-encodings of fitness landscapes
• Easily searched encodings for number partitioning
• Fast Fourier transform for fitness landscapes
• scientific article; zbMATH DE number 5604049 (Why is no real title available?)
• scientific article; zbMATH DE number 12464 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• Idempotent generators in finite full transformation semigroups
• Isomorphisms of transformation semigroups associated with simple digraphs.
• Maximal regular subsemibands of \(\text{Sing}_n\).
• Renormalization group and critical phenomena. I: Renormalization group and the Kadanoff scaling picture
• Structural aspects of semigroups based on digraphs
• SYSTEMATIC APPROXIMATIONS FOR GENETIC DYNAMICS
• The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs
• The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup
• The traveling salesman problem. A computational study.

This page was built for publication: Optimisation via encodings: a renormalisation group perspective

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