- 2021-05-07 00:01
*views 8*- 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

- Python146 blogs
- Java131 blogs
- Vue86 blogs
- Flow Chart79 blogs
- javascript42 blogs
- C++41 blogs
- programing language38 blogs
- MySQL37 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

cartoon ： What is? JVM Garbage collection in China ? Huawei Hongmeng system HarmonyOS Learning 9 ： Hongmeng HarmonyOS History and future python Implementation in Mysql Data rollback rollback() And principle analysis The problem of string left rotation android 10.0 Version integration GMS package mysql actual combat 45 speak --- 33 Query large amount of data , Will the memory burst ajax send out post/get data ,java How to receive in the background RocketMQ Multiple namesrv Use of pits encountered 2021 Blue Bridge Cup B group C/C++ Personal records Blockchain journey ( three ) Smart contract and consensus mechanism