The efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget
Lobachevsky University and University of Calabria scientists propose a convenient tool for comparing deterministic and stochastic global optimization algorithms
Global optimization problems where evaluation of the objective function is an expensive operation arise frequently in engineering, machine learning, decision making, statistics, optimal control, etc. A general global optimization problem requires to find a point x* and the value f(x*) being the global (i.e., the deepest) minimum of a function f(x) over an N-dimensional domain D, where f(x) can be non-differentiable, multiextremal, hard to evaluate even at one point (evaluations of f(x) are expensive), and given as a "black box". Therefore, traditional local optimization methods cannot be used in this situation.
Among existing derivative-free global optimization methods two classes of algorithms can be marked out: stochastic metaheuristic algorithms and deterministic mathematical programming methods. The former, due to their simplicity and attractive nature-inspired interpretations (genetic algorithms, particle swarm optimization, firefly algorithms, etc.), are used by a broad community of engineers and practitioners to solve real-life problems whereas the latter are actively studied in academia due to their interesting theoretical properties including a guaranteed convergence. Historically, these two communities are almost completely disjoint: they have different journals, different conferences, and different test functions. Due to the hardness of global optimization problems and different nature of methods from these two groups, the problem of their comparison is very difficult and methods are collated on some dozens of test functions giving poor information and unreliable results.
In order to bridge the gap between the two communities, researchers at Lobachevsky University (Russia) and University of Calabria (Italy) Ya.D. Sergeyev, D.E. Kvasov and M.S. Mukhametzhanov have proposed in their recent paper two new efficient visual techniques (called operational zones and aggregated operational zones) for a systematic comparison of global optimization algorithms having different nature. More than 800,000 runs on randomly generated 800 multidimensional test problems have been performed to compare five popular stochastic metaheuristics and three deterministic methods thus giving a new level of understanding the tested algorithms. The test problems have been chosen because, after they have been randomly generated, the optimizer is provided with locations of the global minimum and of all local minimizers (this property has made the generator of these test problems very popular–it is used nowadays in more than 40 countries of the world). The knowledge of the global solution gives the possibility to check whether the tested method has found the global optimum. Since in practical problems the global solution is unknown and, therefore, it is not possible to check the quality of the obtained solution, it is very important to see how different methods are close to the global solution after their stopping rule has been satisfied.
The research performed in the paper shows that the proposed operational and aggregated operational zones allow one to compare effectively deterministic and stochastic global optimization algorithms having different nature and give a handy visual representation of this comparison for different computational budgets. The broad numerical experiments give a new understanding for both classes of methods and open a dialogue between the two communities. It can be seen that both classes of algorithms are competitive and may surpass one another depending on the available budget of function evaluations.