LNS（大规模大邻域搜索）（含AI创作）（背景与VNS相同）

LNS

Large Neighborhood Search（LNS）是一种启发式搜索算法，用于解决组合优化问题，例如旅行商问题（TSP）等。与其他启发式算法相比，LNS的特点在于它通过在搜索过程中动态地探索大规模的邻域来寻找更优的解决方案。以下是关于LNS的一些重要概念和特点：

1. 基本思想：LNS的基本思想是通过在搜索过程中使用大型邻域结构来快速发现高质量的解。它采用了一种分解和重组的策略，将问题分解成子问题，并在这些子问题上应用不同的搜索策略，以找到更优的解。
2. 邻域结构：LNS通过定义一系列不同的邻域结构来探索解空间。这些邻域结构可以是不同的搜索策略或者不同的问题约束条件，例如路径中的节点集合、路径顺序等。LNS的关键在于使用大型、多样化的邻域结构，以便在搜索过程中尽可能地探索解空间。
3. 扰动和修复：在LNS的搜索过程中，通常会对当前解进行扰动以引入新的变化，并尝试在扰动后的解空间中寻找更优的解。扰动操作可以是随机的、有针对性的或者基于一定的规则。一旦获得了新的解，LNS通常会应用一种修复策略来确保新解满足问题的约束条件。
4. 启发式搜索：尽管LNS的搜索空间很大，但它通常不会盲目地搜索整个空间。相反，它通常会根据一些启发式规则或者经验知识来指导搜索，以提高搜索效率。这些启发式规则可以基于问题的特点、先前的搜索经验或者其他启发式信息。
5. 性能分析：LNS的性能通常受到邻域结构的选择、扰动和修复策略的设计以及启发式搜索规则的影响。因此，在使用LNS解决问题时，需要进行对比实验和性能分析，以确定最合适的参数设置和算法配置。

总的来说，LNS是一种强大的启发式搜索算法，适用于解决各种组合优化问题。通过使用大型的邻域结构和灵活的搜索策略，LNS能够在相对较短的时间内找到高质量的解，因此在实际应用中具有广泛的应用前景。

LNS与VNS对比

1. 相似性和补充性：LNS和VNS都属于多邻域搜索（Multi-Neighborhood Search）算法家族的一部分，它们在搜索过程中都涉及到对解空间的多次搜索，通过改变邻域结构来寻找更优的解。因此，它们在算法原理和实现方法上具有一定的相似性，可以互相参考和借鉴。同时，它们在具体的邻域定义和搜索策略上也可能存在一些差异，这使得它们可以相互补充，提供更丰富的搜索策略。
2. 解决同一类问题：LNS和VNS都是通用的启发式搜索算法，适用于解决各种组合优化问题，包括TSP问题。因此，将它们一起研究可以更加深入地探索它们在解决同一类问题时的优劣势，并为问题的解决提供多种选择。
3. 对比实验和性能分析：通过将LNS和VNS作为研究对象，你可以设计对比实验来比较它们在解决TSP问题时的性能表现。通过对比实验，你可以更加客观地评估它们的优劣势，并可能发现哪种算法更适合解决特定类型的TSP问题。
4. 理论研究和算法改进：研究LNS和VNS还可以促进对这两种算法的理论分析和改进研究。通过深入理解它们的工作原理和性能特点，你可以提出新的改进策略和优化方法，从而进一步提高它们在解决TSP问题时的效率和性能。

综上所述，将LNS和VNS作为一起研究可以帮助你更全面地理解这两种算法的性能和特点，并为解决实际问题提供更多的选择和可能性。

LNS的核心

LNS的核心在与破坏和修复

LNS算法通过替换问题的一部分来探索解空间，这一过程分为“破坏”（Destroy）和“修复”（Repair）两个关键步骤。

1. 破坏步骤：这一步的目的是从当前解中移除一部分元素，从而形成一个部分破坏的解。这可以通过随机选择一组节点并将它们从当前的路径中移除来实现，或者采用更复杂的策略来选择哪些节点被移除，以期望找到更好的搜索路径。
2. 修复步骤：在破坏步骤之后，需要通过添加缺失的元素来“修复”解，恢复其为一个完整的解。这一步骤通常涉及到启发式或元启发式算法来选择如何最佳地重新插入被移除的节点，以形成新的、可能更优的解。修复步骤的关键在于如何有效地选择插入的顺序和位置，以达到最小化路径长度的目的。

