Traveling Salesman Problem (TSP), also known as salesman problem, is the most basic route problem. The problem seeks the minimum path cost for a single traveler to start from the starting point, pass through all given demand points, and finally return to the starting point. The earliest mathematical model of the traveling salesman problem was proposed by Dantzig(1959) et al. Traveling salesman problem is a special case of vehicle routing problem (VRP), and it has been proved that traveling salesman problem is NP problem.

Mark the local optimal solutions or solving processes that have been solved, and avoid these local optimal solutions or solving processes in further iterations. The disadvantage of local search lies in that it is too much to search a certain local area and its neighborhood, leading to blindness. In order to find the global optimal solution, tabu search is to consciously avoid some local optimal solutions, so as to obtain more search areas.

Metaphor: when the rabbits find Mount Tai, one of them will stay here and the others will look for it somewhere else. And so, after a big circle, comparing the few peaks we found, Everest stood out.

2.2 Algorithm Process

Step1: give taboo table H= empty set, and select an initial solution xnow;

Step2: when the stop rule is met, stop the calculation and output the results; Otherwise, Can_N(xnow), which is not taboo, is selected in xNOW’s neighborhood N(xnow). In Can_N(xnow), select a solution with the best evaluation value xnext, xnow=xnext; Update historical record H, save f(xnow), repeat step2;

Step3: select the minimum (large) value as the solution among the numerous f’s saved;

1. When the rabbits find Mount Tai, one of them will stay here and the others will look elsewhere. When the rabbits searched again, they generally avoided Mount Tarzan consciously, because they knew that it had already been searched and that a rabbit was watching. That’s what you see in taboo search.Taboo table (tabulist)The meaning of.
2. The rabbit that stays on Mount Taishan does not usually make its home there. It returns to the search for the highest peak after a certain time, when there is much new news. This return time is called in the tabu searchTabu length“;
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, You can take this place into account, regardless of whether rabbits stay or not, and this is called”Aspiration Criterion“

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

Constituent elements

1. Evaluation Function: Evaluation function is used to evaluate neighbors in a neighborhood and judge its merits. In most cases, evaluation function is objective function. However, a custom form can also exist, and the algorithm can also use multiple evaluation functions to improve the dispersion (differentiation) of the solution.
2. Move Operator: Neighborhood movement is the key of solution transfer, also known as “operator”, which affects the search speed of the whole algorithm. Neighborhood movement needs to be self-defined according to the characteristics of different problems, and the whole neighborhood solution space is a set of all neighborhood solutions constructed by the current solution through the defined movement operation.
3. Tabu Table: Taboos record prohibited changes in case of search cycles and local optima. The most critical factor in its design is the taboo object (Objects qualified by taboos) and taboo step size (How many iterations do objects’ taboos expire)Tabu table is the core of tabu search algorithm. The object, step size and update strategy of tabu table affect the search speed and quality to a great extent. If the tabu object is inaccurate or the step size is too small, the ability of the algorithm to avoid falling into local optimum will be greatly reduced. If the tabu step size is too large, the search area will be limited and good solutions may be skipped.).
4. Tabu length: The maximum number of taboos that can be accepted in the taboos table.
5. Taboo step: How many iterations do objects’ taboos expire?

Figure 1 Flow chart of TS algorithm

Suppose that the intending travel agent wants to visit 31 provincial capital cities (excluding Hong Kong, Macao and Taiwan) in China. Starting from one city, he needs to pass through all the cities and return to the starting point. Each city can only pass once, and a shortest path is required.

Table 1 Coordinates of each city

FIG. 2 Distribution map of 31 cities

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

load citys_data.mat; n = size(citys, 1); % City number D = zeros(n); % distance matrix Tabu = zeros(n); TabuL = round(SQRT (n*(n-1)/2); % Taboo length Ca = 200; % Number of candidate sets (number of all neighborhood solutions) Canum = Zeros (Ca, n); % Candidate solution S0 = randperm(n); % randomly generate the initial solution bestSOFAR = S0; % BestL = Inf; % Current optimal solution distance iter = 1; % Initial number of 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) Neighborhood mapping of the initial solution is defined as 2-opt form, that is, two cities are randomly exchanged in the path of the initial solution. 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 %% 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); % save fitness value (path distance) 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, 2) 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) Judge whether the solutions selected meet the amnesty criteria. The code is as follows:

%% amnesty criteria if BestCa(1,2) < BestL % candidate solution is less than the best value, then it is the same operation whether in the taboo table or not % in the taboo table, all minus 1, amnesty comes out, put at the end; % is not in the taboo list, all minus 1, put last; BestL = BestCa(1, 2); 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 not better than the current best value, then: For I = 1:BestCanum % Traversal candidate set if Tabu(BestCa(I, 3), BestCa(I, 4)) == 0 % BestCa is arranged from small to large, select the first solution that is not in the Tabu table, 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; % at the end of taboos break; % immediately jumps out of the for loop because the best solution that is not in the tabu is already selected end end endCopy the code

​

FIG. 3 TS algorithm optimization path

FIG. 4 Fitness evolution curve

Code download or simulation consultation to add QQ1575304183