Nature's Way of Optimizing
arXiv:cond-mat/9901351 · doi:10.1016/S0004-3702(00)00007-2
Abstract
We propose a general-purpose method for finding high-quality solutions to hard optimization problems, inspired by self-organizing processes often found in nature. The method, called Extremal Optimization, successively eliminates extremely undesirable components of sub-optimal solutions. Drawing upon models used to simulate far-from-equilibrium dynamics, it complements approximation methods inspired by equilibrium statistical physics, such as Simulated Annealing. With only one adjustable parameter, its performance proves competitive with, and often superior to, more elaborate stochastic optimization procedures. We demonstrate it here on two classic hard optimization problems: graph partitioning and the traveling salesman problem.
15 Pages, RevTex, 5 eps-figures included, several additions, as to appear in Artificial Intelligence; related papers available at http://userwww.service.emory.edu/~sboettc/
References in corpus (2)
Cited by in corpus (42)
- Community detection in complex networks using Extremal Optimization
- Random Geometric Graphs
- A Survey on Ensemble Learning under the Era of Deep Learning
- Optimization with Extremal Dynamics
- Extremal Optimization for Graph Partitioning
- Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
- Basin Hopping with Occasional Jumping
- Extremal Optimization at the Phase Transition of the 3-Coloring Problem
- Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
- Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
- Continuous extremal optimization for Lennard-Jones Clusters
- Improved extremal optimization for the Ising spin 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
- Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
- Optimization of transport protocols with path-length constraints in complex networks
- Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
- Optimizing at the Ergodic Edge
- Hysteretic Optimization For Spin Glasses
- A Heterosynaptic Learning Rule for Neural Networks
- The Peculiar Phase Structure of Random Graph Bisection
- Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
- Extremal optimization for sensor report pre-processing
- Quenches in the Sherrington-Kirkpatrick model
- Travelling Salesman Problem with a Center
- Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
- Next nearest neighbour Ising models on random graphs
- Wealth distribution of simple exchange models coupled with extremal dynamics
- Reduction of Dilute Ising Spin Glasses
- Lightning optimizes: a threshold mechanism ensures minimum-path flow
- Ground States of the Sherrington-Kirkpatrick Spin Glass with Levy Bonds
- Replica Symmetry and Combinatorial Optimization
- A comparison of extremal optimization with flat-histogram dynamics for finding spin-glass ground states
- An Extremal Optimization approach to parallel resonance constrained capacitor placement problem
- Fractals in the Nervous System: conceptual Implications for Theoretical Neuroscience
- Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
- Experimental performance of graph neural networks on random instances of max-cut
- Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
- Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity
- Agent Based Processing of Global Evaluation Function
- Gumbel-softmax Optimization: A Simple General Framework for Combinatorial Optimization Problems on Graphs