Monte Carlo dynamics in global optimization.

Abstract

Several very different optimization problems are studied by using the fixed-temperature Monte Carlo dynamics and found to share many common features. The most surprising result is that the cost function of these optimization problems itself is a very good stochastic variable to describe the complicated Monte Carlo processes. A multidimensional problem can therefore be mapped into a one-dimensional diffusion problem. This problem is either solved by direct numerical simulation or by using the Fokker-Planck equations. Above certain temperatures, the first passage time distribution functions of the original Monte Carlo processes are reproduced. At low temperatures, the first passage time has a path dependence and the single-stochastic-variable description is no longer valid. This analysis also provides a simple method to characterize the energy landscapes.