Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.
About 876 papers for “Extremal optimization”
Stefan Boettcher · arXiv (Cornell University) · 2004
This chapter contains sections titled: Emerging Optimality Extremal Optimization Basic Notions EO Algorithm Extremal Selection Rank Ordering Defining Fitness Distinguishing EO from other Heuristics Implementing EO Numerical Results for EO Early Results Applications of EO by Others Large-scale Simulations of Spin Glasses Theoretical Investigations References
Cited by 7Open access
Sousa, Fabiano Luis de, Soeiro, Francisco José da Cunha Pires, Ramos, Fernando Manoel et al. · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · 2023
Cited by 0
Fabiano Luís de Sousa, Francisco José da Cunha Pires Soeiro, Fernando Manoel Ramos et al. · 2023
Cited by 0
Yong-Zai Lu, Yu‐Wang Chen, Min-Rong Chen et al. · Auerbach Publications eBooks · 2016
Cited by 0
Stefan Boettcher, Allon G. Percus · Physical Review Letters · 2001
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.
Cited by 341Open access
Rodica Ioana Lung (527647), Camelia Chira (527648), Anca Andreica (527649) · Figshare · 2015
Cited by 0Open access
Boettcher, S., Percus, A. G. · arXiv (Cornell University) · 2000
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.
Cited by 0Open access
Fabiano Luis De Sousa · 2008
In this paper a new stochastic algorithm for function optimization is presented. Called Generalized Extremal Optimization, it was inspired by the theory of Self-Organized Criticality and is intended to be used in complex inverse design problems, where traditional gradient based optimization methods may become inefficient. Preliminary results from a set of test functions show that this algorithm can be competitive to other stochastic methods such as the genetic algorithms. NOMENCLATURE k Index of bit rank. L Length of binary string that encodes the design variables. l Length of binary string for one design variable. N Number of design variables. V Value of the objective function for a given binary string. x Design variable. ∆V Bit fitness. τ Free adjustable parameter of the optimization algorithm.
Cited by 0
Stefan Boettcher · Journal of Computational Interdisciplinary Sciences · 2011
Dynamic features of the recently introduced extremal optimization heuristic are analyzed. Numerical studies of this evolutionary search heuristic show that it performs optimally at a transition between a jammed and an diffusive state. Using a simple, annealed model, some of the key features of extremal optimization are explained. In particular, it is verified that the dynamics of local search possesses a generic critical point under the variation of its sole parameter, separating phases of too greedy (non-ergodic, jammed) and too random (ergodic, diffusive) exploration. Analytic comparison with other local search methods, such as a Metropolis algorithm, within this model suggests that the existence of the critical point is the essential distinction leading to the optimal performance of the extremal optimization heuristic.
Cited by 1Open access
2009
Dynamic features of the recently introduced extremal optimization heuristic are analyzed. Numerical studies of this evolutionary search heuristic show that it performs optimally at a transition between a jammed and an diffusive state. Using a simple, annealed model, some of the key features of extremal optimization are explained. In particular, it is verified that the dynamics of local search possesses a generic critical point under the variation of its sole parameter, separating phases of too greedy (non-ergodic, jammed) and too random (ergodic, diffusive) exploration. Analytic comparison with other local search methods, such as a fixed temperature Metropolis algorithm, within this model suggests that the existence of the critical point is the essential distinction leading to the optimal performance of the extremal optimization heuristic.
Cited by 2
Souza, F. L., Ramos, Fernando Manuel · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · 2002
Cited by 0Open access
Stefan Boettcher, Allon G. Percus · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 2001
Extremal optimization is a new general-purpose method for approximating solutions to hard optimization problems. We study the method in detail by way of the computationally hard (NP-hard) graph partitioning problem. We discuss the scaling behavior of extremal optimization, focusing on the convergence of the average run as a function of run time and system size. The method has a single free parameter, which we determine numerically and justify using a simple argument. On random graphs, our numerical results demonstrate that extremal optimization maintains consistent accuracy for increasing system sizes, with an approximation error decreasing over run time roughly as a power law t(-0.4). On geometrically structured graphs, the scaling of results from the average run suggests that these are far from optimal with large fluctuations between individual trials. But when only the best runs are considered, results consistent with theoretical arguments are recovered.
Cited by 137Open access
Yong-Zai Lu, Yu‐Wang Chen, Min-Rong Chen et al. · CERN Document Server (European Organization for Nuclear Research) · 2016
Cited by 21
Karel Zimmermann · Mathematical programming studies · 1984
Cited by 11
János D. Pintér · Operations research, computer science. Interface series · 2000
Cited by 3
Sousa, Fabiano Luis de, Ramos, Fernando Manuel · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · 2001
In this article is introduced the Generalized Extremal Optimization algorithm. Based on the dynamics of self-organized criticality, it is intended to be used in complex inverse design problems, where traditional gradient based optimization methods are not efficient. Preliminary results from a set of test functions show that this algorithm can be competitive to other stochastic methods such as the genetic algorithms.
Cited by 0Open access
Karl Heinz Hoffmann, Frank Heilmann, Peter Salamon · Physical Review E · 2004
We treat the problem of selecting the next degree of freedom for update in an extremal optimization algorithm designed to find the ground state of a system with a complex energy landscape. We show that there exists a best distribution for selecting the next degree of freedom in order to optimize any linear function of the state probabilities, e.g., the expected number of visits to the ground state. We dub the class of algorithms using this best distribution in conjunction with extremal optimization fitness threshold accepting. In addition, we construct an extended random walk and use it to show that fitness threshold accepting is optimal also for several other measures of algorithm performance, such as maximizing the expected probability of seeing the ground state and minimizing the expected value of the lowest energy seen.
Cited by 14
Stefan Boettcher, Allon G. Percus · ArXiv.org · 2002
A recently introduced general-purpose heuristic for finding high-quality solutions for many hard optimization problems is reviewed. The method is inspired by recent progress in understanding far-from-equilibrium phenomena in terms of {\em self-organized criticality,} a concept introduced to describe emergent complexity in physical systems. This method, called {\em extremal optimization,} successively replaces the value of extremely undesirable variables in a sub-optimal solution with new, random ones. Large, avalanche-like fluctuations in the cost function self-organize from this dynamics, effectively scaling barriers to explore local optima in distant neighborhoods of the configuration space while eliminating the need to tune parameters. Drawing upon models used to simulate the dynamics of granular media, evolution, or geology, extremal optimization complements approximation methods inspired by equilibrium statistical physics, such as {\em simulated annealing}. It may be but one example of applying new insights into {\em non-equilibrium phenomena} systematically to hard optimization problems. This method is widely applicable and so far has proved competitive with -- and even superior to -- more elaborate general-purpose heuristics on testbeds of constrained optimization problems with up to $10^5$ variables, such as bipartitioning, coloring, and satisfiability. Analysis of a suitable model predicts the only free parameter of the method in accordance with all experimental results.
Cited by 0Open access
Hengyun Lu, Genke Yang, L.F. Yeung · 2009
This paper proposes a combinational optimization algorithm extremal optimization (EO) for protein structure alignment based on the contact map overlap (CMO) model. EO is a meta-heuristic algorithm, as genetic algorithm and simulated annealing, but with a local fitness introduced to guide the improvement of the optimization. By exploiting similarity matrix between two contact maps, the results demonstrate that our algorithm is significantly faster and gets better results for most of the test sets.
Cited by 8
Stefan Boettcher, Allon G. Percus · Operations research, computer science. Interface series · 2003
Cited by 86