- 2021-05-07 00:01
*views 24*- Path planning
- TWVRP
- VRP
- Matlab

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

- Java239 blogs
- Python239 blogs
- Vue108 blogs
- algorithm94 blogs
- c language90 blogs
- Flow Chart81 blogs
- MySQL71 blogs
- C++64 blogs
- more...

Daily Recommendation

© ioDraw All rights reserved

Outsourcing for five years , Abandoned ...Windows Basic command 【Linux】 Understanding, advantages and disadvantages of multiprocess and multithreading Tkinter： change Button Control state C Practice your language every day 2： Yanghui triangle Computer function key name , Do you know the basic knowledge of computer keyboard function c Language game code _C Language implementation Gobang Computer keyboard letter memory , keyboard 26 What is a letter formula ? Wu Enda machine learning - Detect exception server Explain in detail Qt Font settings (QFont)