How to implement the details of shotgun hill climbing to make it effective?

Question

I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems to be the best fit, as I have no clue how the best start value can be found.

But there is not a lot of information about this type of algorithm except the rudimentary idea behind it:

[Shotgun] hill climbing is a meta-algorithm built on top of the hill climbing algorithm. It iteratively does hill-climbing, each time with a random initial condition $x_0$. The best $x_m$ is kept: if a new run of hill climbing produces a better $x_m$ than the stored state, it replaces the stored state.

If I understand this correctly, this means something like this (assuming maximisation):

x = -infinity;
for ( i = 1 .. N ) {
  x = max(x, hill_climbing(random_solution()));
}
return x;

But how can you make this really effective, that is better than normal hill climbing? It is hard to believe that using random start values helps a lot, especially for huge search spaces. More precisely, I wonder:

• Is there a good strategy for choosing the $x_0$ (that is implementing random_solution), in particular knowing (intermediate) results of former iterations?
• How to choose $N$, that is how many iterations are needed to be quite certain that the perfect solution is not missed (by much)?

Answer 1

The general idea behind doing multiple climbs is to try to avoid local optima. This is the reason shotgun climbing might work better than just a plain hill climbing method.

Usually one starts with a random value. On the other hand if one can guess something better, that can be used as a initial value as well. If there is no knowledge of what a good start value should be, it makes sense to use a random one.

The suitable value for $N$ varies. Usually one has to define a stopping criterion. A suitable criterion might depend on your specific domain. For example, if for some small number of moves you don't improve your solution at all, you stop. In general, you don't know -- you are using heuristics and they give you no guarantees. You might want to even determine a suitable $N$ experimentally.