LNS算法的效果很大程度上依赖于破坏和修复策略的选择。破坏策略需要足够大胆，以确保算法能够跳出局部最优解，探索到解空间中更远的区域；而修复策略则需要足够聪明，能够有效地重建解，寻找到更优的解决方案。不同的破坏和修复策略组合可以应对不同的问题场景，因此在应用LNS解决TSP问题时，经常需要对这些策略进行调整和优化，以适应具体问题的特性

破坏：

修复情况如下：

流程图

这图是ai创作的，不过大差不差的，想看正常的自己查（小摆一下，复试太！累！了！^^）

函数设计

构造初始解

跟VNS一样的方法。

初始解是算法开始搜索的起点，它可以通过多种方式构造，包括以下几种常见方法：

1. 随机生成：可以随机生成一个初始解，这通常是一种简单而快速的方法。但是，随机生成的初始解可能会比较差，因此需要后续的搜索来改进。
2. 启发式算法：可以使用其他启发式算法（如最近邻算法、插入算法、交换算法等）来生成一个初始解。这些算法通常会根据一些启发式规则来构建初始解，以期望得到相对较好的起点。
3. 基于已知信息的构建：如果问题的特性允许，可以根据已知的信息来构建初始解。例如，对于VRP，可以基于顾客之间的距离或需求来构建初始路线。

初始解的质量对于变邻域搜索算法的性能至关重要。一个好的初始解可以加速算法的收敛，而一个差的初始解可能需要更多的搜索时间才能找到更优的解。因此，在实际应用中，通常会尝试不同的初始解构造方法，以找到最好的初始解来启动变邻域搜索算法的搜索过程。现在用贪婪算法来举例子

1. 初始化一个空的解，表示还没有选择任何元素或路径。
2. 从未选择的元素中选择一个元素，通常是基于某种启发式规则来做出选择。这个规则可能会考虑元素之间的成本、距离、权重等信息，以选择最有希望的元素。
3. 将选定的元素添加到当前解中。
4. 重复步骤2和步骤3，直到满足某个终止条件，例如所有元素都被选择完毕。function [init_route,init_len]=construct_route(dist)%% 贪婪算法构造TSP的初始解%输入dist： 距离矩阵 %输出init_route： 贪婪算法构造的初始路线%输出init_len： init_route的总距离 N=size(dist,1);%城市数目for i = 1:N for j = 1:N if i == j dist(i,j)=inf; end endendunivisited=1:N;%初始未被安排的城市集合visited=[];%初始已被安排的城市集合min_dist=min(min(dist));%找出距离矩阵中的最小值[row,col]=find(dist==min_dist);%在dist中找出min_dist所对应的行和列first=row(1);%将min_dist在dist中所对应行序号作为起点univisited(univisited==first)=[];%将first从unvisit中删除visited=[visited,first];%%把first添加到visit中pre_point=first;%%将fisrt赋值给pre_pointwhile ~isempty(univisited) pre_dist=dist(pre_point,:); %pre_point与其它城市的距离 pre_dist(visited)=inf;%将pre_point与已经添加进来的城市之间的距离设位无穷大 [~,pre_point]=min(pre_dist); %找出pre_dist中的最小值 univisited(univisited==pre_point)=[];%将pre_point从unvisit中删除 %%第一个pre_point只是为了找到最小距离的起点序号,后面用于储存pre_dist %%第二个pre_point储存了pre_dist中的最小值然后并将其赋予[]值 visited=[visited,pre_point]; %把pre_point添加到visit中endinit_route=visited;init_len=route_length(init_route,dist); %计算init_route的总距离end

路线距离计算

function len=route_length(route,dist)
%% 计算一条路线总距离
%输入route：            一条路线
%输入dist：             距离矩阵
%输出len：              该条路线总距离
    N=numel(route);
    route=[route route(1)];
    len=0;
    for k=1:N 
        i=route(k);
        j=route(k+1); 
        len=len+dist(i,j); 
    end
end

dist这里已经用了pdist函数进行计算，不清楚的可以在命令行里输入doc pdist去查查函数使用格式。顺序就是x是1行，y是1行，把x与y组在一起，先用pdist计算每个位置的距离，再用squareform 进行Format distance matrix。

x=dataset(:,2);%x坐标
y=dataset(:,3);%y坐标
vertexes=dataset(:,2:3);%提取各个城市的xy坐标
h=pdist(vertexes);
dist=squareform(h);%距离矩阵

破坏解

破坏的目的是据城市数量和随机选择的条件，确定移除最多和最少的城市数量，即

       L 
      
      
      
        m 
       
      
        a 
       
      
        x 
       
      
     
    
   
     L_{max} 
    
   
 Lmax​和 
  
   
    
     
     
       L 
      
      
      
        m 
       
      
        i 
       
      
        n 
       
      
     
    
   
     L_{min} 
    
   
 Lmin​，然后根据这些数量来移除城市，以满足特定条件。

