1
$\begingroup$

A Motivating Example

The Travelling Salesman Problem (TSP) is a classic one where a "salesman" tries to minimize their length of travel (i.e., distance travelled) to a number of destinations (e.g., a plane flying along a flight route).

The TSP can be solved using a variety of techniques such as dynamic programming, simulated annealing (SA), or genetic algorithms.

In R, the optim package has a method called SANN that performs simulated annealing for a given problem of interest. The example within the documentation is the TSP using the eurodist dataset of major European cities.

Typically we want to run SA with a large number of iterations (iters) and a high temperature ($T$). The idea is that at high $T$, the search is purely random, exploring lots of solutions in the search space. Randomness decreases as $T$ is lowered and the search tends to exploit good solutions.

Running the example in R several times (since SA is stochastic), as well as increasing both iters and $T$, the maximal distance travelled changes a bit, but usually not by much. However, the actual permutation of visited cities does change quite substantially as it is almost always the case that a global optimum is never found (only a local one).

SA and its relatives are useful because they can find "good enough" solutions in very little time.

Question

If the actual permutation changes quite substantially, why is SA a "good" approach to employ at all? Suppose, in some crazy world, that airlines actually used SA to determine flight paths on a regular basis. Surely, because the permutation is often not a global solution, some other approach ought to be employed.

Clarification

"Good" stochastic algorithms should be well-behaved when run multiple times. This is certainly the case for real parameter optimization, but not for combinatorial problems like the TSP. Why is this the case?

$\endgroup$

2 Answers 2

1
$\begingroup$

I would say that simulated annealing is a good approach because it can find pretty good (or even sometimes optimal) solutions to some problems, such as travelling salesman for many cities, that are too large to solve by brute force methods. For large problems, and in particular problems with local minima, it might be practically impossible to be sure that you have the optimal solution. So the algorithm is good in the sense that it gives you a decent answer most of the time, which is not going to be the case for a brute force search.

As for your clarification question, I'm not sure that it's always the case for "real parameter optimization" that stochastic algorithms will be well-behaved across multiple runs. I assume by "well-behaved" you mean that it will give more or less the same answer every time? It is definitely possible to get stuck in a local minimum, and thus get different answers from different runs. Though I would say that an important part of using any stochastic optimisation algorithm is to run it many times, to get an idea of the variation.

$\endgroup$
1
  • $\begingroup$ Thanks. Yes. By "well-behaved", I mean performs well, showing small variation from one run to the next. $\endgroup$ Feb 27, 2022 at 1:19
0
$\begingroup$

The goal of SA is not to give you the global solution (in fact you can't even know if there is one "global solution" .. because in order to know it you should be able to calculate all the distance travalled for any possible permutations ... and the point is that this is not possible in a reasonable time - reasonnable regarding the human life duration at least !-), but to give you a rather good solution. The fact that it doen't give allways the same solution is not an issue, because it is the core of the algorithm,and what makes it efficient. And,as far as I know, and as long as there is no quantic computers, amost all good algorithms for this kind of problem are stochastic (to be honnest, I don't know if there are competitive deterministc algorithms .. may be someone could tell us that ?).

$\endgroup$
2
  • 1
    $\begingroup$ Disagree on your first sentence. SA is an approach to estimate the global solution (as opposed to a local soln) $\endgroup$
    – user20650
    Feb 26, 2022 at 13:57
  • $\begingroup$ @user20650 you're fully right, it is an approach to estimate the global solution, what I've tried to say is that it will not, in most case, give the global solution .. And when I use SA, my goal is not to find the global solution, because I know I won't, , but a pretty good solution .. $\endgroup$ Feb 28, 2022 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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