Optimization with Extremal Dynamics
arXiv:cond-mat/0010337 · doi:10.1103/PhysRevLett.86.5211
Abstract
We explore a new general-purpose heuristic for finding high-quality solutions to hard optimization problems. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively replaces extremely undesirable variables of a single sub-optimal solution with new, random ones. Large fluctuations ensue, that efficiently explore many local optima. With only one adjustable parameter, the heuristic's performance has proven competitive with more elaborate methods, especially near phase transitions which are believed to coincide with the hardest instances. We use extremal optimization to elucidate the phase transition in the 3-coloring problem, and we provide independent confirmation of previously reported extrapolations for the ground-state energy of +-J spin glasses in d=3 and 4.
4 pages, RevTex4, 1 table and 3 ps-figures included, as to appear in PRL, related papers available at http://www.physics.emory.edu/faculty/boettcher/
References in corpus (6)
Cited by in corpus (94)
- Community detection in graphs
- Comparing community structure identification
- Community detection in complex networks using Extremal Optimization
- Influence maximization in complex networks through optimal percolation
- Vital nodes identification in complex networks
- A Survey on Ensemble Learning under the Era of Deep Learning
- Community Detection via Maximization of Modularity and Its Variants
- A Classification for Community Discovery Methods in Complex Networks
- Optimal routing on complex networks
- Coloring random graphs
- Extremal Optimization for Graph Partitioning
- Exact results for the Barabasi model of human dynamics
- Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
- Immunization and targeted destruction of networks using explosive percolation
- Energy exponents and corrections to scaling in Ising spin glasses
- Transport optimization on complex networks
- Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
- Stiffness of the Edwards-Anderson Model in all Dimensions
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
- Network Community Detection: A Review and Visual Survey
- Extremal Optimization at the Phase Transition of the 3-Coloring Problem
- Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
- Collective and synchronous dynamics of photonic spiking neurons
- Nongaussian fluctuations arising from finite populations: Exact results for the evolutionary Moran process
- Accuracy and Precision of Methods for Community Identification in Weighted Networks
- Collectively optimal routing for congested traffic limited by link capacity
- Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
- Continuous extremal optimization for Lennard-Jones Clusters
- Matching Kasteleyn Cities for Spin Glass Ground States
- Improved extremal optimization for the Ising spin glass
- Stiffness Exponents for Lattice Spin Glasses in Dimensions d=3,...,6
- Random Graph Coloring - a Statistical Physics Approach
- Low-Temperature Excitations of Dilute Lattice Spin Glasses
- Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
- Density of States and Critical Behavior of the Coulomb Glass
- Comparing extremal and thermal Explorations of Energy Landscapes
- Conjecture on the maximum cut and bisection width in random regular graphs
- Jamming Model for the Extremal Optimization Heuristic
- Probing tails of energy distributions using importance-sampling in the disorder with a guiding function
- The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm
- Guided Simulated Annealing Method for Optimization Problems
- Exact Algorithm for Sampling the 2D Ising Spin Glass
- Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
- Optimal transport on wireless networks
- Optimization of transport protocols with path-length constraints in complex networks
- Local field distributions in spin glasses
- Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
- Spin glasses and algorithm benchmarks: A one-dimensional view
- Optimizing at the Ergodic Edge
- Entropic Effects in the Very Low Temperature Regime of Diluted Ising Spin Glasses with Discrete Couplings
- Fair Throughput Optimization with a Dynamic Network of Drone Relays
- On the phase transitions of graph coloring and independent sets
- On Multiobjective Evolution Model
- borealis - A generalized global update algorithm for Boolean optimization problems
- Hysteretic Optimization For Spin Glasses
- Novel disordering mechanism in ferromagnetic systems with competing interactions
- Genetic embedded matching approach to ground states in continuous-spin systems
- Exact Enumeration of Ground States in the Sherrington-Kirkpatrick Spin Glass
- Mesoscopic real space structures in aging spin-glasses: the Edwards-Anderson model
- Optimal transport on supply-demand networks
- A Heterosynaptic Learning Rule for Neural Networks
- Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
- A comparative study of selected parallel tempering methods
- Extremal optimization for sensor report pre-processing
- The dynamics of proving uncolourability of large random graphs I. Symmetric Colouring Heuristic
- Quenches in the Sherrington-Kirkpatrick model
- Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
- Wealth distribution of simple exchange models coupled with extremal dynamics
- Reduction of Dilute Ising Spin Glasses
- A comparison of extremal optimization with flat-histogram dynamics for finding spin-glass ground states
- Ground States of the Sherrington-Kirkpatrick Spin Glass with Levy Bonds
- Perturbative large deviation analysis of non-equilibrium dynamics
- Random-field-induced disordering mechanism in a disordered ferromagnet: Between the Imry-Ma and the standard disordering mechanism
- Inference from Matrix Products: A Heuristic Spin Glass Algorithm
- Understanding glassy phenomena in materials
- Magnetic freezing transition in a CoO/Permalloy bilayer revealed by transverse ac susceptibility
- The network source location problem: ground state energy, entropy and effects of freezing
- The co-evolutionary dynamics of directed network of spin market agents
- Extremal fluctuations driving the relaxation in glassy energy landscapes
- Numerical study of ground state energy fluctuations in spin glasses
- Obtaining Stiffness Exponents from Bond-diluted Lattice Spin Glasses
- An Extremal Optimization approach to parallel resonance constrained capacitor placement problem
- Maximizing Entropy Yields Spatial Scaling in Social Networks
- Physics of the Edwards-Anderson Spin Glass in Dimensions from Heuristic Ground State Optimization
- Optimization by Record Dynamics
- Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
- Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization
- Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
- Emergence of Nestedness in the Public Internet Peering Ecosystem
- Ground states of 2d +-J Ising spin glasses via stationary Fokker-Planck sampling
- A hybrid generalized extremal optimization algorithm for the quay crane scheduling problem with interference constraints
- Finding Minima in Complex Landscapes: Annealed, Greedy and Reluctant Algorithms