A brief introduction of tabu search algorithm
The process of solving a problem is search, which is a basic problem of artificial intelligence, and artificial intelligence is widely used in various application fields. Now search technology permeates in all kinds of artificial intelligence systems, it can be said that there is no application of artificial intelligence without search method. The idea of Tabu Search or Taboo Search (TS) was first proposed by Prof. Glover, academician of The American Academy of Engineering in 1986 [], and further defined and developed this method in 1989 and 1990 [2-4]. In the research field of natural computing, tabu search algorithm, with its flexible storage structure and corresponding tabu criteria to avoid roundabout search, is unique among intelligent algorithms and has become a research hotspot, attracting extensive attention from scholars at home and abroad. So far, tabu search algorithm has achieved great success in combinatorial optimization, production scheduling, machine learning, circuit design, neural network and other fields. In recent years, it has been studied more in function global optimization and has a rapid development trend [5-8]. The so-called taboo is the prohibition of repeating the previous operation. In order to improve the local neighborhood search easy to fall into local optimal point, the deficiency of the tabu search algorithm is introduced into a tabu table, record has been searching local optimal point, in the next search, information of tabu table no longer search or search selectively, in order to jump out of local optimal point, so as to achieve global optimization. Tabu search algorithm is an extension of local neighborhood search and an algorithm of global neighborhood search and optimization step by step. Tabu search algorithm is an iterative search algorithm, which differs from other modern heuristic algorithms in that it uses memory to guide the search process of the algorithm. It is a simulation of human intelligence process, is a manifestation of artificial intelligence. Tabu search algorithm involves neighborhood, tabu table, tabu length, candidate solutions, contempt criteria and other concepts. On the basis of neighborhood search, tabu criteria are used to avoid repeated search, and some good tabu states are spared through contempt criteria, so as to ensure diversified effective search and finally achieve global optimization.
Tabu search algorithm theory 2.1 Local neighborhood searchLocal neighborhood search is a continuous search in the current neighborhood based on greedy criteria. Although its algorithm is universal, easy to implement, and easy to understand, its search performance completely depends on the neighborhood structure and initial solution, and it is especially prone to fall into local minimum and cannot guarantee global optimization. The algorithm of local search can be described as:
2.4 improvement direction of the tabu search algorithm Tabu search is famous as a heuristic search algorithm, but it has obvious lack of tabu search, which needs to be improved in the following aspects: (1) has a strong dependence to the initial solution, a good initial solution can make the tabu search algorithm to search a good solution in the solution space, while poor initial solution can reduce the convergence rate of the tabu search. Therefore, it can be combined with genetic algorithm, simulated annealing algorithm and other optimization algorithms to generate a good initial solution, and then use tabu search algorithm for search optimization. (2) The iterative search process is serial, only the movement of a single state, rather than parallel search. In order to further improve the performance of tabu search, on the one hand, the operation and parameter selection of tabu search algorithm itself can be improved, and the parallel strategy can be implemented in the initialization and parameter setting of the algorithm to obtain different types of parallel tabu search algorithm [9] : On the other hand, it can be combined with genetic algorithm, neural network algorithm and local search based on problem information. (3) Lack of diversity in the case of both concentration and diversity search. The centralized search strategy is used to strengthen the search of the neighborhood of the good solution in order to find the global optimal solution. Diversity search strategy is used to expand the search area, especially the unknown area. When the search falls into the local optimum, diversity search can change the search direction and jump out of the local optimum, so as to achieve the global optimum. A simple way to increase diversity is to rerandomly initialize the algorithm or to punish some known object based on the frequency information.
3 tabu search algorithm flowThe basic idea of simple tabu search algorithm is: given a current solution (initial solution) and a kind of neighborhood, then determine several candidate solutions in the neighborhood of the current solution; If the corresponding target value of the best candidate solution is better than that of the “Best so far” state, the tabu property of the best candidate solution is ignored, and the tabu property is used to replace the current solution and the “Best so far” state, and the corresponding objects are added to the tabu table, and the tenure of each object in the tabu table is modified: If there is no candidate solution, the best state of non-taboo is selected as the new current solution, ignoring its merits and demerits with the current solution. At the same time, the corresponding objects are added to the tabu table, and the term of each object in the tabu table is modified. The iterative search process is repeated until the stop criteria are met. The algorithm steps can be described as follows: (1) Given tabu search algorithm parameters, initial solution X is randomly generated and tabu table is left blank. (2) Determine whether the algorithm termination conditions are met: If so, end the algorithm and output the optimization results; otherwise, proceed with the following steps. (3) Generate all (or several) neighborhood solutions by using the neighborhood function of the current solution, and determine some candidate solutions. (4) Judge whether the contempt criterion meets the candidate solution: if so, x is replaced by y, the best state meeting the contempt criterion, as the new current solution, that is, x= Y, and the taboo object corresponding to Y is used to replace the taboo object that entered the taboo table at the earliest, and y is used to replace the “best so far” state, and then go to step (6) : Otherwise, proceed with the following steps. (5) Judge the tabu attribute of each object corresponding to the candidate solution, select the best state corresponding to the non-tabu object in the candidate solution set as the new current solution, and replace the tabu object that entered the tabu table first with the corresponding tabu object. (6) Determine whether the algorithm termination conditions are met: If so, end the algorithm and output the optimization results; otherwise, go to Step (3). The operation process of tabu search algorithm is shown in Figure 8.1.
By moving, the value of the objective function will change, and the difference between the value of the objective function before and after moving is called the moving value. If the movement value is non-negative, it is called an improved movement; otherwise, it is called an unimproved movement. The best movement is not necessarily improved movement, but also may be non-improved movement, which can guarantee that tabu search algorithm can automatically jump out of the local optimal when the search falls into the local optimal.
Taboo objects refer to the changing elements that are placed in the taboos table. The purpose of taboos is to avoid roundabout search and search other places in the solution space as much as possible. To sum up, taboo objects can usually select the state itself or state components.
Selection of candidate solutions Candidate solutions are usually selected preferentially in the neighborhood of the current state. Too much selection will result in a large amount of calculation, while less selection will lead to premature convergence. However, to achieve the selection of the whole neighborhood often requires a lot of calculation, so candidate solutions can be selected deterministically or randomly in part of the neighborhood. The size of the data depends on the characteristics of the problem and the requirements of the algorithm. The nature of taboos that are not allowed to be restored (that is, forbidden) is called Tabu. The main purpose of taboos is to prevent loops and avoid falling into local optimality in the search process. It usually records the previous several moves and prohibits them from returning in the near future. After a fixed number of iterations, the tabu table releases these moves and re-participates in the operation, so it is a circular table, with each iteration, the most recent move is placed at the end of the tabu table, and its earliest move is released from the tabu table. In terms of data structure, taboos are fifO queues with a certain length. Tabu search algorithm uses tabu table to forbid searching for previously visited solutions, thus forbidding local loops in search. Tabu lists can be memorized in two ways: explicit memory and attribute memory. Clear memory means that the element in tabu table is a complete solution, consuming more memory and time. Attribute memory means that the element in tabu table records the information of the current solution movement, such as the direction of the current solution movement, etc.
Taboo length refers to the maximum number of times that taboo objects are not allowed to be selected without considering the amnesty criterion. Colloquially, the taboo length can be regarded as the tenure of the taboo object in the taboo table. Taboo objects can only be unbanned if their tenure is 0. In the process of algorithm design and construction, it is generally required to minimize the amount of computation and storage, which requires the taboo length to be as small as possible. However, too long a taboo can create a search cycle. The selection of taboo length is related to the characteristics of the problem, which determines the computational complexity of the algorithm to a large extent. On the one hand, taboo length can be a fixed constant (such as t=c, where C is a constant), or a fixed quantity related to the problem size (such as t=√n, where n is the dimension or size of the problem), which is convenient, simple and effective to implement: On the other hand, taboo length can also change dynamically. For example, the change interval of taboo length can be set according to search performance and problem characteristics, and the taboo length can change within this interval according to some rules or formulas.
In tabu search algorithm, all candidate solutions may be tabu, or there may be a tabu candidate solution better than the “best so far” state. In this case, amnesty criterion will unblock some states to achieve more efficient optimization performance. The common ways of amnesty criteria are as follows: (1) Principle based on fitness value: if the fitness value of a tabu candidate solution is better than the “bestso far” state, the tabu candidate solution will be released as the current state and the new “Best so far” state. (2) Criterion based on search direction: if the adaptation value of the tabu object improved when it was tabu last time, and the adaptation value of the candidate solution corresponding to the tabu object is better than the current solution, the tabu object will be lifted.
Search strategies Search strategies are divided into concentrated search strategies and diversified search strategies. The concentrated search strategy is used to enhance the further search for the neighborhood of good solution. A simple way to do this is to reinitialize it based on the best state after a certain number of iterations and search its neighborhood again. In most cases, the reinitialized neighborhood space is not the same as the last neighborhood space, and of course some of the neighborhood space may overlap. Diversity search strategy is used to broaden the search area, especially unknown area. It can be handled simply by rerandomly initializing the algorithm or punishing some known objects according to the frequency information.
Termination criterion Tabu search algorithm needs a termination criterion to end the search process of the algorithm, but it is obviously impossible to realize the convergence condition in strict theoretical sense, that is, to achieve the traversal of the state space under the condition of sufficiently large tabu length. Therefore, approximate convergence criterion is usually adopted in practical algorithm design. The commonly used methods are as follows: (1) The maximum number of iterative steps is given. When the tabu search algorithm runs to a specified number of iterative steps, the search is terminated. (2) Set the maximum taboo frequency of an object. If the tabu frequency of a certain state, match value or commutation object exceeds a certain threshold value, or the best match value remains unchanged for several consecutive steps, the algorithm is terminated. (3) Set the deviation threshold of adaptation value. First, the lower bound of the problem is estimated. If the deviation between the best fit value and the lower bound is less than a specified threshold, the search is terminated.
Two, some source code
clear;
CityNum=22; [dislist,Clist]=tsp(CityNum); Tlist=zeros(CityNum); % Tabu tablelist)
cl=60; Retain the first Cl best candidate solution BSF =Inf; tl=50; % Tabu length l1=100; % candidate solution, not greater than n*(n)/2(Number of solutions in all fields) S0= Randperm (CityNum); S0(:,1) =0;
S0(:,CityNum)=CityNum- 1;
S0(:,2:CityNum- 1)=randperm(CityNum2 -);
S0=S0+ones;
S=S0(:,2:CityNum- 1);
Num=length(S);
BSF=S0;
Si=zeros(l1,Num);
StopL=100; % Number of terminated steps p=1;
clf;
figure(1);
while (p<StopL+1)
if l1>Num*(Num)/2
disp('Number of candidate solutions, no more than n*(n)/2(total domain solutions)! The system automatically exits! ');
l1=(Num*(Num)/2) ^. 5;
break;
end
ArrS(p)=CalDist(dislist,S);
i=1;
A=zeros(l1,2);
while i<=l1
M=Num*rand(1.2);
M=ceil(M);
if M(1)~=M(2)
m1=max(M(1),M(2)); m2=min(M(1),M(2));
A(i,1)=m1; A(i,2)=m2;
if i==1
isdel=0;
else
for j=1:i- 1
if A(i,1)==A(j,1)&&A(i,2)==A(j,2)
isdel=1;
break;
else
isdel=0;
end
end
end
if ~isdel
i=i+1;
else
i=i;
end
else
i=i;
end
end
for i=1:l1
Si(i,:)=S;
Si(i,[A(i,1),A(i,2)])=S([A(i,2),A(i,1)]);
CCL(i,1)=i;
CCL(i,2)=CalDist(dislist,Si(i,:));
CCL(i,3)=S(A(i,1));
CCL(i,4)=S(A(i,2));
end
[fs fin]=sort(CCL(:,2));
for i=1:cl
CL(i,:)=CCL(fin(i),:);
end
if CL(1.2)< BSF % flout criteria(aspiration criterion)
bsf=CL(1.2);
S=Si(CL(1.1), :); BSF(:,2:CityNum- 1)=S;
for m=1:Num
for n=1:Num
if Tlist(m,n)~=0
Tlist(m,n)=Tlist(m,n)- 1;
end
end
end
Tlist(CL(1.3),CL(1.4))=tl;
else
for i=1:cl
if Tlist(CL(i,3),CL(i,4)) = =0
S=Si(CL(i,1), :);for m=1:Num
for n=1:Num
if Tlist(m,n)~=0
Tlist(m,n)=Tlist(m,n)- 1;
end
end
end
Tlist(CL(i,3),CL(i,4))=tl;
break;
end
end
end
Arrbsf(p)=bsf;
drawTSP(Clist,BSF,bsf,p,0);
p=p+1;
end
BestShortcut=BSF;
theMinDistance=bsf
figure(2);
plot(Arrbsf,'r'); hold on;
plot(ArrS,'b'); grid; title('Search process');
legend('Optimal solution'.'Current solution');
function F=CalDist(dislist,s)
n=size(s,2);
v1=0.8; % loading speed v2=20; % driving speed w1=0.9; W2 = %3;
w3=6;
c=20; % Fixed loss cost r=0.025; % Loss coefficient of vehicle damage and load mass q=[0.5.0.5.1.10.4.7.4.1.2.5.5.4.1.5.10.11.1.2.1.4.2.9.0.1.4.7.2.7.9.0]; According to the %1- 30Order of sites T1 =[0.9.2.10.7.5.9.8.0.9.4.8.8.10.1.11.2.12.0.12.9.13.4.14.2.15.0.16.5.14.3.13.5.13.14.2.16.2.15.3.17];
t2=[34.0.10.0.12.1.6.3.8.5.9.9.9.7.10.9.11.7.12.6.19.4.13.9.14.9.15.5.17.4.18.2.18.9.19.1.19.8.20.4.20.9.23];
q1=zeros(1,n); % updated site order t11=zeros(1,n);
t21=zeros(1,n);
z1=zeros(1,n); % Store z2=zeros(1,n);
t=zeros(1,n); % Time of arrival for each site DistanV=0; % Distribution cost loss=0; % vehicle damage costfor i1=1:n
k=find(s(:,:)==i1);
q1(:,k)=q(:,i1);
t11(:,k)=t1(:,i1);
t21(:,k)=t2(:,i1);
end
q1;
t11;
t21;
for j=1:(n- 1)
DistanV=DistanV+dislist(s(j),s(j+1));
t(:,j+1)=t(j)+(dislist(s(j),s(j+1))/v2)+max(0,t11(:,j)-t(:,j))+q1(:,j)/v1;
loss=loss+c*(1+r*q1(:,j));
end
DistanV=DistanV+dislist(s(n),s(1));
loss=loss+c;
t(:,1)=t(:,n)+(dislist(s(n),s(1))/v2)+max(0,t11(:,n)-t(:,n))+q1(:,n)/v1;
t;
for m=1:n
if t11(:,m)-t(:,m)>0
z1(:,m)=z1(:,m)+t11(:,m)-t(:,m);
end
if t(:,m)-t21(:,m)> 0z2(:,m)=z2(:,m)+t(:,m)-t21(:,m);
end
end
function [DLn,cityn]=tsp(n)
CityNum=22;
city=[1304.1312;
3488.1535;
3326.1556;
3238.1229;
4196.1004;
4386.570;
3007.1970;
2562.1756;
3918.2179;
4061.2370;
3780.2212;
3676.2578;
4029.2838;
4263.2931;
3429.1908;
3394.2643;
3439.3201;
2935.3240;
3140.3550;
2780.2092;
676.1978;
2449.748];
for i=1:CityNum
for j=1:CityNum
DL(i,j)=((city(i,1)-city(j,1)) ^2+(city(i,2)-city(j,2)) ^2) ^0.5;
end
end
DLn=DL;
cityn=city;
Copy the code3. Operation results
Matlab version and references
1 matlab version 2014A
[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.