Optimization with Extremal Dynamics

By Stefan Boettcher, Allon G. Percus. Complex, 2000

385 citations recorded by the source corpus.

We explore a new general-purpose heuristic for finding high-quality solutions to hard discrete 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 updates extremely undesirable variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, efficiently exploring many local optima. 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.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/340404bf94f621bb67bc673aeddf96e099f5e756

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

A Comprehensive Survey on Community Detection With Deep Learning (2021, methodology): “Moreover, the extensions of greedy optimizations include simulated annealing [56], extremal optimization [57], and spectral optimization [58].”
Vital nodes identification in complex networks (2016, background): “The solution can be found by minimizing the energy of a many-body system with the extremal optimization (EO) method [268].”
Community Structure in Graphs (2007, methodology): “Extremal optimization is a heuristic search procedure proposed by Boettcher and Percus [52], in order to achieve an accuracy comparable with simulated annealing, but with a substantial gain in computer time.”
Design of a Fractional Order Frequency PID Controller for an Islanded Microgrid: A Multi-Objective Extremal Optimization Method (2017, background): “Extremal optimization (EO) [28,29] is a novel evolutionary optimization framework differing from traditional optimization algorithms due to its prominent far-from-equilibrium characteristics, imitating the theory of self-organized criticality [30].”
A classification for community discovery methods in complex networks (2011, background): “sion [94] that is less sensitive to different initializations and allows escape from local maxima.”
Comparing community structure identification (2005, methodology): “ss computer memory than the other presented, since it doesn’t need extra data structures. 6.3 Extremal optimisation In this approach [38], an heuristic search procedure based on extremal optimisation [39] is used to ﬁnd the network community conﬁguration that has the best modularity value. The algor”
Community detection in graphs (2009, methodology): “Better results can be obtained if one introduces a probabilistic selection, in which vertices are ranked based on their fitness values and one picks the vertex of rank qwith the probability P(q) ∼ q (τ -EO, [196]).”
A Survey on ensemble learning under the era of deep learning (2021, methodology): “The meta-learning strategy was composed of a support vector regression machine (SVRM) (Xu et al. 2017; Zhang et al. 2017) that took the forecasting results of the trained base deep learners as inputs and was optimized by extremal optimization (EO) (Boettcher and Percus 2000, 2001, 2002).”