How to generate neighbors in hill climbing algorithm?

Question

Hill climbing seems to be a very powerful tool for optimization. However, how to generate the "neighbors" of a solution always puzzles me.

For example, I am optimizing a solution $(x_1, x_2, x_3)$. Here $x_1$ is in range $(0, 0.1)$, $x_2$ is in range $(0, 100)$, $x_3$ is in range $(0, 1000000)$. What's the best way to generate "neighbors"? I can't really pick a "step size" here, because a step size of 1 is huge to $x_1$, but very minor to $x_3$.

What is the best generic way to generate "neighbors" in hill climbing algorithms?

Answer 1

Vincent's solution will get you over the first hurdle. You might still be wondering how to select the step size even if all the dimensions have the same range. In that case it helps to understand the behavior of your function so you can select an appropriate value. Another way is to adaptively set the step size based on gradient (tread lightly if the function is changing a lot).

This paper might have some interesting ideas too: On a Hill-Climbing Algorithm with Adaptive Step Size: Towards a Control Parameter-Less Black-Box Optimisation Algorithm

Answer 2

The easiest (and safest) is to reparametrize your problem so that all parameters have a comparable range, say [0,1].

Alternatively, you can use a different step size for each parameter.