LOCATING GLOBAL MINIMA IN OPTIMIZATION PROBLEMS BY A RANDOM-COST APPROACH

OPTIMIZATION problems are common to many diverse disciplines. The classic example is the travelling-salesman problem1,2, in which the objective is to find the shortest path connecting a number of cities. Spin glasses3, meanwhile, exemplify a general class of systems subject to conflicting constraints: in this case, the impossibility of each spin in a lattice aligning favourably with all of its neighbours leads to 'frustration' and to a large number of local energy minima. The optimization problem then becomes the attempt to find the global minimum, or ground state. Predicting the conformational ground state of proteins4 is closely allied to the spin-glass problem. The chief difficulty in searching for global minima is that straightforward search algorithms1 tend to become trapped in local minima. Only a few promising approaches, such as simulated annealing2 or genetic algorithms5, exist. Here I present a general purpose Monte Carlo procedure in which local redirections of the search path are effected at all relevant length scales while enforcing a one-dimensional random walk in the function being minimized. This method yields a series of extrema, from which the global minimum can be extracted with high probability in the limit of large statistics.