The efficiency of nature-inspired metaheuristics in limited-budget expensive global optimization

March 23, 2018, Lobachevsky University

Global optimization problems in which 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 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 has found the global optimum. Since in practical 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 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 evaluations.

The study is published in Scientific Reports.

Explore further: Diagonal methods for expensive global optimization

Related Stories

Diagonal methods for expensive global optimization

November 13, 2017

The goal of global optimization is essentially to search for optimal solutions in various areas of human activity. The principal advantage of the diagonal approach compared to other methods is its speed. Russian scientists ...

A practical optimisation algorithm for big data applications

September 26, 2017

Numerous science and engineering applications require finding the lowest or highest value of a mathematical model. This is usually obtained computationally by running an optimisation algorithm. When working with big data ...

D-Wave and predecessors: From simulated to quantum annealing

June 23, 2014

The D-Wave computer is currently the latest link of a long chain of computers designed for the solution of optimization problems. In what sense does it realize quantum computation? We describe the evolution of such computers ...

Recommended for you

Semimetals are high conductors

March 18, 2019

Researchers in China and at UC Davis have measured high conductivity in very thin layers of niobium arsenide, a type of material called a Weyl semimetal. The material has about three times the conductivity of copper at room ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.