Single temperature for MonteCarlo optimization on complex landscapes

Denis Tolkunov, Alexandre Morozov

Research output: Contribution to journalArticle

4 Citations (Scopus)

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

optimization
statistics
irregularities
temperature
traveling salesman problem
funnels
simulated annealing
schedules
spin glass
folding
proteins
energy

All Science Journal Classification (ASJC) codes

  • Physics and Astronomy(all)

Cite this

@article{26d7888d13be4d74a9e5b9d187d9c1b2,
title = "Single temperature for MonteCarlo optimization on complex landscapes",
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.",
author = "Denis Tolkunov and Alexandre Morozov",
year = "2012",
month = "6",
day = "20",
doi = "10.1103/PhysRevLett.108.250602",
language = "English (US)",
volume = "108",
journal = "Physical Review Letters",
issn = "0031-9007",
publisher = "American Physical Society",
number = "25",

}

Single temperature for MonteCarlo optimization on complex landscapes. / Tolkunov, Denis; Morozov, Alexandre.

In: Physical review letters, Vol. 108, No. 25, 250602, 20.06.2012.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Single temperature for MonteCarlo optimization on complex landscapes

AU - Tolkunov, Denis

AU - Morozov, Alexandre

PY - 2012/6/20

Y1 - 2012/6/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84862529716&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862529716&partnerID=8YFLogxK

U2 - 10.1103/PhysRevLett.108.250602

DO - 10.1103/PhysRevLett.108.250602

M3 - Article

AN - SCOPUS:84862529716

VL - 108

JO - Physical Review Letters

JF - Physical Review Letters

SN - 0031-9007

IS - 25

M1 - 250602

ER -