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

1. Taboo search

Tabu search is the promotion of local neighborhood search algorithm. “Tabu” refers to the prohibition of repeating the previous work, so as to jump out of the local best advantage. Local neighborhood search algorithms are explained here (Intelligent Algorithms – Local Neighborhood Search Algorithms)

Tabu search algorithm can be popularly understood as: A group of rabbits to to reach the highest mountain, from the starting point (initial solution) began to explore, every step, find they told each other, in the current on the top of the marker (forbidden), and then to discuss the next step where to find, in a short period of time they will not repeat again to explore have already made the mark place, just the way they repeat just continue to explore.

2. Algorithm flow chart

3. Examples

3.1 Problem Description

Please use tabu search algorithm to solve the symmetric travel salesman path problem of five cities, that is, start from point A, pass through all nodes, and finally return to point A to find 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:

The graphical relationship of the five cities is shown below:

3.2 Solution Process

3.2.1 Step 1: Generate the initial solution

Firstly, the tabu length is 4, the tabu object is the change of simple solutions (the same solution cannot appear continuously), and 4 neighborhood solutions in the current solution neighborhood are required to be searched as candidate solution sets each time.

Initial solution: Xnow=X0=(ACBDE)Xnow=X0=(ACBDE)Xnow=X0=(ACBDE)

The distance corresponding to the initial solution is: f(x0)= 43F (x0)= 43F (x0)=43

Initialize the tabu table. 45)}

3.2.2 Step 2: First Iteration

Xnow = (ABCDE) Xnow = (ABCDE) Xnow = (ABCDE), f (Xnow) = f (Xnow) 45 = 45 f (Xnow) = 45

Taboos (the last item is taboos length) : HHH={(ABCDE; 45. 4)}

Generate the candidate solution set: CanN(xnow)Can_N(xnow)CanN(xNOW)={(ACBDE; 43), (ADCBE; 45), (ABEDC; 59), (ABCED; 44)}.

The current optimal solution is: Xnext=(ACBDE)Xnext=(ACBDE)Xnext=(ACBDE)

3.2.2 Step 3: The second iteration

Xnow = (ACBDE) Xnow = (ACBDE) Xnow = (ACBDE), f (Xnow) = f (Xnow) 43 = 43 f = 43 (Xnow)

The updated taboos are as follows: HHH={(ABCDE; 45. 3), (ACBDE; 43. 4)}

Generate a new candidate solution set: CanN(xnow)Can_N(xnow)CanN(xnow)={……………… }.

The current optimal solution is: Xnext=(……) Xnext = (…) Xnext = (…)

Repeat until the end of the loop condition is reached

4. Aspiration Criteria

  1. Based on the rule of evaluation value, if there is a solution whose target value is better than any of the previous best candidate solutions, amnesty can be granted.
  2. Based on the rule of least error, if all objects are taboo, amnesty a solution with the lowest evaluation value;
  3. Influence-based rules allow amnesty for objects that have a large impact on the target value.

5. Determination method of candidate set

  1. Several neighbors with the best target value are selected from the neighborhood.
  2. Select several optimal target values from some neighbors in the neighborhood.
  3. Random selection;

6. Algorithm termination rule

  1. If the number of steps is determined to terminate, the effect of the solution cannot be guaranteed, the current optimal solution should be recorded;
  2. Frequency control principle, when the frequency of a solution, target value or element sequence exceeds a given value, the calculation is terminated; (Too many occurrences)
  3. Objective control principle: if the current optimal value does not change within a given number of steps, the calculation can be terminated.