Monte Carlo simulation and global optimization without parameters

Abstract

We propose a new ensemble for Monte Carlo simulations, in which each state is assigned a statistical weight $1/k$, where $k$ is the number of states with smaller or equal energy. This ensemble has robust ergodicity properties and gives significant weight to the ground state, making it effective for hard optimization problems. It can be used to find free energies at all temperatures and picks up aspects of critical behaviour (if present) without any parameter tuning. We test it on the travelling salesperson problem, the Edwards-Anderson spin glass and the triangular antiferromagnet.

10 pages with 3 Postscript figures, to appear in Phys. Rev. Lett.

References in corpus (3)

• Simulated Tempering: A New Monte Carlo Scheme
• Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
• A New Approach to Spin Glass Simulations

Cited by in corpus (37)

• A Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes
• Reconstructing the Density of States by History-Dependent Metadynamics
• A Unified Approach to Enhanced Sampling
• Transition Matrix Monte Carlo Reweighting and Dynamics
• Generalized-ensemble Monte carlo method for systems with rough energy landscape
• Multicanonical Recursions
• Parallel Excluded Volume Tempering for Polymer Melts
• Algorithmic aspects of multicanonical simulations
• Potentials of Mean Force for Protein Structure Prediction Vindicated, Formalized and Generalized
• Multi-Overlap Simulations for Transitions between Reference Configurations
• Phase Transition Properties of 3D Potts Models
• Spin glass overlap barriers in three and four dimensions
• Determining Surface Phase Diagrams Including Anharmonic Effects
• Improving SAMC using smoothing methods: Theory and applications to Bayesian model selection problems
• Fast Flat-Histogram Method for Generalized Spin Models
• Stochastic dynamics simulations in a new generalized ensemble
• Convergence of Monte Carlo Simulations to Equilibrium
• Reexamination of the long-range Potts model: a multicanonical approach
• Broad Histogram Method for Multiparametric Hamiltonians
• Broad Histogram Method for Continuous Systems: the XY-Model
• Introduction to Multicanonical Monte Carlo Simulations
• Warp Bridge Sampling: The Next Generation
• Convergence of Stochastic Approximation Monte Carlo and modified Wang-Landau algorithms: Tests for the Ising model
• Single temperature for Monte Carlo optimization on complex landscapes
• Global Optimization on an Evolving Energy Landscape
• Error estimation in the histogram Monte Carlo method
• A comparison of extremal optimization with flat-histogram dynamics for finding spin-glass ground states
• Split Sampling: Expectations, Normalisation and Rare Events
• Wang-Landau simulations with non-flat distributions
• Nonflat Histogram Techniques for Spin Glasses
• Vertical-likelihood Monte Carlo
• New Algorithm to Investigate Neural Networks
• An adaptive Metropolis-Hastings scheme: sampling and optimization
• The application of Monte Carlo methods for learning generalized linear model
• A physics-based solver to improve the illumination of cylindrical targets using spherically-distributed high power laser systems
• Reconstructing the energy landscape of a distribution from Monte Carlo samples
• The Doomsday Argument, Consciousness and Many Worlds