Renormalization for Discrete Optimization

Abstract

The renormalization group has proven to be a very powerful tool in physics for treating systems with many length scales. Here we show how it can be adapted to provide a new class of algorithms for discrete optimization. The heart of our method uses renormalization and recursion, and these processes are embedded in a genetic algorithm. The system is self-consistently optimized on all scales, leading to a high probability of finding the ground state configuration. To demonstrate the generality of such an approach, we perform tests on traveling salesman and spin glass problems. The results show that our ``genetic renormalization algorithm'' is extremely powerful.

4 pages, no figure

References in corpus (3)

• Scaling of stiffness energy for 3d +/-J Ising spin glasses
• Optimization by thermal cycling
• Ising Spin Glasses in a Magnetic Field

Cited by in corpus (29)

• Optimization with Extremal Dynamics
• Spin and link overlaps in 3-dimensional spin glasses
• Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Hysteretic Optimization
• On the Effects of a Bulk Perturbation on the Ground State of 3D Ising Spin Glasses
• On the Effects of Changing the Boundary Conditions on the Ground State of Ising Spin Glasses
• Matching Kasteleyn Cities for Spin Glass Ground States
• Improved extremal optimization for the Ising spin glass
• Disorder chaos in spin glasses
• Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
• Large deviations in spin-glass ground-state energies
• Large-scale low-energy excitations in 3-d spin glasses
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• A hierarchical approach for computing spin glass ground states
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• Exact Algorithm for Sampling the 2D Ising Spin Glass
• Local excitations of a spin glass in a magnetic field
• Optimizing at the Ergodic Edge
• Persistence and Memory in Patchwork Dynamics for Glassy Models
• A comparison of extremal optimization with flat-histogram dynamics for finding spin-glass ground states
• Local excitations in mean field spin glasses
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• The Binomial Spin Glass
• Ferromagnetic-spin glass transition in four-dimensional random-bond Ising model
• Decimation flows in constraint satisfaction problems
• Ground-State Properties of a Heisenberg Spin Glass Model with a Hybrid Genetic Algorithm
• Gradient dynamics in reinforcement learning
• Bimodal coalitions and neural networks