5
1

I am familiar with many meta heuristic algorithms (including Simulated Annealing, Tabu Search, Genetic, Ant Colony, PSO , Bee Colony) I always have a fundamental question about choosing appropriate algorithm based on problem domain and its characteristics. Which properties I should know about the problem and how can I decide which algorithm is the best choice? I really appreciate any recommendation.

asked 08 Jun '13, 22:52

esmaeil's gravatar image

esmaeil
5114
accept rate: 0%

edited 08 Jun '13, 22:57


It is difficult to answer your question precisely as it is quite broad. I would advise you to look into the scientific literature to check which metaheuristic worked well on similar problems. If it worked well on a similar problem, you can modify this algorithm to suit your problem. The most basic versions of each seldom work well on complex problems so if you have any previous experience in applying any metaheuristic to other problem you should start with what you know.

Implementation issues are more important than the choice of metaheuristic metaphor you wish to refer to when designing the metaheuristic. For general advice you can refer to this book, written by E.-G. Talbi.

link

answered 09 Jun '13, 01:38

ORNinja's gravatar image

ORNinja
1311
accept rate: 0%

1

In my experience, adding a single constraint to a use case can change which is the best metaheuristic (although the original one still performs very well).

In practice, people try out a few quick metaheuristic implementations on a few datasets (often too small!) in realistic time, take the best and then heavily invest in optimizing and tweaking that best one. If - months later - another metaheuristic is used, that best metaheuristic became a self-fulfilling prophecy: because all the other code (parameters, neighborhood selection, ...) is tweaked for that best metaheuristic, it wins.

(09 Jun '13, 08:08) Geoffrey De ... ♦

It's impossible to predict in advance, for your use case, your constraints and/or your time limit.

Implement all the metaheuristic algorithms (correctly - I might add) and use a Benchmarker to find the best metaheuristic with the best parameters for your use case, your constraints and your time limit.

link

answered 09 Jun '13, 07:53

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
accept rate: 6%

edited 09 Jun '13, 07:57

If you're using Java: OptaPlanner has such a open source benchmarker. It generates a benchmark report with graphs and tables. Here's an older version of such a benchmark report. I use the Benchmarker regularly to optimize use cases and to test new metaheuristics (as shown here).

(09 Jun '13, 07:57) Geoffrey De ... ♦
1

Note: Generally, all (respectable) metaheuristics do give relatively good results on almost any use case: not choosing the best metaheuristic isn't the end of the world. Exceptions define the rule ;-) For example: if the construction heuristic is absolutely terrible (such as just random construction), a fast stepping metaheuristic such as Simulated Annealing and Late Acceptance will dwarf a slow stepping one such as Tabu Search.

(13 Jun '13, 03:38) Geoffrey De ... ♦

The short answer is that the choice of metaheuristic should be guided by the availability of implementations for similar problems rather than by a mapping between problem class and metaheuristic class. That mapping is most likely uninformative.

Here is some more detail:

For algorithm A to outperform algorithm B, algorithm A must, with mathematical certainty, either:

  • use problem-specific information more efficiently than B; or
  • waste less effort trying to acquire that information.

This is a corollary of extensions of a rather nuanced theorem referred to as the "No Free Lunch" theorem.

Therefore, the first question to ask is: what characteristics of your problem can be exploited to produce shortcuts? There are two main places to look:

  1. The implementation of the hill climbing component (the local search part)
  2. The schedule for adjusting the emphasis between local and global search

The first item is mostly independent of the choice of metaheuristic. The second one is not independent of the choice, but only because it needs to be translated differently to the context defined by each metaheuristic. That translation is the secret sauce that makes some implementations succeed while others fail.

Therefore, your best bet is to find in the literature a community of people who have solved problems similar to those you are interested in. Then follow their choice of metaheuristic and adapt their algorithms to exploit what is novel about your problem. Using an alternative to their choice is an easy way to get a paper published, but those papers are rarely very insightful, since their main contribution is translating the same structure to a different context.

link

answered 12 Jun '13, 23:06

Leo's gravatar image

Leo
1.1k17
accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×29
×28
×13
×5

Asked: 08 Jun '13, 22:52

Seen: 9,644 times

Last updated: 13 Jun '13, 03:39

OR-Exchange! Your site for questions, answers, and announcements about operations research.