candidates

禁忌搜索算法总结

禁忌搜索算法简介

禁忌搜索（TabuSearch，TS）是⼀种现代启发式算法，由美国科罗拉多⼤学教授FredGlover在1986年左右提出的，是⼀个⽤来跳脱局

部最优解的搜索⽅法。

算法基于局部搜索算法改进⽽来，通过引⼊禁忌表来克服局部搜索算法容易陷⼊局部最优的缺点，具有全局寻优能⼒。

局部搜索算法

局部搜索算法从⼀个初始解开始，通过邻域动作，产⽣其邻居解，判断邻居解的质量，根据某种策略，来选择邻居解，重复上述过程，⾄到

达终⽌条件。

针对局部邻域搜索，为了实现全局优化，可尝试的途径有：

以可控性概率接受劣解来逃逸局部极⼩，如模拟退⽕算法；

扩⼤邻域搜索结构，如TSP的2opt扩展到k-opt；

多点并⾏搜索，如进化计算；

采⽤TS的禁忌策略尽量避免迂回搜索，它是⼀种确定性的局部极⼩突跳策略。

基本思想

避免在搜索过程中的循环

只进不退的原则,通过禁忌表实现

不以局部最优作为停⽌准则

标记已经解得的局部最优解或求解过程，并在进⼀步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某⼀局部区

域以及其邻域的搜索，导致⼀叶障⽬。为了找到全局最优解，禁忌搜索就是对于找到的⼀部分局部最优解，有意识地避开它，从⽽或得更多

的搜索区域。

基本构成部分

禁忌表

禁忌表的作⽤：防⽌搜索出现循环。记录前若⼲步⾛过的点、⽅向或⽬标值，禁⽌返回；表是动态更新的，表的长度称为Tabu-Size(禁忌长

度)。

禁忌长度

指在之后多少个循环内禁⽤某个产⽣邻域的规则(禁忌对象)。

就禁忌长度的选择⽽⾔，禁忌长度越短，机器内存占⽤越少，解禁范围更⼤（搜索范围上限越⼤），但很容易造成搜索循环（实际去搜索的

范围却很⼩），过早陷⼊局部最优。禁忌长度过长⼜会导致计算时间过长。

特赦规则

通俗定义：对于在禁忌的对象，如果出现以下情况，不论现在对象的禁忌长度如何，均设为0

基于评价值的规则，若出现⼀个解的⽬标值好于前⾯任何⼀个最佳候选解，可特赦；

基于最⼩错误的规则，若所有对象都被禁忌，特赦⼀个评价值最⼩的解；

基于影响⼒的规则，可以特赦对⽬标值影响⼤的对象。

候选集

⼀次循环中产⽣领域解的数⽬。

候选集的⼤⼩，过⼤增加计算内存和计算时间，过⼩过早陷⼊局部最优。候选集的选择⼀般由邻域中的邻居组成，可以选择所有邻居，也可

以选择表现较好的邻居，还可以随机选择⼏个邻居。

评价函数

即代价函数，衡量⽬标解的好坏。评价函数分为直接评价函数和间接评价函数。

终⽌规则

⼀些直观的终⽌规则：

确定步数终⽌，⽆法保证解的效果，应记录当前最优解；

频率控制原则，当某⼀个解、⽬标值或元素序列的频率超过⼀个给定值时，终⽌计算；

⽬标控制原则，如果在⼀个给定步数内，当前最优值没有变化，可终⽌计算。

算法流程

代码⽰例

禁忌搜索算法求解中国TSP问题：

%%⼀个旅⾏商⼈要拜访全国31个省会城市，且每个城市只能拜访⼀次，求所有路径之中的最⼩值

%%%禁忌搜索算法求解TSP问题%%%%%%%%%%%%%%%%%%%%%

function[BestShortcut,theMinDistance]=TabuSearch

clear;

clc;

Clist=[13042312;36391315;41772244;37121399;34881535;33261556;32381229;...

41961044;4312790;4386570;30071970;25621756;27881491;23811676;...

1332695;37151678;39182179;40612370;37802212;36762578;40292838;...

42632931;34291908;35072376;33942643;34393201;29353240;31403550;...

25452357;27782826;23702975];%全国31个省会城市坐标

CityNum=size(Clist,1);%TSP问题的规模,即城市数⽬

dislist=zeros(CityNum);

fori=1:CityNum

forj=1:CityNum

dislist(i,j)=((Clist(i,1)-Clist(j,1))^2+(Clist(i,2)-Clist(j,2))^2)^0.5;

end

end

TabuList=zeros(CityNum);%(tabulist)

TabuLength=round((CityNum*(CityNum-1)/2)^0.5);%禁忌表长度(tabulength)

Candidates=200;%候选集的个数(全部领域解个数)

CandidateNum=zeros(Candidates,CityNum);%候选解集合

S0=randperm(CityNum);%随机产⽣初始解

