Local search (Hill Climbing) scope and definition

Question

I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-queens puzzle to illustrate the algorithm working, he stated that in it a queen can only move one row up or down, so for example in a column with the following configuration:

In the first iteration the queen can only move to either rows 4 or 6 (8 rows, 0-based index), then in the next iteration it would be stuck in a local maxima because neither row 3 nor 7 have values lower than 14, so the algorithm would then proceed to the next column or terminate. He argued that even tough a queen can legally move directly through all the rows of its column doing so would make the algorithm fall of the concept of "Local search", because a local search move is limited to only one of its closest neighboors per time/iteration.

I found this weird because it appears to me that such a limitation greatly reduces the usefulness of hill climbing (in the 8-queen problem it makes the success rate abysmal). So I would like to know what's the correct/formal definition of local search and hill climbing, should it always be constrained to the closest neighboor? what constitute a closest neighboor? I would especially appreciate some book references.

Answer 1

Local search and hill climbing assume that you have defined a notion of "neighbor" and have defined an objective function. It's up to you to define those for your particular application. As you have noticed, some choices of the "neighbor" relation might make local search more effective or less effective.

In the 8-queen problem, there are multiple ways you could define the notion of "neighbor". One option is to treat two configurations as neighbors if you can get from one to the other by moving one queen one step; then the example in the question shows that local search with this notion of neighbor might get stuck. That is a consequence of defining "neighbor" in a particular way as much as a consequence of using local search, and is not fundamental to the notion of local search. Nothing prevents you from defining "neighbor" differently. For instance, one alternative is that you could consider two configuration neighbors if you can get from one configuration to the other by moving one queen any number of steps in a single direction. That might have different properties.

What is fundamental is that local search and hill climbing can risk getting stuck in a local minimum (where all neighbors are worse than your current location, but you're not in a global minimum). The likelihood of this may depend on the particular problem you are working with, the specific notion of neighbor you choose, and which local search method you use. Hill climbing is particularly susceptible to local minima; other methods are designed to try to reduce the risk of local minima.