Single temperature for MonteCarlo optimization on complex landscapes

Denis Tolkunov, Alexandre Morozov

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

We propose a new strategy for MonteCarlo (MC) optimization on rugged multidimensional landscapes. The strategy is based on querying the statistical properties of the landscape in order to find the temperature at which the mean first passage time across the current region of the landscape is minimized. Thus, in contrast to other algorithms such as simulated annealing, we explicitly match the temperature schedule to the statistics of landscape irregularities. In cases where these statistics are approximately the same over the entire landscape or where nonlocal moves couple distant parts of the landscape, a single-temperature MC scheme outperforms any other MC algorithm with the same move set. We also find that in strongly anisotropic Coulomb spin glass and traveling salesman problems, the only relevant statistics (which we use to assign a single MC temperature) are those of irregularities in low-energy funnels. Our results may explain why protein folding is efficient at constant temperature.

Original languageEnglish (US)
Article number250602
JournalPhysical review letters
Volume108
Issue number25
DOIs
StatePublished - Jun 20 2012

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Physics and Astronomy(all)

Cite this