BSF=S0;%bestsofar;

BestL=Inf;%当前最佳解距离

p=1;%记录迭代次数

StopL=2000;%最⼤迭代次数

figure(1);

stop=uicontrol('style','toggle','string'...

,'stop','background','white');

tic;%⽤来保存当前时间

%%%%%%%%%%%%%%%%%%%%%%禁忌搜索循环%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

whilep

ifCandidates>CityNum*(CityNum-1)/2

disp('候选解个数不⼤于n*(n-1)/2!');

break;

end

ALong(p)=Fun(dislist,S0);%当前解适配值

i=1;

A=zeros(Candidates,2);%解中交换的城市矩阵

%以下while的是⽣成随机的200X2的矩阵矩阵A。每⼀个元素都是在1-31之间的

whilei<=Candidates

M=CityNum*rand(1,2);

M=ceil(M);

ifM(1)~=M(2)

A(i,1)=max(M(1),M(2));

A(i,2)=min(M(1),M(2));

ifi==1

isa=0;

el

forj=1:i-1

ifA(i,1)==A(j,1)&&A(i,2)==A(j,2)

isa=1;

break;

el

isa=0;

end

end

end

if~isa

i=i+1;

el

end

end

el

end

end

%%%%%%%%产⽣领域解%%%%%%%%%%%%%%%%%%%%%%%

BestCandidateNum=100;%保留前BestCandidateNum个最好候选解

BestCandidate=Inf*ones(BestCandidateNum,4);

F=zeros(1,Candidates);

%这相当于是产⽣⼀个S0的邻域...

fori=1:Candidates

CandidateNum(i,:)=S0;%候选解集合。

CandidateNum(i,[A(i,2),A(i,1)])=S0([A(i,1),A(i,2)]);

F(i)=Fun(dislist,CandidateNum(i,:));

ifi<=BestCandidateNum

BestCandidate(i,2)=F(i);

BestCandidate(i,1)=i;

BestCandidate(i,3)=S0(A(i,1));

BestCandidate(i,4)=S0(A(i,2));

el

forj=1:BestCandidateNum

ifF(i)

BestCandidate(j,2)=F(i);

BestCandidate(j,1)=i;

BestCandidate(j,3)=S0(A(i,1));

BestCandidate(j,4)=S0(A(i,2));

break;

end

end

end

end

%对BestCandidate

[JL,Index]=sort(BestCandidate(:,2));

SBest=BestCandidate(Index,:);

BestCandidate=SBest;

%%%%%%%%%%%%%%%%%%%%%%%藐视准则%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ifBestCandidate(1,2)

BestL=BestCandidate(1,2);

S0=CandidateNum(BestCandidate(1,1),:);

BSF=S0;

form=1:CityNum

forn=1:CityNum

ifTabuList(m,n)~=0

TabuList(m,n)=TabuList(m,n)-1;%更新禁忌表

end

end

end

TabuList(BestCandidate(1,3),BestCandidate(1,4))=TabuLength;%更新禁忌表

el

fori=1:BestCandidateNum

ifTabuList(BestCandidate(i,3),BestCandidate(i,4))==0

S0=CandidateNum(BestCandidate(i,1),:);

form=1:CityNum

forn=1:CityNum

ifTabuList(m,n)~=0

TabuList(m,n)=TabuList(m,n)-1;%更新禁忌表

end

end

end

TabuList(BestCandidate(i,3),BestCandidate(i,4))=TabuLength;%更新禁忌表

break;

end

end

end

ArrBestL(p)=BestL;

fori=1:CityNum-1

plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'bo-');

holdon;

end

plot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ro-');

title(['迭代次数:',int2str(p),'优化最短距离:',num2str(BestL)]);

holdoff;

pau(0.005);

ifget(stop,'value')==1

break;

end

%存储中间结果为图⽚

if(p==1||p==5||p==10||p==20||p==60||p==150||p==400||p==800||p==1500||p==2000)

filename=num2str(p);

fileformat='jpg';

saveas(gcf,filename,fileformat);

end

p=p+1;%迭代次数加1

end

toc;%⽤来保存完成时间

BestShortcut=BSF;%最佳路线

theMinDistance=BestL;%最佳路线长度

t(stop,'style','pushbutton','string','clo','callback','clo(gcf)');

figure(2);

plot(ArrBestL,'b');

xlabel('迭代次数');

ylabel('⽬标函数值');

title('适应度进化曲线');

grid;

holdon;

%%figure(3)

%%plot(toc-tic,'b');

%%grid;

%%title('运⾏时间');

%%legend('BestSoFar','当前解');

%%%%%适配值函数%%%%%%%%%%%%%%%%%%%%%

functionF=Fun(dislist,s)

DistanV=0;

n=size(s,2);

fori=1:(n-1)

DistanV=DistanV+dislist(s(i),s(i+1));

end

DistanV=DistanV+dislist(s(n),s(1));

F=DistanV;