步骤如下：

1. 确定移除最多和最少的城市数量，记为 L m a x L_{max} Lmax​和 L m i n L_{min} Lmin​。
2. 随机选择 L m a x L_{max} Lmax​和 L m i n L_{min} Lmin​中的任意一个整数记为 A A A，同时记城市数目为 N N N。
3. 从当前解 r o u t e route route中随机选择一个城市 B B B作为即将移除的相连接 A A A个城市的参考城市。
4. 标记 B B B在当前解的索引记为 C C C，以起始点 r o u t e ( 1 ) route(1) route(1)为界限计算在 r o u t e route route中 B B B左侧的城市数目即 B L N = C − 1 B_{LN}=C-1 BLN​=C−1，同理 B R N = N − C B_{RN}=N-C BRN​=N−C。
5. 如果 B L N ≤ B R N B_{LN}\leq B_{RN} BLN​≤BRN​，执行以下步骤：- 如果 B L N B_{LN} BLN​小于 L − 1 L-1 L−1并且 B R N B_{RN} BRN​小于 L − 1 L-1 L−1，则左右两侧都不足以提供 L − 1 L-1 L−1个城市。在这种情况下，我们需要从左侧移除一些城市，计算出需要移除的数量 n L n_{L} nL​，然后根据剩余的数量设置右侧需要移除的城市数量 n R n_{R} nR​。- 如果 B L N B_{LN} BLN​大于等于 L − 1 L-1 L−1并且 B R N B_{RN} BRN​大于等于 L − 1 L-1 L−1，则左右两侧都足够提供 L − 1 L-1 L−1个城市。这时，我们会随机决定从左侧移除多少个城市，并计算右侧需要移除的城市数量。- 如果一侧城市数量足够，而另一侧不足，则根据具体情况进行分配，引入一些随机性。
6. 如果 B L N > B R N B_{LN}>B_{RN} BLN​>BRN​，表示右侧城市数量超过左侧城市数量。在这种情况下，我们会根据具体情况进行处理，以确保最终剩下的城市数量为 L − 1 L-1 L−1function[Sdestroy,removed]=destroy(route)%% 破坏函数destroy根据从当前解中连续移除若干个城市%输入route： 当前解，一条路线%输出Sdestroy： 移除removed中的城市后的route%输出removed： 被移除的城市集合N=numel(route);%当前解中城市数目Lmin=1;%一条路径中所允许移除最小的城市数目Lmax=min(ceil(N/2),25);%一条路径中所允许移除最大的城市数目visit=ceil(rand*N);%从当前解中随机选出要被移除的城市L=Lmin+ceil((Lmax-Lmin)*rand);%计算在该条路径上移除的城市的数目findv=find(route==visit,1,'first');%找出visit在route中的位置vLN=findv-1;%visit左侧的城市个数vRN=N-findv;%visit右侧的城市个数%如果vLN小if vLN<=vRN %如果vLN小于L-1并且vRN小于L-1，则两侧都不足以提供L-1个城市。在这种情况下，nL被设置为L-1-vLN，表示左侧需要移除的城市数量，而nR被设置为L-1-nL，表示右侧需要移除的城市数量。%如果vLN大于等于L-1并且vRN大于等于L-1，则两侧都足够提供L-1个城市。在这种情况下，nL被设置为随机值，表示左侧需要移除的城市数量，而nR被设置为L-1-nL，表示右侧需要移除的城市数量。%如果一侧足够提供L-1个城市，而另一侧不足，那么可以根据具体情况分配。这里也引入了一定的随机性。if vRN < L-1&& vLN < L-1 nR=L-1-vLN+round(rand*(vRN-L+1+vLN)); nL=L-1-nR;%visit左侧要移除城市的数目elseif(vRN>L-1)&&(vLN>L-1) nR=round(rand*vLN);%visit右侧要移除城市的数目 nL=L-1-nR;%visit左侧要移除城市的数目else nR=L-1-vLN+round(rand*vLN); nL=L-1-nR;%visit左侧要移除城市的数目endelse%如果vRN小if(vLN<L-1)&&(vRN<L-1) nL=L-1-vRN+round(rand*(vLN-L+1+vRN)); nR=L-1-nL;%visit右侧要移除城市的数目elseif(vLN>L-1)&&(vRN>L-1) nL=round(rand*vRN);%visit左侧要移除城市的数目 nR=L-1-nL;%visit右侧要移除城市的数目else nL=L-1-vRN+round(rand*vRN); nR=L-1-nL;%visit右侧要移除城市的数目endendremoved=route(findv-nL:findv+nR);%移除城市的集合，即包括visit在内的连续L个城市Sdestroy=route;%复制routefori=1:L Sdestroy(Sdestroy==removed(i))=[];%将removed中的所有城市从route中移除endend

