Jamming Model for the Extremal Optimization Heuristic

Extremal optimization, a recently introduced meta-heuristic for hard optimization problems, is analysed on a simple model of jamming. The model is motivated first by the problem of finding lowest energy configurations for a disordered spin system on a fixed-valence graph. The numerical results for the spin system exhibit the same phenomenology found in all earlier studies of extremal optimization, and our analytical results for the model reproduce many of these features.

• Publication year

  2001

• Venue

  arXiv.org

• Publication date

  2001-10-08

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/0305-4470/35/5/301arXiv cond-mat/0110165
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Artificial Intelligence in Medicine: 23rd International Conference, AIME 2025, Pavia, Italy, June 23–26, 2025, Proceedings, Part I

  2025cited by this paper
• Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms

  2001cited by this paper
• Exact solutions for diluted spin glasses and optimization problems

  2001cited by this paper
• Faster Monte Carlo simulations at low temperatures. The waiting time method

  2001cited by this paper
• Extremal Optimization for Graph Partitioning

  2001cited by this paper
• Best possible strategy for finding ground states.

  2001cited by this paper
• Optimization with Extremal Dynamics

  2000cited by this paper
• Trajectories in phase diagrams, growth processes, and computational complexity: how search algorithms solve the 3-satisfiability problem.

  2000cited by this paper
• Simplest random K-satisfiability problem

  2000cited by this paper
• Nature of the spin glass state.

  2000cited by this paper
• Ground States for Large Samples of Two-Dimensional Ising Spin Glasses

  1999cited by this paper
• 2+p‐SAT: Relation of typical‐case complexity to the nature of the phase transition

  1999cited by this paper
• Determining computational complexity from characteristic ‘phase transitions’

  1999cited by this paper
• Calculation of ground states of four-dimensional +/-J Ising spin glasses.

  1999cited by this paper
• Extremal optimization of graph partitioning at the percolation threshold

  1999cited by this paper
• Glassy dynamics of protein folding.

  1999cited by this paper
• GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference

  1999cited by this paper
• Modern Heuristic Search Methods

  1998cited by this paper
• Slow relaxation in granular compaction

  1998cited by this paper
• GROUND-STATE BEHAVIOR OF THE THREE-DIMENSIONAL J RANDOM-BOND ISING MODEL

  1998cited by this paper
• Multicanonical methods, molecular dynamics, and Monte Carlo methods: Comparison for Lennard-Jones glasses

  1997cited by this paper
• Granular solids, liquids, and gases

  1996cited by this paper
• The ground state of the cubic spin glass with short-range interactions of Gaussian distribution

  1996cited by this paper
• Modern Heuristic Search Methods

  1996cited by this paper
• The ground state energy of the Edwards-Anderson Ising spin glass with a hybrid genetic algorithm

  1996cited by this paper
• Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm

  1995cited by this paper
• Glassiness in a Model without Energy Barriers.

  1995cited by this paper
• Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence

  1992cited by this paper
• Mean-field theory of randomly frustrated systems with finite connectivity

  1987cited by this paper
• Graph bipartitioning and spin glasses on a random network of fixed finite valence

  1987cited by this paper
• Graph bipartitioning and statistical mechanics

  1987cited by this paper
• Phase diagrams for dilute spin glasses

  1985cited by this paper
• Models of hierarchically constrained dynamics for glassy relaxation

  1984cited by this paper
• Optimization by Simulated Annealing

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper

• Long-Range Anomalous Decay of the Correlation in Jammed Packings.

  2020cites this paper
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem

  2019cites this paper
• Design of fractional order PID controller for automatic regulator voltage system based on multi-objective extremal optimization

  2015cites this paper
• Extremal Optimization for Quadratic Unconstrained Binary Problems

  2015cites this paper
• Extremal optimization for unit commitment problem for power systems

  2012cites this paper
• Extremal Optimisation Applied to Constrained Combinatorial Multi-Objective Optimisation Problems

  2012cites this paper
• Study on probability distributions for evolution in modified extremal optimization

  2010cites this paper
• Evolutionary Dynamics of Extremal Optimization

  2009influential citation
• An Information Fashion Algorithm Based on Extremal Optimization

  2009cites this paper
• A Hybrid Algorithm Based on Extremal Optimization with Adaptive Levy Mutation and Differential Evolution and Application

  2009cites this paper
• Improved Extremal Optimization for Constrained Pairwise Testing

  2009cites this paper
• A conjecture on the maximum cut and bisection width in random regular graphs

  2009cites this paper
• Construct Pairwise Test Suites Based on the Bak-Sneppen Model of Biological Evolution

  2009cites this paper
• Survey on computational complexity with phase transitions and extremal optimization

  2009cites this paper
• A Hybrid Algorithm Based on Extremal Optimization with Adaptive Levy Mutation and Differential Evolution and Application

  2009cites this paper
• Applying Extremal Optimisation To Dynamic Optimisation Problems

  2008cites this paper
• Coordinated Services Provision in Peer-to-Peer Environments

  2008cites this paper
• Scheduling aircraft landings dynamically using stochastic and deterministic elements

  2007cites this paper
• An effective heuristic algorithm for the maximum satisfiability problem

  2006influential citation
• Optimizing at the ergodic edge

  2005cites this paper
• The State Space of Complex Systems

  2005cites this paper
• Self-organizing Dynamics for Optimization

  2005cites this paper
• Solving the Maximum Satisfiability Problem Using an Evolutionary Local Search Algorithm

  2005influential citation
• Extremal optimization at the phase transition of the three-coloring problem.

  2004cites this paper
• Continuous extremal optimization for Lennard-Jones clusters.

  2004cites this paper
• Comparing extremal and thermal explorations of energy landscapes

  2004cites this paper
• Extremal optimization for Sherrington-Kirkpatrick spin glasses

  2004cites this paper
• Approximate analysis of search algorithms with "physical" methods

  2003cites this paper
• Extremal Optimization: an Evolutionary Local-Search Algorithm

  2002influential citation
• Evolutionary local-search with external optimization

  2002cites this paper
• Optimization with Extremal Dynamics

  2000cites this paper