Justification of simulated annealing versus random search 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?
 A: 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.
A: "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.
