Best possible strategy for finding ground states

Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance...

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2001-06, Vol.86 (23), p.5219-5222
Main Authors: Franz, A, Hoffmann, K H, Salamon, P
Format: Article
Language:English
Subjects:
ALGORITHMS
ANNEALING
BASIC BIOLOGICAL SCIENCES
GROUND STATES
Models, Theoretical
NEURAL NETWORKS
PROTEINS
SPIN
STATISTICS
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance on selected examples. We present a proof that, within the large class of algorithms that simulate a random walk on the landscape, threshold accepting is the best possible strategy. In particular, it can perform better than simulated annealing and Tsallis statistics. Our proof is the first example of a provably optimal strategy in this area.
ISSN:0031-9007
1079-7114
DOI:10.1103/PhysRevLett.86.5219