The Scaling Behaviour of Stochastic Minimization Algorithms in a Perfect Funnel Landscape

Abstract

We determined scaling laws for the numerical effort to find the optimal configurations of a simple model potential energy surface (PES) with a perfect funnel structure that reflects key characteristics of the protein interactions. Generalized Monte-Carlo methods(MCM, STUN) avoid an enumerative search of the PES and thus provide a natural resolution of the Levinthal paradox. We find that the computational effort grows with approximately the eighth power of the system size for MCM and STUN, while a genetic algorithm was found to scale exponentially. The scaling behaviour of a derived lattice model is also rationalized.

accepted for publication in Phys. Rev. E, January 1999