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

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

Journal information: Scientific Reports

Provided by Lobachevsky University
Citation: The efficiency of nature-inspired metaheuristics in limited-budget expensive global optimization (2018, March 23) retrieved 21 November 2019 from https://phys.org/news/2018-03-efficiency-nature-inspired-metaheuristics-limited-budget-expensive.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
11 shares

Feedback to editors

User comments