Single temperature for Monte Carlo optimization on complex landscapes.

ABSTRACT

We propose a new strategy for Monte Carlo (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.