It is widely believed that in order to solve large scale global optimization problems an appropriate mixture of local approximation and global exploration is necessary. Local approximation, if first order information on the objective function is available, is efficiently performed by means of local optimization methods. Unfortunately, global exploration, in absence of some kind of global information on the problem, is a ``blind'' procedure, aimed at placing observations as evenly as possible in the search domain. Often this procedure reduces to uniform random sampling (like in Multistart algorithms, or in techniques based on clustering). In this paper we propose a new framework for global exploration which tries to guide random exploration towards the region of attraction of low-level local optima. The main idea originated by the use of smoothing techniques (based on gaussian convolutions): the possibility of applying a smoothing transformation not to the objective function but to the result of local searches seems to have never been explored yet. Although an exact smoothing of the results of local searches is impossible to implement, in this paper we propose a computational approximation scheme which has proven to be very efficient and (maybe more important) extremely robust in solving large scale global optimization problems with huge numbers of local optima.
Citation
Technical Report DSI 5-2003 (revised), Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Firenze, 2003.