​

The article directories

  • 1. Overview of TSP issues
  • Second, tabu search algorithm
    • 1. Basic principles
    • 2. Parameter Settings
    • 3. Algorithm features
    • 4. Algorithm flow
  • Three, MATLAB program implementation
    • 1. Problem description
    • 2. Tabu search algorithm solution
    • 3. Simulation results

1. Overview of TSP issues

Traveling salesman problem (TSP), also known as salesman problem and salesman problem, is the most basic route problem. The problem seeks the minimum path cost of a single traveler from the starting point, through all given demand points, and back to the starting point. The earliest mathematical model of the traveling salesman problem was proposed by Dantzig et al. (1959). The traveling salesman problem is a special case of the vehicle routing problem (VRP).

Second, tabu search algorithm

1. Basic principles

Marks the local optima solutions or processes that have been solved and avoids them in further iterations. The disadvantage of local search is that it searches a certain local area and its neighborhood too much, which leads to blindness. In order to find the global optimal solution, tabu search is to consciously avoid a part of the local optimal solution found, so as to enlarge the search area.

Metaphor: When rabbits find Mount Tai, one of them will stay here and the others will go elsewhere to look for it. In this way, after a long circle, a comparison of the several found peaks, Everest stood out.

2.2 Algorithm Process

Step1: Give tabu table H= null set and select an initial solution xNOW;

Step2: when the stop rule is satisfied, stop the calculation and output the result; Otherwise, select the untabu candidate set Can_N(XNOW) in the neighborhood N(XNOW) of XNOW; Select a solution with the best value in Can_N(xNOW) xnext, xnow= xNext; Update the historical record H, save f(xnow), and repeat step2;

Step3: Select the minimum (large) value as the solution among the stored f;

​

  1. When the rabbits find Tarzan, one of them will stay here and the others will look elsewhere. When the rabbits look again, generally will consciously avoid Tarzan, because they know, here has been looking for, and there is a rabbit watching. This is the meaning of tabulist in tabu search.

  2. The rabbit that stays in Taishan generally does not settle there, it will return to the army that seeks the highest peak after a certain time, because this time has had many new news. This is called “Tabu Length” in tabu search.

  3. , if in the process of search, taishan rabbit hasn’t come back, but found the whole is a low place such as the north China plain, the rabbits had to consider selected once again mount tai, mount tai, after all, there is also a good height, that is to say, when a rabbit left local superiority too outstanding, more than “the best so far” and “state, To consider the place regardless of whether there are rabbits left behind. That’s aspiration criterion.

These three concepts are tabu search and general search criteria the most different place, algorithm optimization is also the key here.

Constituent elements

  1. Evaluation Function: The Evaluation Function is used to evaluate the neighbors in the neighborhood and judge their advantages and disadvantages. In most cases, the evaluation function is the objective function. However, a custom form may also exist, and the algorithm may use multiple evaluation functions to improve the dispersion (differentiation) of the solutions.

  2. Move Operator: Neighborhood Move, also known as “Operator”, is the key to the solution transfer and affects the search speed of the whole algorithm. Neighborhood movement needs to be defined according to different characteristics of the problem, and the entire neighborhood solution space is a set of all neighborhood solutions constructed by the current solution through the defined movement operations.

  3. Tabu Table: A Tabu Table records forbidden changes to prevent search loops and local optima. Tabu table is the core of tabu search algorithm. The object, step and update strategy of tabu table greatly affect the search speed and the quality of solution. If the tabu object is not accurate or the step size is too small, the algorithm’s ability to avoid falling into the local optimal will be greatly reduced. If the tabu table step size is too large, the search area will be limited and good solutions may be skipped. .

  4. Tabu length: The maximum number of tabu objects that can be accepted in the tabu list.

  5. Tabu step: The number of iterations after which an object’s tabu becomes invalid.

Algorithm process

​

Figure 1 flowchart of TS algorithm

Three, MATLAB program implementation

1. Problem description

Suppose that the intended travel agent wants to visit 31 provincial capitals (excluding Hong Kong, Macao and Taiwan), from a city, need to pass through, after all the cities, back to the point of departure. You can only pass through each city once, and you need to choose a shortest path.

​

Table 1 Coordinates of each city

​

FIG. 2 Distribution of 31 cities

2. Tabu search algorithm solution