修复解

理解修复解前需解释"插入成本"和“遗憾值”（这部分为ai创作）

插入成本指的是将一个节点加入到路径中某个位置时所增加的额外成本。在TSP中，成本通常是路径长度的增加，即加入这个节点后，整个路径长度增加了多少。例如，如果你有一个节点序列A-B-C，并且考虑将节点X插入到B和C之间，插入成本就是路径AXC与原路径ABC长度之差的增加量。 插入成本的计算公式可以简化为：
插入成本 = 距离(A,X) + 距离(X,C) - 距离(A,C)

这个成本帮助算法评估在不同位置插入节点的效率，目的是找到成本最小的插入位置。

function[new_route,up_delta]=ins_route(visit,dist,route)%% 将visit插回到插入成本最小的位置后的路线，同时还计算出插入到各个插入位置的插入成本%输入visit：               待插入的城市%输入dist：                距离矩阵%输入route：               被插入路径%输出new_route：           将visit插入到route最小插入成本位置后的解%输出up_delta：            将visit插入到route中各个插入位置后的插入成本从小到大排序后的结果
lr=numel(route);%当前路线城市数目
rc0=zeros(lr+1,lr+1);%记录插入城市后的路径
delta0=zeros(lr+1,1)'%记录插入城市后的增量fori=1:lr+1ifi== lr+1
        rc =[route visit];elseifi==1
        rc =[visit route];else 
        rc =[route(1:i-1) visit route(i:end)];endrc0(i:end)=rc;
    dif=route_length(rc,dist)-route_length(route,dist);delta0(i,1)=dif;end
up_delta=sort(delta0);[~,ind]=min(delta0);
new_route=rc0(ind,:);end

遗憾值是一个衡量指标，用来评估不将节点插入最佳位置所可能失去的价值。具体来说，它是最优插入位置的成本与次优插入位置的成本之差。遗憾值的概念基于这样一个假设：如果你没有按照最优成本插入节点，那么你可能会“遗憾”没有选择一个更好的位置，因为这将导致路径成本显著增加。

遗憾值的计算公式可以表示为：
遗憾值 = 次优插入成本 - 最优插入成本

在选择插入位置时，高遗憾值意味着第二最好的选择与最好选择之间有较大差距，揭示了选择最优位置的重要性。在一些策略中，算法可能优先考虑那些遗憾值较高的插入决策，因为这样做可能会在全局上获得更优的路径。

1. 定义一个被移除的城市集合命名为remove，同时定义一个经过“破坏”操作后的解，记作 S d e s t r o y S_{destroy} Sdestroy​。
2. 初始设置“修复”后的解 S r e p a i r S_{repair} Srepair​等于 S d e s t r o y S_{destroy} Sdestroy​，即 S r e p a i r = S d e s t r o y S_{repair} = S_{destroy} Srepair​=Sdestroy​。
3. 检查remove集合是否为空。如果为空，跳转到步骤6；如果不为空，继续执行步骤4。
4. 计算remove集合中城市的数量，记为nr。对于remove中的每一个城市，计算将其重新插入到 S r e p a i r S_{repair} Srepair​中的“遗憾值”（regret）。
5. 从所有计算得到的遗憾值中，找出最大的遗憾值，并记录对应的索引值 m a x i n d e x max_{index} maxindex​。据此确定将要重新插入的城市 r e i n s e r t c i t y = r e m o v e ( m a x i n d e x ) reinsert_{city} = remove(max_{index}) reinsertcity​=remove(maxindex​)，并将 r e i n s e r t c i t y reinsert_{city} reinsertcity​插入回 S r e p a i r S_{repair} Srepair​中，选择“插入成本”最小的位置进行插入。
6. 更新remove集合，移除已经重新插入的城市 r e m o v e ( m a x i n d e x ) = [ ] remove(max_{index}) = [\ ] remove(maxindex​)=[ ]，然后回到步骤3。
7. 当“修复”过程结束时，返回修复后的解 S r e p a i r S_{repair} Srepair​。

