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].

2. Formal definition of the neighbourhood structure of a local search algorithm

The neighbourhood (denoted N(S)) of a current solution (denoted S) is a set of neighbouring solutions that is generated by the neighbourhood structure with the aim to enable the move from the current solution to a new and hopefully better solution [1].

At each iteration of a local search heuristic algorithm, the neighbourhood function that can be applied to the current solution S define a set of neighbouring solutions in the search space [2]. In other words, N(S) is a subset of the search space made of all solutions that can be obtained by applying the neighbourhood function to the current solution S.

Note that the neighbourhood function is also called local transformation in literature.

3. A simple example of neighbourhood structure

For instance, for the hybrid flowshop scheduling problem (HFSP) where there are parallel processing machines at each stage, a simple neighbourhood structure could be moving at each iteration a single job from its current processing machine and insert it in other positions in the production sequence of the current machine or insert it in a position in the production sequence of another parallel machine.

An important feature of the neighbourhood structures is the way of selecting the next solution from the neighbourhood. One could use first improvement or best improvement. First improvement selects the first improved solution as the next solution, while best improvement examines all the neighbouring solutions in the neighbourhood and selects the best solution among the neighbouring solutions.

Note that in the above example, the neighbourhood involves moving a single job, the neighbourhoods defined contain all the solutions that can be obtained from the current solution by moving any job and inserting it in the stated way.

4. More complex neighbourhood structures

To improve the performance of the local search heuristic algorithm when solving an optimization problem, more complex neighbourhood structures can be defined.

For instance, for the HFSP, the -interchange defines the neighbourhood in which the neighbouring solutions are obtained by allowing simultaneously the movement of a number of jobs to new positions in the production sequence of the current machine and to the positions in the production sequences of other parallel machines.

5. Other aspects

For many specific optimization problems, there are usually many more possible neighbourhood structure definitions than search space definitions. In general, there may be several plausible neighbourhood structures for a given definition of the search space.

Again, a good definition of neighbourhood structure based on a good understanding of the problems at hand. So it is always preferable to understand your problems well so that you can make the best use of the understanding and knowledge of the problem when defining the neighbourhood structure.

References

1. Błażewicz, J., Domschke, W., and Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93(1):1–33.

2.Glover, F. W., & Kochenberger, G. A. (Eds.). (2003). Handbook of metaheuristics (Vol. 57). Springer Science & Business Media.

3. Van Laarhoven, P.J., Aarts, E.H., Lenstra, J.K., 1992. Job shop scheduling by simulated annealing. Oper. Res. 40 (1), 113–125.

4. Steinhöfel, K., Albrecht, A., Wong, C.K., 1999. Two simulated annealing-based heuristics for the job shop scheduling problem. European J. Oper. Res. 118 (3), 524–548.

Welcome to visit the page of my publication where there are more articles on algorithms for optimization problems.

https://ningjoptalg.substack.com