13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think there has been quite some work done on evolutionary algorithms for continuous optimization. A term I have come across is "real-coded genetic algorithms". Have to admit, though, that I am no expert at all. $\endgroup$ – Sune Jun 24 at 11:14
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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:)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Well... afaict, ... and I'm not [by any means] an expert on this issue -- but [actually took a few (that's to be read as: two) classes on signal and image processing], from what I can tell -- in recent years, "deep learning" replaced "metaheuristics" as a "global optizimation tool" in the respective domains. $\endgroup$ – fbahr Jun 24 at 18:39
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So in that case are the decision variables discretized, or do the metaheuristics operate on the continuous variables directly? $\endgroup$ – LarrySnyder610 Jun 24 at 23:51
  • 1
    $\begingroup$ All variables are considered as continuous, I've yet to see a kind of discretisation there. There is some kind of intelligence in the way solutions are combined in an evolutionary metaheuristic, but that's it (the basic way is to average the two values, but I remember seeing more complicated schemes). $\endgroup$ – dourouc05 Jun 25 at 2:08
  • $\begingroup$ Metaheuristics do not exclude code reuse nor proper modeling. As OptaPlanner, LocalSolver and many other production metaheuristic solvers show, that's a false dichotomy. There is indeed a subculture in many sectors of writing these algorithms themselves (NIH syndrome), but that's diminishing rapidly as the production constraints solvers have matured and became more flexible. $\endgroup$ – Geoffrey De Smet Jun 25 at 9:10
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "The answer is: of course." -- but the rest of your answer mostly argues that MHs for continuous optimization are the exception rather than the rule -- am I interpreting right? $\endgroup$ – LarrySnyder610 Jun 26 at 2:53
  • 1
    $\begingroup$ @LarrySnyder610 Yes, the "of course" has to be read with a grain of salt, it mirrors "ever practical". ;) $\endgroup$ – Marcus Ritt Jun 26 at 11:12
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for the reference, Fabio; I am curious, are these really metaheuristics (evolutionary algorithms: how would a gene look like? local search: a neighborhood would be continuous, right?), or "just" heuristics? $\endgroup$ – Marco Lübbecke Jun 28 at 8:52
  • 1
    $\begingroup$ also, I would be cautious with statements like "the only way". I am not an expert in this area, but as far as I gather from colleagues, (principally) exact solver made great progress recently. $\endgroup$ – Marco Lübbecke Jun 28 at 8:54
  • 1
    $\begingroup$ Dear Marco, I perfectly agree with you that exact solver have made great progress Indeed, (sorry if it looks like advertisment...) in our book o Global Optimization, more than one half is devoted to exact methods. However, when your problem is "unstructured" and/or very large, exact methods are doomed to fail. $\endgroup$ – Fabio Schoen Jun 29 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.