Optimization with Extremal Dynamics

Details Optimization with Extremal Dynamics Optimization with Extremal Dynamics

2000-10-23

arxiv.org/abs/cond-mat/0010337v2

Phys. Rev. Lett, 86 (2001) 5211

Physics

Condensed Matter

Statistical Mechanics

4 pages, RevTex4, 1 table and 3 ps-figures included, as to appear in PRL, related papers available at http://www.physics.emo

Scientific paper

10.1103/PhysRevLett.86.5211

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.

Affiliated with

Also associated with

No associations

Rating

Optimization with Extremal Dynamics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimization with Extremal Dynamics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization with Extremal Dynamics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-45872