A Guided Monte Carlo Approach to Optimization Problems

摘要

We introduce a new Monte Carlo method by incorporating a guiding function to the conventional Monte Carlo method. In this way, the efficiency of Monte Carlo methods is drastically improved. We show how one can perform practical simulation by implementing this algorithm to search for the optimal path of the traveling salesman problem and demonstrate that its performance is comparable with more elaborate and heuristic methods. Application of this algorithm to other problems, specially the protein folding problem and protein structure prediction is also discussed.