2

I have a set of 16 integer parameters to optimize. The parameter space is too big for an exhaustive search, so I am using simulated annealing instead.

I think my simulated annealing works - it finds a good solution relatively quickly, and quicker on average than random search.

But how can I know for sure whether simulated annealing "added" anything beyond the random search? Is there any objective criterion to justify whether it is "worthwhile" to use a simulated annealing instead of a random search?

user2398029
  • 63
  • 9
  • Are you looking for an informal "this is probably worth it", or some kind of formalized hypothesis test? The typical first thing to do would be to plot the quality of the best solution so far as a function of time for a few random runs (or maybe the quantiles / means+stds / etc of a set of runs). – Danica Jan 26 '16 at 05:17
  • I'm more looking for a "this is probably worth it" kind of criterion. – user2398029 Jan 26 '16 at 05:38

2 Answers2

4

A very reasonable thing to do to just get a sense of "this is probably better," rather than any kind of formalized hypothesis test or anything, is to just plot the performance of the two methods over time.

Here's an example of a similar kind of plot from one of my papers:

Here the problem setting is slightly different, but you can think of the horizontal axis as being roughly time and the vertical as being roughly solution quality; lines are the mean of 10 runs, transparent fills are the standard errors. This is a quick check that clearly the four "APPS"/"AAS" methods are about the same, "LSE" is somewhat worse, and "Unc" and "Rand" are considerably worse. It also allows us to see that "Unc" starts off somewhat slower compared to "Rand", but "Rand" levels off more quickly.

When the amounts vary more, and especially if you're comparing fewer methods, it might be more informative to plot, say, 10%, 50%, and 90% quantiles rather than means + standard errors. There are also methods like "functional boxplots" that can be helpful.

Danica
  • 21,852
  • 1
  • 59
  • 115
  • It would be helpful if you translated the acronyms and abbreviations to the names of the methods so it is more clear what exactly does the plot show. – Tim Jul 05 '16 at 13:31
1

"Random search" is a very broad term and could very well include simulated annealing, as it is a randomized search algorithm.

However, a random-search algorithm that just samples around the currently best sample can easily get stuck in local optima if such exists. The ability to escape from local optima is the main strength of simulated annealing, hence simulated annealing would probably be a better choice than a random-search algorithm that only samples around the currently best sample if there is an overhanging risk of getting stuck in a local optimum.

HelloGoodbye
  • 534
  • 4
  • 10