Are metaheuristics ever practical for continuous optimization?

Question

All of the applications of metaheuristics that I can think of are for discrete optimization (usually combinatorial optimization) problems.

Are metaheuristics ever practical tools for continuous optimization problems?

I searched a bit on the web for this and found a few examples, but I get the sense that these examples are rather artificial and that metaheuristics are not usually a practical method for continuous optimization.

The exception might be the case of nonconvex, global optimization, in which case sometimes metaheuristics are used to find a good starting solution and then continuous optimization is used to find the nearby local optimum. But one could argue that this is really like solving a discrete problem—the problem of choosing which local optimum to target—rather than actually doing any continuous optimization.

Answer 1

I haven't seen any good use cases of metaheuristics for continuous variables optimization. That doesn't mean it's not possible, I just think it's not the right tool for the job. Particularly, all forms of Local Search (Tabu Search, Late Acceptance, Simulated Annealing) with real continuous variables feel like using a hammer on a screw.

That being said, there are interesting gray-area cases, such Investment Portfolio Optimization, which is about buying stock exchange assets. Each variable represents the percentage of an asset to buy. This would clearly be a continuous variable, except that practically we limited it in millis (so in 0.001 units): the motivation being that in the real world there's a minimum unit granularity to buy anyway. And that works ok, not great (but some investors actually use the example impl). And I believe it will improve with dedicated neighborhoods.

PS: Ironically, we coined the term for continuous planning for something completely different than continuous (variables) optimization.

Answer 2

Personally I use them all the time, regardless of variable type, typically for low-dimensional (<= 100 variables) black-box optimization problems of unknown structure where I want an approximate solution quickly.

For example, this solver uses a GA and accepts continuous and discrete variables:

https://support.sas.com/documentation/onlinedoc/or/132/hplso.pdf

In the continuous smooth world, if a method doesn't use derivatives, its effectiveness tends to decay like one divided by the square-root of the dimension for the same work per iteration; so I might be more focused on the number of variables as opposed to variable type. (Look at equations 3.10 define K(G) here (DOI link), though not used in GA's I believe they work probabilistically the same way. The dimension explodes and you cannot possibly keep pace. At best you have an underlying spanning set whose effectiveness degrades rapidly with dimension.)

However, to avoid being rudely laughed at, if you are publishing results, a basic rule of thumb is to apply the solver in your toolbox that matches your optimization problem closest. For example, if you are solving a TSP and have SAS/OPTMILP, don't use a GA. GA's assume almost nothing about the problem while a MILP solver is very specific on problem type. The more assumptions a solver makes about the problem and its structure, the more targeted/expeditious the algorithm design becomes.

Consider group theory (https://www.britannica.com/science/group-theory). It arises from 4 simple assumptions a child might understand (axioms) that result in volumes of complex implications and hours upon hours of mathematical fun. Never under estimate the power limiting assumptions in the hands of a motivated mathematician/developer:)

Of course, if you were on a desert island and had to code up a solver from scratch to find the best solution that day to stay on the island, metaheuristics start to look a lot more attractive, regardless of problem type. I.e. always take your pre-solve set-up time into account. If you spend 3 weeks setting things up to reduce the solve time from 3 hours to 3 minutes, not a clear win ... unless it is for a paper:)

Answer 3

Heuristics are useful to solve continuous optimization problems, in particular:

1. Large-scale problems, whatever their nature. Because even if the problem has nice properties (convexity, smoothness), its large scale may prevent the nice algorithms (for example, Augmented Lagrangian or Interior Point methods) to converge to quality solutions in reasonable running times.

2. Nonconvex problems. Because the nice algorithms evoked above generally fail to converge to global optima.

3. Nonsmooth problems. When computing derivatives is hard or time-consuming. For example, in the presence of black-box functions related to numerical simulations.

We use the term "heuristics" and not "metaheuristics" on purpose. At Hexaly, we don't like the prefix "meta" because it only refers in the mind of many to the zoo of search strategies employed to escape local optima and then to the major scientific abuse that resulted (see Kenneth Sörensen's saving paper about this). The "meta" ingredients - whose goal is to escape local optima when searching for solutions to discrete or nonconvex continuous problems - are not the hard part of the job when implementing heuristics to solve practical problems. In many cases, they are even not critical to getting high-quality solutions quickly. For example, have a look at this, this, this, or that.

