The Neighbourhood Structure of A Local Search Heuristic Algorithm

Definition, examples, and some important points

Photo by Mahreen Sarwar on Unsplash

When using a local search heuristic algorithm to solve an optimization problem, the two first basic elements of the algorithm that need to be defined are the search space and the neighbourhoods structure.

In the previous article, the definition of the search space of a local search algorithm was introduced. In this article, I will introduce the definition of the neighbourhood structure, and provide some examples to illustrate the neighbourhood structure definition of a local search algorithm when using it to solve different optimization problems.

1. A beginner’s definition on neighbourhood structure of a local search algorithm

The neighbourhood structure of a heuristic algorithm can simply be described as a way to obtain new solutions from existing solutions.

The performance of a local search algorithm is directly affected by two factors in the neighbourhood structure, i.e. the definition the neighbourhood function, and the way of selecting the next solution from the neighbourhood [1].

Neighbourhood structures are usually defined by first choosing a neighbourhood function, which is usually a simple type of transition, to obtain a new solution from a given one, and then defining the neighbourhood as the set of solutions that can be obtained form a given solution in a single transition [3][4].