Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

1. Neighborhood Overview

In the function optimization problem in the distance space, the usual definition of neighborhood is a sphere centered on a point (neighbors).

2. Local neighborhood search

The goal is to find the optimal solution to a problem. First, find A feasible solution (initial solution, which may not be the optimal solution) in the solution, then explore in the vicinity of the initial solution, find the optimal solution in the initial solution neighborhood is better than the initial solution (let as solution A). Then, it will explore in the vicinity of solution A, and find the optimal solution in the neighborhood of solution A that is better than solution A (let’s call it solution B), and continue to explore until the end of the cycle condition is reached, and output the final solution.

3. Explain with examples

3.1 Problem Description

Local search algorithm is used to solve the symmetric travel salesman path problem of five cities, that is, starting from point A, passing through all nodes, finally returning to point A, and finding the path with the shortest distance. A,B,C,D and E respectively represent five cities, and node A is the starting city.

Distance weight matrix DDD is shown as follows:

Schematic diagram of five city node paths:

3.2 Solution Process

3.2.1 Step 1: Generate the initial solution

Here the initial solution is generated in a random way (it can also be generated in other ways),

The initial solution is xBest =(ABCDE) xBest =(ABCDE) xBest =(ABCDE), and the current optimal (short) path length f(xBest)=45f(xBest)=45f(xbest)=45

Neighborhood mapping is defined as 2-OPT (two-element optimization) to swap the location of two cities, and city A is selected as the starting point.

3.2.2 Step 2: First Search

Full neighborhood search is used here, that is, the neighbors of the current solution are found to compare the size. The neighborhood set found in the first search is:

N(xbest)N(xbest)N(xbest) N(xbest) = {(ABCDE), (ACBDE), (ADCBE), (AECDB), (ABDCE), (ABEDC), (ABCED)}

These neighborhoods are obtained by alternating the initial solutions and the initial solutions (ABCDE)(ABCDE)(ABCDE) in pairs

Note: City A is not changed because A is A fixed starting point and cannot be changed in order

The corresponding objective function is f(x)f(x)f(x)={45, 43, 45, 60, 60, 59, 44}

Xbest =xnow=(ACBDE) xBest =xnow=(ACBDE)

3.2.3 Step 3: Perform the second search

The neighborhood set found in the second search is:

N(xbest)N(xbest)N(xBest) ={(ACBDE), (ABCDE), (ADBCE), (AEBDC), (ACDBE), (ACEDB), (ACBED)},

Corresponding to the objective function is f (x) f (x) f (x) = {44, 43, 45, 59, 59, 58, 43}

Xbest =xnow=(ACBDE) xBest =xnow=(ACBDE) xBest =xnow=(ACBDE)

The search is then repeated until the end condition is met.

We can see that the optimal solution becomes the previous optimal solution, which is one of the limitations of local search.

4. Local search features

  • It is simple and easy, but cannot guarantee global optimality (it may find local optimal solution, so this algorithm cannot jump out of local optimal solution).
  • Local search mainly depends on the selection of the starting point and the structure of the neighborhood (the starting point is selected near the local optimal solution, and the local optimal solution is found after several iterations)
  • To get a good solution, different neighborhood structures and different initial points can be compared.
  • If you choose enough initial points, you can always calculate the global optimal solution (try again)