BITEOPT - Derivative-Free Optimization Method

Introduction

BITEOPT is a free open-source stochastic non-linear bound-constrained derivative-free optimization method (algorithm, heuristic, or strategy) for global optimization. The name "BiteOpt" is an acronym for "BITmask Evolution OPTimization".

The benefit of this method is a relatively high robustness: it can successfully optimize a wide range of multi-dimensional test functions. Another benefit is a low convergence time which depends on the complexity of the objective function. Hard (multi-modal) problems may require many optimization attempts to reach optimum.

Instead of iterating through different "starting guesses" to find optimum like in deterministic methods, this method requires optimization attempts with different random seeds. The stochastic nature of the method allows it to automatically "fall" into different competing minima on each attempt. If there are no competing minima in a function present (or the true/global minimum is rogue and cannot be detected), this method in absolute majority of attempts returns the same optimum.

BiteOpt uses self-optimization techniques making it objective function-agnostic. In its inner workings, BiteOpt uses objective function value's ranking, and not the actual value. BiteOpt is a multi-faceted example of a "probabilistic computing" system.

Python binding is available as a part of fcmaes library

Sponsoring

If you are regularly using BiteOpt in a commercial environment, you may consider donating/sponsoring the project. Please contact the author via aleksey.vaneev@gmail.com or info@voxengo.com. A solver for AMPL NL models is available commercially.

Comparison

This "black-box" optimization method was tested on 2000+ 1- to 60-dimensional optimization problems and performed well, and it successfully solves even 600-dimensional test problems found in some textbooks. But the main focus of the method is to provide fast solutions for computationally expensive "black-box" problems of medium dimensionality (up to 60).

This method was compared with the results of this paper (on 244 published C non-convex smooth problems, convex and non-convex non-smooth problems were not evaluated): Comparison of derivative-free optimization algorithms. This method was able to solve 76% of non-convex smooth problems in 10 attempts, 2500 iterations each. It comes 2nd in the comparison on non-convex smooth problems (see Fig.9 in the paper). With a huge iteration budget (up to 1 million) this method solves 97% of problems.

On a comparable test function suite and conditions outlined at this page: global_optimization (excluding several ill-defined and overly simple functions, and including several complex functions, use test2.cpp to run the test) this method's attempt success rate is >94% (with 100% of functions solved) while the average number of objective function evaluations is ~370.

At least in these comparisons, this method performs better than plain CMA-ES which is also a well-performing stochastic optimization method. As of version 2021.1, BiteOpt's "solvability" exceeds CMA-ES on synthetic function sets that involve random coordinate axis rotations and offsets (e.g., BBOB suite). BiteOptDeep (e.g., with M=8) considerably outperforms CMA-ES in "solvability".

As a matter of sport curiosity, BiteOpt is able to solve, in reasonable time, almost all functions proposed in classic academic literature on global optimization. This is quite a feat for a derivative-free method (not to be confused with large-scale analytic and gradient-based global optimization methods). Of course, BiteOpt is capable of more than that. If you have a reference to a function (with a known solution) published in literature that BiteOpt can't solve, let the author know.

BiteOpt (state at commit 124) took 2nd place (1st by sum of ranks) in BBComp2018-1OBJ-expensive competition track. Since the time of that commit the method improved in many aspects, especially in low-dimensional convergence performance. Commit 124 can be considered as "baseline effective" version of the method (it is also maximally simple), with further commits implementing gradual improvements, but also adding more complexity.

Also, BiteOpt (state at commit 256) took 2nd place (3rd by sum of ranks) in BBComp2019-1OBJ competition track.

CBiteOpt (biteopt.h)

BiteOpt optimization class. Implements a stochastic non-linear bound-constrained derivative-free optimization method. It maintains a cost-ordered population list of previously evaluated solutions that are evolved towards a lower cost (objective function value). On every iteration, the highest-cost solution in the list can be replaced with a new solution, and the list reordered. A population of solutions allows the method to space solution vectors apart from each other thus making them cover a larger parameter search space collectively. Beside that, a range of parameter randomization and the "step in the right direction" (Differential Evolution "mutation") operations are used that move the solutions into positions with a probabilistically lower objective function value.

Since version 2021.1 BiteOpt uses a companion optimizer - SpherOpt - which works independently and provides "reference points" to BiteOpt. Such companion improves BiteOpt's convergence properties considerably, especially when the parameter space is rotated. Since version 2021.15 BiteOpt uses an additional companion optimizer - NMSeqOpt - which increases diversity of generated solutions.

Since version 2021.3 BiteOpt became a self-optimizing method not requiring any fune-tuning from the user nor the author.

CBiteOptDeep (biteopt.h)

Deep optimization class. Based on an array of M CBiteOpt objects. This "deep" method pushes the newly-obtained solution to the random CBiteOpt object which is then optimized. This method, while increasing the convergence time, is able to solve complex multi-modal functions.

