Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

nodeNum=length(needchange) - 1; %节点个数 不含回到中心的部分 TabuList=zeros(nodeNum); % 禁忌表(tabu…

  1. 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;                                                          %迭代次数加1
    

    end 解释代码的意思,逐行解释

  2. 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,重新进行搜索。

  3. 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 这个地方应该循环的是节点数,还是禁忌表长度

  4. Assistant

    循环的是节点数,因为每个禁忌操作(即交换算子)都对应着两个节点,所以需要循环遍历每个节点对应的禁忌操作在禁忌表中的位置,将其值减1以更新禁忌表。循环范围应该是从1到nodeNum-1,因为最后一个节点已经和第一个节点相连了,不需要再进行禁忌操作。而且,内层循环的起始位置是m+1,因为交换算子在生成时已经保证了不会对称交换,也就是[m,n]和[n,m]是不同的操作,只需要遍历其中一半就可以了。

  5. 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; % 是什么意思

  6. Assistant

    这段代码是更新禁忌表的操作,其目的是防止获得过去已经搜索过的解而陷入局部最优解。在这里,如果候选解中的交换算子没有在禁忌表中出现过(即TabuList(Candidate_Content(1,3),Candidate_Content(1,4))等于0),则将其在禁忌表中的值设为TabuLength,表示禁忌条件可以持续TabuLength个迭代。否则,将这个禁忌条件从禁忌表中删除,即将其值设置为0。这里的TabuLength可以理解为禁忌期的长度,在一个禁忌期内,相同的交换算子不能再被重复执行。若被重复执行,禁忌表中对应的禁忌条件值将大于0,因此需要等待它的值归0后才能再次执行。