Optimization: Finding optima in multi-funnel functions
High-dimensional optimization problems in which no gradient information is available dominate in many applications, ranging from image processing over molecular biophysics to parameter identification. Evolution strategies and other stochastic optimization algorithms have been particularly successful in this area. A large class of functions, however, could not be solved by any of the available algorithms so far. These so-called multi-funnel functions have several local minima that are distributed across multiple valleys (funnels). These functions thus are multi-modal (non-convex) and have no global structure. In such functions, local minima cannot be interpreted as perturbations to an underlying convex topology. Prominent examples of such multi-funnel functions are the free energy landscapes of gases and bio-molecules such as proteins.
We have recently presented a hybrid adaptive evolutionary optimization algorithm, combining the powerful CMA evolution strategy with concepts from swarm intelligence. Including non-local information into CMA made it possible to solve certain multi-funnel functions for the first time. On multi-funnel, strongly multi-modal, and noisy functions, the new algorithm shows superior performance compared to state-of-the-art methods. The new algorithm is implemented in a computationally efficient and fully parallel software library, which allows exploiting the parallelism of modern multi-core computer hardware and large computer clusters.
The image above shows an example of a multi-funnel function in two dimensions. The function has two funnels that both contain several local minima. The global minimum in funnel 2 is hard to find in higher dimensions. Such functions are, e.g., characteristic for the free-energy landscapes of proteins, where the minima in funnel 1 would correspond to the “unfolded state” and the isolated deep minimum in funnel 2 to the native structure.
C. L. Müller, B. Baumgartner, and I. F. Sbalzarini. Particle swarm CMA evolution strategy for the optimization of multi-funnel landscapes. In Proc. IEEE Congress on Evolutionary Computation (CEC), pages 2685-2692, Trondheim, Norway, May 2009.
C. L. Müller, B. Baumgartner, G. Ofenbeck, B. Schrader, and I. F. Sbalzarini. pCMALib: a parallel FORTRAN 90 library for the evolution strategy with covariance matrix adaptation. In Proc. ACM Genetic and Evolutionary Computation Conference (GECCO’09), Montreal, Canada, July 2009.
C. L. Müller and I. F. Sbalzarini. A tunable real-world multi-funnel benchmark problem for evolutionary optimization (and why parallel island models might remedy the failure of CMA-ES on it). In Proc. Intl. Conf. Evolutionary Computation (ICEC), Madeira, Portugal, October 2009.