This method is most effective on complex functions, possibly with noisy fluctuations near the global solution, that are not very expensive to evaluate and that have a large iteration budget. Tests have shown that on smooth functions that have many strongly competing minima this "deep" method considerably increases the chance to find a global solution, relative to the CBiteOpt class, but still requires several attempts with different random seeds. When using this method, the required iteration budget usually increases by a factor of M^0.5, but the number of required optimization attempts usually decreases. In practice, it is not always possible to predict the convergence time increase of the CBiteOptDeep class, but increase does correlate to its M parameter. For some complex functions the use of CBiteOptDeep even decreases convergence time. For sure, the CBiteOptDeep class often produces better solutions than the CBiteOpt class.

Notes

BiteOpt is a completely self-optimizing method. It does not feature user-adjustable hyper-parameters. Even population size adjustments may not be effective.

It is usually necessary to run the optimization process several times, with different random seeds, since the process may get stuck at a local minimum. Running 10 times is a minimal general requirement. The required number of optimization attempts is usually proportional to the number of strongly competing minima in a function.

This method is hugely-probabilistic, and it depends on its initial state, which is selected randomly. In most cases it is more efficient to attempt to optimize with a new random seed than to wait for the optimization process to converge. Based on the results of optimization of the test-set, for 2-dimensional functions, it is reasonable to expect convergence in 800 iterations (in a successful attempt); for 10-dimensional functions, it is reasonable to expect convergence in 8000 iterations (harder functions may require more iterations to converge). Most classic 2-dimensional problems converge in 400 iterations or less, at 10^-6 precision. On average, every doubling of dimensions requires tripling of iteration budget. Complex multi-modal problems require a magnitudes larger iteration and attempt budget.

Each attempt may generate an equally-usable candidate solution (not necessarily having the least cost), permitting the researcher to select a solution from any attempt based on his/her own considerations. In this light, it may be incorrect to assume that least-performing attempts are "wasted". In practice, least-performing attempts may give more acceptable parameter values within the search space compared to the best-performing attempts.

Note that derivative-free optimization methods in general provide "asymptotic" solutions for complex functions. Thus it is reasonable to assume that BiteOpt gives an optimal solution with some implicit tolerance factor. Given a large enough function evaluation budget, BiteOpt usually does find an optimal solution which can be cross-checked with other solvers, but a solution of a new unexplored function must be treated as "asymptotically optimal".

Also note that in some problem areas like ESA GTOP problem suite the attempt budget should be as high as 1000 or more (beside using the BiteOptDeep depth of at least 6). At the same time, the iteration budget per attempt can be kept moderate (250000), compared to usual techniques used to solve these problems. Despite a large attempt budget, on a 8-core processor, this still allows one to get good (not necessarily best-known) solutions in a matter of minutes per problem.

Limitations

Rogue optimums may not be found by this method. A rogue optimum is an optimum that has a very small, almost undetectable area of descent, and is placed apart from other competing minima. The method favors minimum with a larger area of descent. The Damavandi test function is a perfect example of the limitation of this method (this test function is solved by this method, but requires a lot of iterations). In practice, however, rogue optimums can be considered as undesired outliers that rely on unstable parameter values: if such parameters are used in a real-world system that has a certain parameter value precision, a system may leave the "rogue" optimal regime easily. Another class of optimums the method cannot cope with well are "shadowed" optimums - the optimums that are located very close to opposite extremums.

To some degree, this method is immune to noise in the objective function. While this method was designed to be applied to continuous functions, it is immune to discontinuities, and it can solve problems that utilize parameter value rounding (integer parameters). This method usually can't acceptably solve high-dimensional continuous problems that are implicitly combinatorial (e.g., Perm, and Lennard-Jones atom clustering problems) as in such problems the global descent vanishes at some point and the method is left with an exponentially increasing number of local minima.

Also, problems with many competing minima without a pronounced global descent towards global minimum (e.g., Bukin N.6 problem) may not be solved acceptably as in most cases they require exhaustive search or a search involving knowledge of the structure of the problem. When the problem field requires one to locate such "rogue optimums", the best approach is to use a magnitudes larger attempt budget (preferrably using parallel computation like in the fcmaes library). With 1000 attempts and 250000 iterations per attempt budget, BiteOpt solves even the Bukin N.6 problem. It may seem excessive, but currently BiteOpt does not offer another way to solve such extremal multi-modal problems.

A difference between upper and lower parameter bound values should be specified in a way to cover a wider value range, in order to reduce boundary effects that may reduce convergence.

Tests have shown that in comparison to stochastic method like CMA-ES, BiteOpt's convergence time varies more from attempt to attempt. For example, on some problem CMA-ES's average convergence time may be 7000 iterations +/- 1000 while BiteOpt's may be 7000 +/- 3000. Such higher standard deviation is mostly a negative property if only a single optimization attempt is performed since it makes required iteration budget unpredictable. But if several attempts are performed, it is a positive property: it means that in some optimization attempts BiteOpt converges faster and may find a better optimum with the same iteration budget per attempt. Based on test2.cpp (2-dimensional) and test3.cpp (14-dimensional) test-sets, less than 0.9% of attempts require more than 3*sigma iterations, 54% of attempts require less than the mean. A typical probability distribution of percent of attempts/sigma is as follows (discretized, not centered around 0 because it deviates from the standard distribution, the mean corresponds to 0*sigma):

Traveling Salesman Problem (TSP)

BiteOptDeep is able to solve symmetric and asymmetric TSP problems even as large as 400-node ones, to wit