function[Srepair,repair_length]=repair(removed,Sdestroy,dist)%% 修复函数repair依次将removed中的城市插回路径中%先计算removed中各个城市插回当前解中所产生最小增量，然后再从上述各个最小增量的城市中%找出一个(距离增量第2小-距离增量第1小)最大的城市插回，反复执行，直到全部插回%输入removed：                 被移除城市的集合%输入Sdestroy：                “破坏”后的解%输入dist：                    距离矩阵%输出Srepair：                 “修复”后的解%输出repair_length：           Srepair的总距离
Srepair=Sdestroy;while~isempty(removed)% 表示只要 removed 中还有被移除的城市，循环就会继续执行
    nr=numel(removed);%移除集合中城市数目
    regret=zeros(nr,1);%存储removed各城市插回最“好”插回路径后的遗憾值增量%逐个计算removed中的城市插回当前解中各路径的目标函数值增量fori=1:nr
        visit =removed(i);%当前要插回的城市[~,up_delta]=ins_route(visit,dist,Srepair);%将visit插回到插入成本最小的位置后的路线，同时还计算出插入到各个插入位置的插入成本
        de12=up_delta(2)-up_delta(1);%up_delta是排序后的，不是字面意思上的第二位减去第一位regret(i)=de12;%更新当前城市插回最“好”插回路径后的遗憾值end[~,max_index]=max(regret);%找出遗憾值最大的城市序号
    reinsert_city=removed(max_index);%removed中准备插回的城市
    Srepair=ins_route(reinsert_city,dist,Srepair);%将reinsert_city插回到Srepairremoved(max_index)=[];%将removed(firIns)城市从removed中移除end
repair_length=route_length(Srepair,dist);%计算Srepair的总距离end

绘图函数

functionplot_route(route,x,y)%% TSP路线可视化%输入route：           一条路线%输入x,y：             x,y坐标
figure
route=[route route(1)];plot(x(route),y(route),'k-o','MarkerSize',10,'MarkerFaceColor','w','LineWidth',1.5);xlabel('x');ylabel('y');end

这里的图很丑，你可以用figurebest进行修图，具体去搜微信公众号图通道，一个matlab修图插件

主函数

tic
clc
clear
close all
%% 输入数据
dataset=importdata('input.txt');%数据中，每一列的含义分别为[序号，x坐标，y坐标]
x=dataset(:,2);%x坐标
y=dataset(:,3);%y坐标
vertexes=dataset(:,2:3);%提取各个城市的xy坐标
h=pdist(vertexes);
dist=squareform(h);%距离矩阵%% 参数初始化
MAXGEN=300;%最大迭代次数%% 构造初始解[Sinit,init_len]=construct_route(dist);%贪婪构造初始解
init_length=route_length(Sinit,dist);
str1=['初始总路线长度 =  'num2str(init_length)];disp(str1)%% 初始化当前解和全局最优解
Scurr = Sinit;
curr_length = init_length;
Sbest=Sinit;
best_length = init_length;%% 主循环
gen =1;
BestL=zeros(MAXGEN,1);while gen < MAXGEN
    %%破坏解[Sdestroy,removed]=destroy(Scurr);%%修复解[Srepair,repair_length]=repair(removed,Sdestroy,dist);if repair_length<curr_length
        Scurr=Srepair;
        curr_length=repair_length;endif curr_length<best_length
        Sbest=Scurr;
        best_length=curr_length;end%% 打印当前代全局最优解disp(['第',num2str(gen),'代最优路线总长度 =  'num2str(best_length)])BestL(gen,1)=best_length;%% 计数器加1
    gen=gen+1;end
str2=['搜索完成！ 最优路线总长度 =  'num2str(best_length)];disp(str2)%% 画出优化过程图
figure;plot(BestL,'LineWidth',1);title('优化过程')xlabel('迭代次数');ylabel('总距离');%% 画出全局最优路线图plot_route(Sbest,x,y);
toc

POI转换

有的同学可能直接用规划云里面的POI数据作为二维坐标集，但经纬度的换算是不一样的所以需要转换 类似这种

clc
clear
close all

% 经度和纬度坐标
lon = [104.054572, 104.150916, 104.059763, 104.056257, 104.034848, 104.08517, 104.147618];
lat = [30.652582, 30.743319, 30.669938, 30.651897, 30.666397, 30.663776, 30.635065];

% 使用UTM投影参数（根据坐标中心点的纬度和经度）
center_lat = mean(lat);
center_lon = mean(lon);
utmZone = utmzone(center_lat, center_lon);
utmStruct = defaultm('utm'); % 创建一个默认的UTM投影结构体
utmStruct.zone = utmZone; % 设置UTM区域
utmStruct = defaultm(utmStruct); % 更新结构体

% 转换为平面坐标（XY坐标）
[x, y] = mfwdtran(utmStruct, lat, lon); % 使用投影转换函数

% 输出平面坐标
xy_coordinates = [x', y']; % 转置为每行一个点
disp(xy_coordinates);