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)?