7

I have been looking in detail into one of the many "meta-heuristic" optimization algorithms and became suspicious at how well it appeared to perform (compared to other methods like Nelder-Mead, Multi-Directional search, and Spiral optimization) on a "pathological" test function, Rastrigin.

If any of you good people are using the Rastrigin function in your work, can I ask you to try "shifting" the origin so that it sits at e.g. (2,3,5) in 3D, and see if it causes any algorithms you are using to perform adversely? My suspicion is that some (many?) algorithms have a tendency to favour the origin as a solution!

Suffice to say the methods I mentioned by name earlier can cope with the shift in origin as well as they do without it.

[EDIT] I am currently "hardening" all my test functions with a minimum at the origin, shifting each numbered coordinate variable by the coordinate index.

[EDIT] Regarding the paper linked in @Lysistrata's answer below. It turns out that not only does the method I hinted at above appear on the "naughty list" (the red items in Table 3), but its author and his associates are identified as the source of "20 of the 47 methods that contain centre-bias"!

[UPDATE] It was already on the cards (because of suspicious visual "artifacts" when viewing operation on 3D problems, and the absence of any useful mathematical description of its "mechanism"), but following the valuable contributions in these answers and the references contained, I have now dropped the offending algorithm from my project.

m4r35n357
  • 215
  • 6
  • And many test problems are (nonlinear) least squares problems, which is a special structure, many of which have zero residual at the global optimum, i.e., optimal objective value of zero, on a problem in which the objective is structurally nonnegative. The Rosenbrock banana function https://en.wikipedia.org/wiki/Rosenbrock_function is such an example. – Mark L. Stone Mar 17 '24 at 12:47
  • @MarkL.Stone I do not really understand what you are saying here (for example I have not come across the term "structurally nonnegative" - I am not a mathematician). Can you elaborate? FWIW I do not consider a zero minimum value to be a problem, just the coordinates. Incidentally I use multidimensional Rosenbrock routinely in my "work" (it is not paid work!), and consider it a very good test! – m4r35n357 Mar 17 '24 at 20:25
  • Nonlinear least squares is the sum of squares, each of which must be nonnegative, and that structure means the objective function can't be negative (hence structurally nonnegative). So if an objective value of zero is achieved, it must be a global optimum. It's not necessarily that Rosenbrock is a bad test function, but it's a very special function, with special properties which might make certain algorithms perform well on it, but not necessarily on more general nonlinear functions. – Mark L. Stone Mar 17 '24 at 21:37
  • @MarkL.Stone OK thanks I get that now. I've always understood that Rosenbrock was designed to be challenging. However I know it allows Nelder-Mead to do well. OTOH the "meta-heuristics" really struggle, as does Multi-directional search. My take is I see it as a useful example of a non-trivial unimodal function. – m4r35n357 Mar 17 '24 at 22:03
  • Some methods for least squares problems (such as the Gauss-Newton and Levenberg-Marquardt methods) depend on approximations to the Hessian of the objective function which work very poorly when the optimal solution has a sum of squares that is very large. Many commonly used test functions don't have this feature. – Brian Borchers Mar 18 '24 at 20:46

2 Answers2

10

Your suspicion that many algorithms rely on specific position of the global optimum is well founded - even if it’s by symmetry only.

Most of the classical test functions found in the literature suffer from a number of limitations and weaknesses, that are often exploited by global optimization algorithms:

Initialization Bias (Central Bias): many of the benchmark functions in the SciPy test suite have bounds that are symmetric with respect to the global optimum (i.e., the global optimum is exactly in the middle), or they have one or more optima on the bounds.

Axial and Directional Bias: Many mathematical functions used for benchmarking exhibit some alignment in the structure, and in particular valleys containing local minima.

Rotational Invariance: Some mathematical functions, such as Schaffer’s F6 function, exhibit rotational symmetry.

Regularity: Many elementary benchmark functions have local minima spread in regular patterns.

I have adopted the same approach on my large set of benchmarks:

http://infinity77.net/go_2021/

for “standard” benchmark functions:

http://infinity77.net/go_2021/scipy_extended.html#scipy-extended

Infinity77
  • 391
  • 3
  • 4
  • Thanks for your reply - plenty to read there! It is encouraging that I am not the only one who has been motivated to "shift the origin" in one way or another. – m4r35n357 Mar 17 '24 at 10:52
  • Incidentally, I was genuinely composing my answer at the same time as you were replying! I will leave it there for now . . . – m4r35n357 Mar 17 '24 at 11:14
  • 1
    BTW the paper mentioned in your second link is excellent IMO (and open access) - https://www.researchgate.net/publication/4170894_Novel_composition_test_functions_for_numerical_global_optimization – m4r35n357 Mar 17 '24 at 12:13
  • There is another very subtle bias that can creep in. Some stochastic search procedures rely on Gaussian distributions to generate new solutions. Symmetric benchmark functions could be biased in favor of these operators.

    The COCO benchmark suite uses symmetry breaking transformations to avoid those biases. For more details see: Finck et al, Real-Parameter Black-Box Optimization Benchmarking 2010: Presentation of the Noiseless Functions https://numbbo.github.io/gforge/downloads/download16.00/bbobdocfunctions.pdf

     – Lysistrata Mar 20 '24 at 10:59
4

The center bias problem is definitely something more practitioners should be aware of. This recent paper is worth reading.

Jakub Kůdela, The Evolutionary Computation Methods No One Should Use https://arxiv.org/abs/2301.01984

From the abstract: We show that more than half (47 out of the 90) of the considered methods have the center-bias problem. We also show that the center-bias is a relatively new phenomenon (with the first identified method being from 2012), but its inclusion has become extremely prevalent in the last few years.

COCO (Comparing Continuous Optimizers) is another good benchmark suite to consider. https://github.com/numbbo/coco

It has the useful feature of producing LaTeX ready performance plots.

There are about 260 sets of results that you can compare to your results. https://numbbo.github.io/data-archive/bbob/

Post-processed results are also available at: https://numbbo.github.io/ppdata-archive/

Lysistrata
  • 329
  • 1
  • 7
  • Fascinating paper! Suffice to say the algorithm that prompted my OP appears as one of the culprits! – m4r35n357 Mar 19 '24 at 09:43
  • To add to that, so does the author! In this context, your avatar is cruelly pertinent ;) – m4r35n357 Mar 19 '24 at 10:31
  • 1
    From the linked paper: "And new methods are emerging at an ever-increasing rate. It is becoming clearer that there is more creativity being spent naming these 'novel' methods, than in making sure they contain anything new computation wise." An astute observation! – whpowell96 Mar 19 '24 at 13:09
  • 1
    There is another wry, scathing look at metaheuristics in: Kenneth Sörensen, Metaheuristics—the metaphor exposed, Intl. Trans. in Op. Res. 22 (2015) 3–18. For example: A recent marketing strategy is to maintain social media website profiles for “novel” methods. The reader might, for example, be interested to learn that the intelligent water drops algorithm officially “likes” the galaxy-based search algorithm. – Lysistrata Mar 20 '24 at 11:01
  • Yep. It is a circus all right! Surely now it is time for someone with the necessary skills to put the "mathematics" behind some these methods properly under the microscope ;) – m4r35n357 Mar 20 '24 at 12:21