nodeNum=length(needchange) - 1; %节点个数 不含回到中心的部分 TabuList=zeros(nodeNum); % 禁忌表(tabu…
- User
nodeNum=length(needchange) - 1; %节点个数 不含回到中心的部分 TabuList=zeros(nodeNum); % 禁忌表(tabu list) TabuLength=5; %禁忌表长度(tabu length) Candidates_Num=nodeNum*(nodeNum-1)/2; %候选集的个数 (全部邻域解个数) Candidates=zeros(Candidates_Num,nodeNum); %候选解集合 S0=1:nodeNum; %产生初始解 % S0=randperm(nodeNum); % px = 0.6; % 交换算子 逆转算子的选择阈值 0.6以上使用逆转算子 realS = [preroad,needchange([S0,length(needchange)])]; % 求解真实路径 init_T = fitness(realS, preroad, q, qmax, D, starttime, TW, ST, speed, f, sigma, b1, mu, gama, dT, Sout, Sin, Sm, p, pr, yongdu); %计算初始解的适应度值
% init_length=Fun(D,S0); %计算初始路径目标函数值 % str1=['初始解目标函数值 = ' num2str(init_T)]; % disp(str1) BSF=S0; %当前最佳解 BestL=Inf; %当前最佳解目标函数值 p=1; %记录迭代次数 StopL=1000; %最大迭代次数
swap_operator=create_Swap_Operator( nodeNum ); % 解中需要交换的两个节点坐标的矩阵, %即根据节点个数生成nodeNum*(nodeNum-1)/2个交换算子,即nodeNum*(nodeNum-1)/2行2列的矩阵,为后续生成候选集打下基础 %%%%%%%%%%%%%%%%%%%%%%禁忌搜索循环%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% while p<StopL %%%%%%%%产生领域解%%%%%%%%%%%%%%%%%%%%%%% Candidate_Content=zeros(Candidates_Num,4); %用于存储候选解的有关信息,第1列存储序号,第2列存储目标函数值,第3列第4列存储交换算子 F=zeros(1,Candidates_Num); %存储每一个候选解Candidates的目标函数值 %这相当于是产生一个S0的邻域... for i=1:Candidates_Num Candidates(i,:)=S0; %候选解集合。 %选择交换算子 if rand() > px Candidates(i,:) = two_opt_swap( swap_operator(i,1),swap_operator(i,2),Candidates(i,:) ); else Candidates(i,[swap_operator(i,2),swap_operator(i,1)])=S0([swap_operator(i,1),swap_operator(i,2)]); %候选解集合 end
% Candidates(i,[swap_operator(i,2),swap_operator(i,1)])=S0([swap_operator(i,1),swap_operator(i,2)]); %候选解集合。
F(i)=Fun(Candidates(i,:),preroad,needchange,nowroad, q, qmax, D, starttime, TW, ST, speed, f, sigma, b1, mu, gama, dT, Sout, Sin, Sm, p, pr, yongdu); %第i个候选解的目标函数值 Candidate_Content(i,1)=i; Candidate_Content(i,2)=F(i); Candidate_Content(i,3)=swap_operator(i,1); Candidate_Content(i,4)=swap_operator(i,2); end %对Candidate_Content的第2列(即目标函数值)从小到大进行排序 [~,Index]=sort(Candidate_Content(:,2)); temp=Candidate_Content(Index,:); Candidate_Content=temp; %%%%%%%%%%%%%%%%%%%%%%%藐视准则%%%%%%%%%%%%%%%%%%%%%%%%%%%% if Candidate_Content(1,2)<BestL BestL=Candidate_Content(1,2); S0=Candidates(Candidate_Content(1,1),:); BSF=S0; for m=1:nodeNum-1 for n=m+1:nodeNum if TabuList(m,n)~=0 TabuList(m,n)=TabuList(m,n)-1; % 更新禁忌表 end end end if TabuList(Candidate_Content(1,3),Candidate_Content(1,4))==0 TabuList(Candidate_Content(1,3),Candidate_Content(1,4))=TabuLength; % 更新禁忌表 else TabuList(Candidate_Content(1,3),Candidate_Content(1,4))=0; % 更新禁忌表 end else for i=1:Candidates_Num if TabuList(Candidate_Content(i,3),Candidate_Content(i,4))==0 S0=Candidates(Candidate_Content(i,1),:); for m=1:nodeNum-1 for n=m+1:nodeNum if TabuList(m,n)~=0 TabuList(m,n)=TabuList(m,n)-1; % 更新禁忌表 end end end TabuList(Candidate_Content(i,3),Candidate_Content(i,4))=TabuLength; % 更新禁忌表 break; end end end p=p+1; %迭代次数加1end 解释代码的意思,逐行解释
- Assistant
首先,本段代码是基于禁忌搜索算法实现的TSP路径规划,主要通过搜索候选解集合和使用禁忌表来找到最优解。
- nodeNum:表示节点的个数。
- TabuList:禁忌表,用于记录禁忌条件。
- TabuLength:禁忌表长度。
- Candidates_Num:候选解的个数,也就是全部邻域解的个数。
- Candidates:候选解集合。
- S0:初始解。
- realS:真实路径。
- init_T:初始解的适应度值。
- BSF:当前最佳解。
- BestL:当前最佳解目标函数值。
- p:迭代次数。
- StopL:最大迭代次数。
- swap_operator:交换算子,用于交换两个节点。
- Candidate_Content:候选解的信息,其中第1列存储序号,第2列存储目标函数值,第3列和第4列存储交换算子。
循环部分:
首先,通过交换算子将初始解S0生成候选解集合Candidates,然后计算每一个候选解的目标函数值F。接着,将每一个候选解的信息存储在Candidate_Content中。通过将Candidate_Content的第2列(即目标函数值)从小到大进行排序的方式,找到目标函数值最小的候选解,并将其作为下一次迭代的初始解S0。
如果找到的最小目标函数值小于当前最佳解BestL,则更新BestL和BSF(当前最佳解)。为了避免陷入局部最优解,需要使用禁忌表。先对所有的禁忌条件进行更新,然后将当前选择的候选解的交换算子记录到禁忌表中,以避免下一次搜索时重复选择同样的交换算子。如果找到的最小目标函数值大于等于当前最佳解BestL,需要按照一定策略(藐视准则)在候选解集合中选择下一个解进行搜索,同时更新禁忌表。最后,迭代次数加1,重新进行搜索。
- User
for m=1:nodeNum-1 for n=m+1:nodeNum if TabuList(m,n)~=0 TabuList(m,n)=TabuList(m,n)-1; % 更新禁忌表 end end end 这个地方应该循环的是节点数,还是禁忌表长度
- Assistant
循环的是节点数,因为每个禁忌操作(即交换算子)都对应着两个节点,所以需要循环遍历每个节点对应的禁忌操作在禁忌表中的位置,将其值减1以更新禁忌表。循环范围应该是从1到nodeNum-1,因为最后一个节点已经和第一个节点相连了,不需要再进行禁忌操作。而且,内层循环的起始位置是m+1,因为交换算子在生成时已经保证了不会对称交换,也就是[m,n]和[n,m]是不同的操作,只需要遍历其中一半就可以了。
- User
if TabuList(Candidate_Content(1,3),Candidate_Content(1,4))==0 TabuList(Candidate_Content(1,3),Candidate_Content(1,4))=TabuLength; % 更新禁忌表 else TabuList(Candidate_Content(1,3),Candidate_Content(1,4))=0; % 更新禁忌表 end 蔑视规则种等于0, TabuList(Candidate_Content(1,3),Candidate_Content(1,4))=TabuLength; % 是什么意思
- Assistant
这段代码是更新禁忌表的操作,其目的是防止获得过去已经搜索过的解而陷入局部最优解。在这里,如果候选解中的交换算子没有在禁忌表中出现过(即TabuList(Candidate_Content(1,3),Candidate_Content(1,4))等于0),则将其在禁忌表中的值设为TabuLength,表示禁忌条件可以持续TabuLength个迭代。否则,将这个禁忌条件从禁忌表中删除,即将其值设置为0。这里的TabuLength可以理解为禁忌期的长度,在一个禁忌期内,相同的交换算子不能再被重复执行。若被重复执行,禁忌表中对应的禁忌条件值将大于0,因此需要等待它的值归0后才能再次执行。