©2020-2024 ioDraw All rights reserved
Tabu search algorithm
<> <> Algorithmic thinking
Mark the local optimal solution or solving process that has been solved , These local optimal solutions or solving processes are avoided in further iterations . The disadvantage of local search is that , Too much for a local region and its neighborhood search , Lead to blindfold . In order to find the global optimal solution , Tabu search is to find a part of the local optimal solution , Avoid it consciously , So you can get more search areas
<> <> Algorithm process
*
（1） Given a tabu list （Tabu List）H=null, An initial solution is selected X_now.
*
（2） If the stop rule is satisfied , The calculation is stopped , Output results ; otherwise , stay X_now The candidate set satisfying the non taboo is selected from the domain of N(X_now). stay N(X_now) Choose the solution with the lowest evaluation value in X_next,X_next：=X_now; Update history H,
Repeat the steps （2）.
* 1
* 2
<> <> Factors affecting search performance
tabu length
Control other variables , As far as the choice of taboo length is concerned , The shorter the taboo length is , The less machine memory is used , Wider scope of lifting the ban （ The larger the upper limit of search scope ）, But it's easy to create a search cycle （ The actual scope of search is very small ）, Fall into local optimum too early . If the taboo length is too long, the computation time will be too long .
Amnesty rules
Popular definition ： For those who are taboo , If , No matter what the taboo length of the present object is , All set to 0
（1） Rules based on evaluation value , If a solution appears, the target value is better than any of the previous best candidate solutions , Pardonable ;
（2） Rules based on minimum error , If all objects are taboo , A solution of amnesty with minimum evaluation value ;
（3） Rules based on Influence , You can grant amnesty to those who have a great influence on the target value .
Candidate set
The size of the candidate set , Excessive increase of computing memory and computing time , Too small to fall into local optimum too early . The selection of candidate sets is generally composed of neighbors in the neighborhood , You can choose all your neighbors , You can also choose a neighbor who performs better , You can also choose a few neighbors at random .
evaluation function
Evaluation function is divided into direct evaluation function and indirect evaluation function .
Direct evaluation function ： The above example , The target value is directly used as the evaluation function .
Indirect evaluation function ： Function reflecting the characteristics of objective function （ It is easier to calculate than the objective function , To reduce the calculation time, etc ）.
Termination Rules
Tabu algorithm is a heuristic algorithm , We can't let the search go on indefinitely , So there are some intuitive termination rules
（1） Determine the number of steps to terminate , The effect of the solution cannot be guaranteed , The current optimal solution should be recorded ;
（2） Frequency control principle , When a solution , When the frequency of the target value or sequence of elements exceeds a given value , Termination of calculation ;
（3） Objective control principle , If in a given number of steps , The current optimal value has not changed , Terminable calculation .
clear clc %% use importdata This function reads the file c208=importdata('c208.txt'); cap=700; % Vehicle load
maxIter=300; % Maximum number of iterations E=c208(1,5); % Warehouse time window start time L=c208(1,6); % Warehouse time window end time
vertexs=c208(:,2:3); % Coordinates of all points x and y customer=vertexs(2:end,:); % Customer coordinates
cusnum=size(customer,1); % Number of customers vecnum=cusnum; % Number of vehicles demands=c208(2:end,4); % requirement
a=c208(2:end,5); % Customer time window start time [a[i],b[i]] b=c208(2:end,6); % End time of customer time window [a[i],b[i]]
s=c208(2:end,7); % Service time of customer point h=pdist(vertexs); dist=squareform(h);
% Distance matrix , Satisfy triangle relation , The cost is temporarily expressed by distance c[i][j]=dist[i][j] vehicles_customer=cell(vecnum,1);
% Customers passing by each car %% CW Law construction VRPTW Initial solution % output init_vc Customers passing by each car % output init_TD Total distance traveled by all vehicles
% output init_vl Loading capacity of each vehicle % output violate_INTW Determine whether the time window constraint is violated ,0 Representative does not violate ,1 Representative violation
[init_vc,init_TD,init_vl,violate_INTW] =
init_TW(c208,L,demands,a,b,s,dist,cap); %%
Initialize each vehicle distribution route , Each installation site is delivered by one vehicle , yes d2 The required installation site is in front of the processing workshop 0 express % [ init_vc ] = init_route(
vehicles_customer ); % init_TD=travel_distance(init_vc,dist); S=init_vc; % Current solution
eS=minLen(S); % The minimum number of customers in each path of the current solution initNV=size(S,1); % Number of vehicles used Sbest=S; % Global optimal solution %
f=initNV*cusnum+eS; % fBest=initNV*cusnum+eS; f=initNV*cusnum+init_TD;
fBest=initNV*cusnum+init_TD; TbList=zeros(cusnum,initNV); % Taboo list TbLength=20;
% tabu length NS=neighborhood(S,L,cusnum,demands,a,b,s,dist,cap); %S Neighborhood of
[subNS]=subNeighbor(TbList,NS,fBest); % non-tabu or allowed by aspiration %%
Tabu Search iter=0; count=0; while iter<maxIter if ~isempty(subNS)
[minValue,minIndex]=min(subNS(:,5)); % Find out the line number with the smallest total distance from the neighborhood
value=subNS(minIndex,:); % Extract the row array of the smallest row number i=value(1); j=value(2); k=value(3);
p=value(4); fS=value(5); [S_copy]=insert(S,i,j,k,p); if fS<fBest fBest=fS;
Sbest=S_copy; S=S_copy;
NS=neighborhood(S_copy,L,cusnum,demands,a,b,s,dist,cap);
[subNS]=subNeighbor(TbList,NS,fBest); % Update tabu list for l=1:cusnum for h=1:initNV if
TbList(l,h)~=0 TbList(l,h)=TbList(l,h)-1; end end end if TbList(i,j)==0
TbList(i,j)=TbLength; else TbList(i,j)=0; end else if TbList(i,j)==0 S=S_copy;
NS=neighborhood(S,L,cusnum,demands,a,b,s,dist,cap);
[subNS]=subNeighbor(TbList,NS,fBest); % Update tabu list for l=1:cusnum for h=1:initNV if
TbList(l,h)~=0 TbList(l,h)=TbList(l,h)-1; end end end TbList(i,j)=TbLength; end
end else break end iter=iter+1; end Sbest=deal_vehicles_customer(Sbest);
bestNV=size(Sbest,1); bestTD=travel_distance(Sbest,dist); DEL=Judge_Del(Sbest);
% Check whether there is element loss in the optimal solution % Calculate the starting time of each vehicle on the distribution route at each point , Also calculate the return time to the warehouse bsv=
begin_s_v(Sbest,a,s,dist ); [ violate_TW ] = Judge_TW( Sbest,bsv,b,L ); %
Determine whether the time window constraint is violated ,0 Representative does not violate ,1 Representative violation
Full code addition QQ1575304183
Technology