Local/neighborhood search methods for combinatorial optimization have their counterpart in continuous optimization. They are called direct or random search methods. For example, the Nelder-Mead method is one of them. Like local search methods in combinatorial optimization, they are very useful in practice but suffer from a lack of understanding in theory. Mostly because understanding requires complex maths like smooth complexity analysis but also because they were discredited for years in academia, being considered as "cooking" (see Margaret H. Wright's nice paper on this).

At Hexaly, we work at integrating the "dirty" (heuristic) ones together with the "nice" (exact) ones for combinatorial and continuous optimization. We work to offer our users the best of both worlds because we know this is critical to getting the best answers in practice.

Answer 4

The authors of "Optimisation in Signal and Image Processing 1", in chapter 11 of their book Metaheuristics for Continuous Variables. The Registration of Retinal Angiogram Images (available on ResearchGate) discussed the various implementations of some well-known metaheuristic methods in the optimization of continuous variables.

In [2], which is one of the introductory papers in the Harmony search metaheuristic, the authors discussed the theoretical bases and the implementation of the new proposed metaheuristic.

1 Siarry, Patrick, ed. Optimisation in signal and image processing. John Wiley & Sons, 2013.

[2] Lee, Kang Seok, and Zong Woo Geem. "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice." Computer methods in applied mechanics and engineering 194.36-38 (2005): 3902-3933.

Answer 5

Metaheuristics for continuous global optimization is the only way to obtain good solutions when your problem is even of moderately high dimension. There are several examples in the literature. Our research group (but many others too) have successfully applied metaheuristics to solve large scale molecular conformation problems, optimal disk packing problems, space trajectory planning, and many many others.

The book I wrote with my colleague Marco Locatelli, Global Optimization: Theory, Algorithms and Applications, SIAM-MOS, 2013 / viii + 439 pages / Softcover / ISBN: 978-1-611972-66-5 http://bookstore.siam.org/mo15/ has plenty of pages devoted to different heuristics for continuous globopt as well as applications.

Answer 6

In some domains, metaheuristics are the most common way of optimising things. I have a bit of experience in water resource management, and using "common" optimisation tools is like a big word in these communities. Don't talk about simplex, interior point, branch-and-bound, or anything like this. Often, they don't have linear or convex models (nor of large size), but they could use linearisation techniques (many relationships could use piece-wise linear modelling instead of precomputed tables -- the latter being only useable within metaheuristics). I daresay metaheuristics are preferable for people not willing to invest time in modelling "properly" a given problem, but rather prefer spend time to build an algorithm (which is really fun, by the way!).

Relatedly, when you deal with multiobjective problems, using evolutionary methods brings you a lot of potentially good solutions for a subset of objective functions in exactly the same computational budget as solving the usual optimisation problem.

For instance, have a look at Reservoir Optimization in Water Resources: a Review. Sometimes, they also include simulation in the optimisation loop, which is harder to include with standard solvers; see Evaluation of stochastic reservoir operation optimization models for instance. However, this community also acknowledges the fact that metaheuristics are very hard to really understand, you never really have an idea of how good a solution is, whether progress remains to be made in the solving process Evolutionary algorithms and other metaheuristics in water resources: Current status, research challenges and future directions.

NB. I'm not a fan of metaheuristics, which means I'm a little bit biased.

Answer 7

The answer is: of course.

First, nonconvex, global optimization, is a huge and challenging area, and arguably one of the most interesting. If you limit the scope to finding a nearby local minimum in a continuous space, then the answer is an easy "no" almost by definition. But for finding a nearby local minimum in a discrete space a simple (discrete) local search is also sufficient, so no meta-heuristic needed.

Second, I would agree with the previous answers, in that the most direct application of meta-heuristics to continuous problems seems to be not very competitive. In metaheuristics you usually need to instantiate some problem-specific components such as local search neighborhoods, recombination operators, or constructive heuristics. In continuous optimization these components often are naturally given, e.g. an $\epsilon$-neighborhood in a local search for some fixed step size $\epsilon$, or a convex combination of two solutions. In this case you end up with a generic approach, that can easily beaten by one the more specific approaches to continuous optimization, that use the extra structure available (e.g. gradients, dynamic steps sizes, etc.). This is probably why "classic" meta-heuristics such a Tabu Search for continous optimization are rare (although Glover & Laguna, Tabu search has two short sections 7.7 and 8.8.1 on continuous optimization).

Finally, two examples of what I believe to be successful meta-heuristic strategies for continuous optimization:

• Continuous GRASP (C-GRASP): there's a chapter "GRASP for continuous optimization" in Ribeiro, Resende, Optimization by GRASP including some applications.

• Covariance matrix adaptation evolution strategies (CMA-ES). Hansen (2016) is a good introduction. Citing Whitley (2018), CMA-ES "have now replaced genetic algorithms for real-valued parameter optimization". Arguably, they borrow some good ideas from continuous optimization, but still rely on evolutionary principles.

Answer 8

Yes, it is !! Especially that there is no other choice for solving such problems.

I suggest looking at the following new paper:

Nidhal Kamel Taha El-Omari, “Sea Lion Optimization Algorithm for Solving the Maximum Flow Problem”, International Journal of Computer Science and Network Security (IJCSNS), e-ISSN: 1738-7906, DOI: 10.22937/IJCSNS.2020.20.08.5, 20(8):30-68, 2020.

You can also find this paper in the following address:

https://www.researchgate.net/publication/344324283_Sea_Lion_Optimization_Algorithm_for_Solving_the_Maximum_Flow_Problem