(1) Initialize parameters and set tabu table to null. Initialize the city size n=31, TabuL length =22, number of candidate solutions Ca=200, maximum number of iterations iter_max=1000, citys refers to the coordinates of 31 cities and other parameters. The code is as follows:

load citys_data.mat; n = size(citys, 1); % number of cities D = zeros(n); Tabu = zeros(n); TabuL = round(SQRT (n*(n-1)/2)); % tabu length Ca = 200; % number of candidate sets (total number of neighborhood solutions) Canum = Zeros (Ca, n); % candidate solution set S0 = Randperm (n); % randomly generate initial solution bestSOFAR = S0; % current best solution BestL = Inf; % current optimal solution distance iter = 1; % Number of initial iterations iter_max = 1000; % Maximum number of iterationsCopy the code

​

% % calculated distance matrix for I = 1: n for j = I + 1: n D (I, j) = SQRT (sum ((citys (I, :) - citys (j:)) ^ 2)); D(j, i) = D(i, j); end endCopy the code

(3) The neighborhood mapping of the initial solution is defined as 2-OPT, that is, two cities are randomly exchanged in the initial solution path. The code is as follows:

i = 1; A = zeros(Ca,2); While I <= Ca r = ceil(n*rand(1,2)); while I <= Ca r = ceil(n*rand(1,2)); Two cities if r % random exchange (1) ~ = r (2) A (I, 1) = Max (r (1), r (2)); A(i, 2) = min(r(1), r(2)); if i == 1 flag = 0; else for j = 1:i-1 if A(i, 1) == A(j, 1) && A(i, 2) == A(j, 2) flag = 1; break; else flag = 0; end end end if ~flag i = i + 1; End end end %% Generate neighborhood solution % retain the best candidate solution before BestCanum BestCanum = Ca/2; BestCa = Inf * ones(BestCanum, 4); F = zeros(1, Ca); for i = 1:Ca Canum(i, :) = S0; Canum(i, [A(i, 2), A(i, 1)]) = S0([A(i, 1), A(i, 2)]); % in exchange for A (I, 1) and A (I, 2) the elements listed F (I) = fitness (D, Canum (I, :)); If I <= BestCanum % select candidate set BestCa(I, 1) = I; % BestCa(I, 2) = F(I); % BestCa(I, 2) = F(I); BestCa(I, 3) = S0(A(I, 1)); BestCa(I, 4) = S0(A(I, 2)); Else for j = 1:BestCanum % update candidate set if F(I) < BestCa(j, 1) = I; BestCa(j, 2) = F(i); BestCa(j, 3) = S0(A(i, 1)); BestCa(j, 4) = S0(A(i, 2)); break; [value, index] = sort(BestCa(:, 2)); SBest = BestCa(index, :); BestCa = SBest; % Select the top 100 good candidate solutionsCopy the code

(4) Determine whether the selected solution meets the amnesty criteria. The code is as follows:

% % amnesty guidelines if BestCa (1, 2) < % BestL candidate solution than the optimal value is small, then whatever's in tabu table, is the same operation % in tabu table, all minus 1, pardon, on the last; % is not in the tabu table, subtract 1 from all and put it at the end. BestL = BestCa(1, 2); % BestL current optimal solution fit value S0 = Canum(BestCa(1,1), :; % optimal solution replacement bestSOfar = S0; Update the taboo table % for I = 1: n if Tabu (I, :) ~ = 0 Tabu (I, :) = Tabu (I, :) - 1; end end Tabu(BestCa(1, 3), BestCa(1, 4)) = TabuL; Else % the best solution is still no better than the current best value, then: For I = 1:BestCanum % traverse candidate set if Tabu(BestCa(I, 3), BestCa(I, 4)) == 0% That is, tabu length is 0 S0 = Canum(BestCa(I, 1), :); For j = 1:n if Tabu(j, :) ~= 0 Tabu(j, :) = Tabu(j, :)-1; end end Tabu(BestCa(i, 3), BestCa(i, 4)) = TabuL; % to the end of tabu table break; % immediately breaks out of the for loop because the best solution that is not in the tabu table is selected end end endCopy the code

Failed to upload the data againwAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==​

3. Simulation results

Failed to upload the data againwAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==​​

Figure 3 Optimization path of TS algorithm

​

FIG. 4 Evolution curve of fitness

Complete code or simulation consulting add QQ1575304183

​