精华内容
下载资源
问答
  • 本资源用matlab实现了粒子群算法,并解决了旅行商问题。其中给出了TSP问题最优解的路径图以及收敛次数等信息。
  • 遗传算法是研究TSP问题中最为广泛的一种算法,它具有全局搜索...本文基于遗传算法的交叉变异设计了混合粒子群算法,通过对TSP问题求解分析,证实该方法提高了标准粒子群的搜索能力,获得了较高的收敛速度和近似最优解。
  • 粒子群算法解决TSP问题,包含所有matlab程序
  • 基于动态粒子群算法TSP求解 基于动态粒子群算法TSP求解 基于动态粒子群算法TSP求解 基于动态粒子群算法TSP求解
  • 粒子群算法解决TSP问题,里面有详细的代码介绍以及相应的数据附件。
  • 本科毕业论文的程序,Matlab编写,有51个城市,城市地址可改,城市的数量也可改!!并且和GA的结果进行对比!!
  • 遗传算法中的交叉和变异思想恰好能应用到此处,比如说个体粒子先和个体最优交叉产生一个新的粒子,当然这里如果新产生的粒子没有原来粒子好,我们就舍弃这个新的粒子;与个体最优交叉完后,新的粒子还需与群体最优...
  • MATLAB源码集锦-混合粒子群算法求解TSP问题代码
  • 粒子群算法解决TSP问题,路径规划 matlab代码
  • 遗传算法里多个个体组成一个种群、蚁群算法的蚂蚁、粒子群算法的粒子都是群优化算法的体现。 本文分别利用以上三种算法来解决31个城市的TSP问题。 二、遗传算法解决TSP问题 遗传算法简介: 遗传算法是一种...

    一、引言

    旅行商问题(Traveling Salesman Problem)就是一个经销商从n个城市中的某一城市出发,不重复的走完其余的n-1个城市并回原出发点,求所有可能的路径中路径长度最短的一条。TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。当城市数较大时,TSP难以用遍历的方法找到最短路径。

    遗传算法、蚁群算法、粒子群算法都是群优化算法,也就是说我们会在解空间里面同时设置许多个个体然后来组成一个群体来进行搜索寻找最优解。好比我们现在有一个任务,周围有好多个人寻找搜索,而不是一个人寻找搜索。遗传算法里多个个体组成一个种群、蚁群算法的蚂蚁、粒子群算法的粒子都是群优化算法的体现。

    本文分别利用以上三种算法来解决31个城市的TSP问题。

    二、遗传算法解决TSP问题

    遗传算法简介:
    遗传算法是一种通过模拟自然进化过程搜索最优解的方法。基本步骤包括:编码、产生初始种群、计算适应度函数值、选择、交叉、变异、产生下一代种群、解码。

    适应度函数用来评价个体的性能到底好不好;选择体现进化,更优的个体生存下来进化到下一代可能性比较大;交叉变异保持了样本的多样性,避免算法陷入局部寻优局部求解的误区。

    计算适应度函数值->选择->交叉->变异 不停的循环迭代,最后直到满足一定的终止条件。

    流程图如下:
    在这里插入图片描述

    用来解决TSP问题:

    1.编码:在TSP问题中直接用一条路径来对应基因的编码是最简单的表示方式。例如:旅程(3->2->5->8->4->1->6->7)可以直接编码表示为(3 2 5 8 4 1 6 7)

    2.适应度函数:计算路径的距离

    3.选择算子:轮盘赌法。注意路径越短被选择的概率应该越高,反之路径越长被选择的概率应该越低,因此可以将路径的距离长度取倒数后,再进行轮盘赌选择。

    4.交叉算子:基于路径表示的编码方法,要求每个的染色体编码中不允许有重复的基因码,也就是每个城市只能访问一次。因此基本遗传算法的交叉操作不再适用。

    本文选用部分匹配交叉法(Partial-MappedCrossover),原理如下:
    首先随机产生两个交叉点,定义这两点间的区域为匹配区域,并交换两个父代的匹配区域,如下所示:

    父代A:12|3456|789
    父代B:54|6921|783

    交换后变为:

    tempA:12|6921|789
    tempB:54|3456|783

    对于tempA、tempB中匹配区域以外出现的数码重复,要依据匹配区域内的位置建立映射关系,然后替换,映射关系:
    1<->6<->3
    2<->5
    9<->4

    最终结果:

    子代A:35|6921|784
    子代B:29|3456|781

    5.变异算子:在TSP问题中基于二进制编码的变异操作不适用,不能直接将其中一个数码变成另外一个数码(会出现城市的重复)。因此可以随机的在路径抽取两个城市,然后交换他们的位置。这样就实现了个体编码的变异。

    结果显示:
    在这里插入图片描述

    在这里插入图片描述
    matlab代码:

    %% 1.清空环境变量
    clear all;
    clc;
    
    %% 2.导入数据
    load citys_data.mat;          %数据集的变量名为citys
    
    %% 3.计算城市间相互距离
    n=size(citys,1);
    D=zeros(n,n);
    
    for i=1:n
        for j=i+1:n
            D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));
            D(j,i)=D(i,j);
        end
    end
    
    %% 4.初始化参数
    m=2000;                         %种群个数
    pop=zeros(m,n);                 %种群
    crospro=0.8;                    %交叉概率
    mutpro=0.1;                     %变异概率
    gen=1;                          %迭代计数器
    genmax=2000;                    %最大迭代次数
    fitness=zeros(m,1);             %适应度函数值
    Route_best=zeros(genmax,n);     %各代最佳路径
    Length_best=zeros(genmax,1);    %各代最佳路径的长度
    Length_ave=zeros(genmax,1);     %各代路径的平均长度
    
    %% 5.产生初始种群
    % 5.1随机产生初始种群
    for i=1:m
        pop(i,:)=randperm(n);
    end
    
    % 5.2计算初始种群适应度函数值
    for i=1:m
        for j=1:n-1
            fitness(i)=fitness(i) + D(pop(i,j),pop(i,j+1));
        end
        fitness(i)=fitness(i) + D(pop(i,end),pop(i,1));
    end
    
    % 5.3计算最短路径及平均距离
    [min_Length,min_index]=min(fitness);
    Length_best(1)=min_Length;
    Route_best(1,:)=pop(min_index,:);
    Length_ave(1)=mean(fitness);
    
    %% 6.迭代寻找最佳路径
    while gen<=genmax
        % 6.1更新迭代次数
        gen=gen+1;
    
        % 6.2选择算子(轮盘赌法)
        P=1./fitness;
        P=P/sum(P);        %计算每一个城市的概率
        Pc=cumsum(P);      %计算累积概率
    
        popnew=zeros(m,n);
        for i=1:m
            target_index=find(Pc>=rand);
            target=pop(target_index(1),:);
            popnew(i,:)=target;
        end
    
        % 6.3交叉算子(部分匹配交叉)
        for i=1:2:n   %两两之间相互交叉
            if crospro>rand  %判断是否进行交叉
                child1path=zeros(1,n);
                child2path=zeros(1,n);
    
                setsize=floor(n/2)-1;      %匹配区域城市的数量
                offset1=randi(setsize);    %匹配区域的下边界
                offset2=offset1+setsize-1; %匹配区域的上边界
    
                %匹配区域
                for j=offset1:offset2
                    child1path(j)=popnew(i+1,j);
                    child2path(j)=popnew(i,j);
                end
    
                % 非匹配区域
                for j=1:offset1-1
                    child1path(j)=popnew(i,j);
                    child2path(j)=popnew(i+1,j);
                end
    
                for j=offset2+1:n
                    child1path(j)=popnew(i,j);
                    child2path(j)=popnew(i+1,j);
                end
    
                % 子代1冲突检测
                for j=offset1:offset2
                    if ~ismember(child1path(j),popnew(i,offset1:offset2)) %不在交叉段内
                        %寻找映射关系
                        a1=child1path(j);
                        a2=popnew(i,j);
                        while ismember(a2,child1path(offset1:offset2))
                            temp_index=find(popnew(i+1,:)==a2);
                            a1=a2;
                            a2=popnew(i,temp_index);  
                        end 
                        %寻找重复数字位置
                        b1=find(child1path==child1path(j));
                        if length(b1)>1
                            if b1(1)>offset2||b1(1)<offset1
                                change_index=b1(1);
                            else
                                change_index=b1(2);
                            end
                        end
                        %替代重复数字
                        child1path(change_index)=a2;                
                    end
                end
    
                % 子代2冲突检测(同上)
                for j=offset1:offset2
                    if ~ismember(child2path(j),popnew(i+1,offset1:offset2)) %不在交叉段内
                        %寻找映射关系
                        a1=child2path(j);
                        a2=popnew(i+1,j);
                        while ismember(a2,child2path(offset1:offset2))
                            temp_index=find(popnew(i,:)==a2);
                            a1=a2;
                            a2=popnew(i+1,temp_index);  
                        end 
                        %寻找重复数字位置
                        b2=find(child2path==child2path(j));
                        if length(b2)>1
                            if b2(1)>offset2||b2(1)<offset1
                                change_index=b2(1);
                            else
                                change_index=b2(2);
                            end
                        end
                        %替代重复数字
                        child2path(change_index)=a2;                
                    end
                end
    
                popnew(i,:)=child1path;
                popnew(i+1,:)=child2path;
            end
        end
    
        % 6.4变异算子
        for i=1:m
            if mutpro>rand %判断是否变异
                %随机抽两个数字
                y=round(rand(1,2)*(n-1)+1);
                %交换位置
                temp=popnew(i,y(1));
                popnew(i,y(1))=popnew(i,y(2));
                popnew(i,y(2))=temp;
            end
        end
    
        % 6.5计算新一代种群适应度函数值
        pop=popnew;
        fitness=zeros(m,1);
        for i=1:m
            for j=1:n-1
                fitness(i)=fitness(i) + D(pop(i,j),pop(i,j+1));
            end
            fitness(i)=fitness(i) + D(pop(i,end),pop(i,1));
        end
    
        % 6.6计算最短路径及平均距离
        [min_Length,min_index]=min(fitness);
        Length_ave(gen)=mean(fitness);
        if min_Length<Length_best(gen-1)
            Length_best(gen)=min_Length;
            Route_best(gen,:)=pop(min_index,:);
        else
            Length_best(gen)=Length_best(gen-1);
            Route_best(gen,:)=Route_best(gen-1,:);
        end
    
    end
    
    %% 7.结果显示
    best_route=Route_best(end,:);
    best_length=Length_best(end,:);
    disp(['最短距离: ' num2str(best_length)]);
    disp(['最短路径: ' num2str(best_route)]);
    
    %% 8.绘图
    figure(1)
    plot([citys(best_route,1);citys(best_route(1),1)],[citys(best_route,2);citys(best_route(1),2)],'o-')
    for i=1:size(citys,1)
        text(citys(i,1),citys(i,2),[' ' num2str(i)]); 
    end
    text(citys(best_route(1),1),citys(best_route(1),2),'     起点');
    text(citys(best_route(end),1),citys(best_route(end),2),'     终点');
    xlabel('城市位置横坐标')
    ylabel('城市位置纵坐标')
    title(['遗传算法优化路径(最短距离:' num2str(best_length) ')'])
    
    figure(2)
    plot(1:genmax+1,Length_ave,'r:',1:genmax+1,Length_best,'b-')
    legend('平均距离','最短距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('各代最短距离与平均距离对比')
    

    三、蚁群算法解决TSP问题

    蚁群算法简介:
    蚁群算法灵感来源于蚂蚁在寻找食物过程中的行为。蚂蚁在觅食时会在经过的路径上释放信息素,并且能够感知环境中信息素的含量浓度大小。蚂蚁释放的信息素浓度大小表征了这条路径距离食物的远近:这条路径距离越短,蚂蚁释放的信息素浓度越高。蚂蚁觅食时会以较大概率选择信息素浓度较高的路径,并且在走过这条路径时会释放自己身上的信息素。这样这条路走的蚂蚁越来越多,信息素浓度越高,就会形成一个正反馈。同时路径上信息素的浓度会随着时间的推进而衰减。

    蚁群算法通过 产生路径表->更新信息素->清空路径表 不停的循环迭代来寻找最优解。信息素最大的路径代表最短路径。

    流程图如下:
    在这里插入图片描述

    用来解决TSP问题:
    1.产生路径表:在计算各个城市的访问概率后,用轮盘赌选择下一个访问城市,避免局部最优。

    2.更新信息素:对于蚂蚁释放的信息素浓度,本文选用蚁周模型。

    结果显示:
    在这里插入图片描述
    在这里插入图片描述
    matlab代码:

    %% 1.清空环境变量
    clear all;
    clc;
    
    %% 2.导入数据
    load citys_data.mat;          %数据集的变量名为citys
    
    %% 3.计算城市间相互距离
    n=size(citys,1);
    D=zeros(n,n);
    
    for i=1:n
        for j=1:n
            if i~=j
                D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));
            else
                D(i,j)=1e-4;
            end
        end
    end
    
    %% 4.初始化参数
    m=50;                         %蚂蚁数量
    alpha=1;                      %信息素重要程度因子
    beta=5;                       %启发函数重要程度因子
    rho=0.1;                      %信息素挥发因子
    Q=1;                          %常系数
    Eta=1./D;                     %启发函数
    Tau=ones(n,n);                %信息素矩阵
    Table=zeros(m,n);             %路径记录表
    iter=1;                       %迭代次数初值
    itermax=200;                  %最大迭代次数
    Route_best=zeros(itermax,n);  %各代最佳路径
    Length_best=zeros(itermax,1); %各代最佳路径的长度
    Length_ave=zeros(itermax,1);  %各代路径的平均长度
    
    %% 5.迭代寻找最佳路径
    while iter<=itermax
        % 5.1随机产生各个蚂蚁的起点城市
        start=zeros(m,1);
        for i=1:m
            temp=randperm(n);
            start(i,:)=temp(1);
        end
        Table(:,1)=start;
        citys_index=1:n;
    
        % 5.2产生解空间(路径表)
        %逐个蚂蚁路径选择
        for i=1:m
            %逐个城市路径选择
            for j=2:n
                tabu=Table(i,:); %已访问城市
                allow_index=~ismember(citys_index,tabu);
                allow=citys_index(allow_index);
                P=allow;
    
                % 5.3计算城市间转移概率
                for k=1:length(allow) 
                    P(k)=Tau(Table(i,j-1),allow(k))^alpha * Eta(Table(i,j-1),allow(k))^beta;
                end
    
                P=P/sum(P);
    
                % 5.4轮盘赌法选择下一个访问城市
                Pc=cumsum(P);
                target_index=find(Pc>=rand);
                target=allow(target_index(1));
                Table(i,j)=target;
            end
        end
    
        % 5.5计算各个蚂蚁的路径距离
        Length=zeros(m,1);
    
        for i=1:m
            for j=1:n-1
                Length(i,1)=Length(i,1)+D(Table(i,j),Table(i,j+1));
            end
            Length(i,1)=Length(i,1)+D(Table(i,end),Table(i,1));
        end
    
        % 5.6计算最短路径及平均距离
        if iter==1
            [min_Length,min_index]=min(Length);
            Length_best(iter)=min_Length;
            Route_best(iter,:)=Table(min_index,:);
            Length_ave(iter)=mean(Length);
        else
            [min_Length,min_index]=min(Length);
            Length_best(iter)=min(Length_best(iter-1),min_Length);
            Length_ave(iter)=mean(Length);
            if Length_best(iter-1)>min_Length
                Route_best(iter,:)=Table(min_index,:);
            else
                Route_best(iter,:)=Route_best(iter-1,:);
            end
        end
    
        % 5.7更新信息素
        Delta_Tau=zeros(n,n);
    
        %逐个蚂蚁计算
        for i=1:m
            %逐个城市计算
            for j=1:n-1
                Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
            end
            Delta_Tau(Table(i,end),Table(i,1))=Delta_Tau(Table(i,end),Table(i,1)) + Q/Length(i);
        end
    
        Tau=(1-rho)*Tau+Delta_Tau;
    
        % 5.8迭代次数加1,清空路径表
        iter=iter+1;
        Table=zeros(m,n);
    
    end
    
    %% 6.结果显示
    best_route=Route_best(end,:);
    best_length=Length_best(end,:);
    disp(['最短距离: ' num2str(best_length)]);
    disp(['最短路径: ' num2str(best_route)]);
    
    %% 7.绘图
    figure(1)
    plot([citys(best_route,1);citys(best_route(1),1)],[citys(best_route,2);citys(best_route(1),2)],'o-')
    for i=1:size(citys,1)
        text(citys(i,1),citys(i,2),[' ' num2str(i)]);
    end
    text(citys(best_route(1),1),citys(best_route(1),2),'     起点');
    text(citys(best_route(end),1),citys(best_route(end),2),'     终点');
    xlabel('城市位置横坐标')
    ylabel('城市位置纵坐标')
    title(['蚁群算法优化路径(最短距离:' num2str(best_length) ')'])
    
    figure(2)
    plot(1:itermax,Length_ave,'r:',1:itermax,Length_best,'b-')
    legend('平均距离','最短距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('各代最短距离与平均距离对比')
    

    四、粒子群算法解决TSP问题

    粒子群算法简介:
    粒子群算法源自于对鸟类捕食问题的研究。基本步骤包括:粒子位置和速度初始化、计算适应度函数值、计算个体极值和群体极值、更新速度和位置、更新适应度函数值、更新个体极值和群体极值。

    粒子相当于遗传算法里的染色体,他对应的就是解空间里面的一个解。速度是一个矢量,代表的是每个粒子下一次搜索的方向和快慢。个体极值:某一个粒子在多次迭代后它所经历的适应度函数值最好的位置,只是一个粒子的最优。群体极值:所有粒子在多次迭代后它们所经历的适应度函数值最好的位置,是整个群体的最优

    更新速度和位置->更新适应度函数值->更新个体极值和群体极值 不停的循环迭代,最后直到满足一定的终止条件。

    流程图如下:在这里插入图片描述

    用来解决TSP问题:
    在TSP问题中,粒子的位置可以使用路径来表示,速度如何表示却是一个难题。基本粒子群算法的速度和位置更新公式不再适用,因此本文重新定义了速度和位置的更新公式。

    基本粒子群算法速度位置更新公式:在这里插入图片描述

    本文重新定义了速度,以及三个运算规则:位置-位置,常数*速度,位置+速度

    1.速度定义为交换序列,位置1+速度=位置2定义为位置1通过速度这个交换序列变成位置2,速度中每一个索引对应的数字意为:位置1中索引为该数字的城市与位置1中索引为速度索引的城市对调,例如:

    位置1=[5 4 3 2 1]
    位置2=[1 2 3 4 5]

    位置2[1]=位置1[5]
    因此位置1[1]与位置1[5]互换位置,速度[1]=5

    交换位置之后:
    位置1=[1 4 3 2 5]
    位置2=[1 2 3 4 5]

    位置2[2]=位置1[4]
    因此位置1[2]与位置1[4]互换位置,速度[2]=4

    交换位置之后:
    位置1=[1 2 3 4 5]
    位置2=[1 2 3 4 5]

    位置2[3]=位置1[3]
    因此位置1[3]与位置1[3]互换位置,速度[3]=3

    由此可以推导,速度=[5 4 3 4 5]

    位置2-位置1即为速度

    2.常数*位置定义为:速度中的每一个值以该常数的概率保留,避免过早陷入局部最优解。

    结果显示:在这里插入图片描述
    在这里插入图片描述
    matlab代码:
    main.m

    %% 1.清空环境变量
    clear all;
    clc;
    
    %% 2.导入数据
    load citys_data.mat;          %数据集的变量名为citys
    
    %% 3.计算城市间相互距离
    n=size(citys,1);
    D=zeros(n,n);
    
    for i=1:n
        for j=i+1:n
            D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));
            D(j,i)=D(i,j);
        end
    end
    
    %% 4.初始化参数
    c1=0.1;                         %个体学习因子
    c2=0.075;                       %社会学习因子
    w=1;                            %惯性因子
    m=500;                          %粒子数量
    pop=zeros(m,n);                 %粒子位置
    v=zeros(m,n);                   %粒子速度
    gen=1;                          %迭代计数器
    genmax=2000;                    %迭代次数
    fitness=zeros(m,1);             %适应度函数值
    Pbest=zeros(m,n);               %个体极值路径
    Pbest_fitness=zeros(m,1);       %个体极值
    Gbest=zeros(genmax,n);          %群体极值路径
    Gbest_fitness=zeros(genmax,1);  %群体极值
    Length_ave=zeros(genmax,1);     %各代路径的平均长度
    ws=1;                           %惯性因子最大值
    we=0.8;                         %惯性因子最小值
    
    %% 5.产生初始粒子
    % 5.1随机产生粒子初始位置和速度
    for i=1:m
        pop(i,:)=randperm(n);
        v(i,:)=randperm(n);
    end
    
    % 5.2计算粒子适应度函数值
    for i=1:m
        for j=1:n-1
            fitness(i)=fitness(i) + D(pop(i,j),pop(i,j+1));
        end
        fitness(i)=fitness(i) + D(pop(i,end),pop(i,1));
    end
    
    % 5.3计算个体极值和群体极值
    Pbest_fitness=fitness;
    Pbest=pop;
    [Gbest_fitness(1),min_index]=min(fitness);
    Gbest(1,:)=pop(min_index,:);
    Length_ave(1)=mean(fitness);
    
    %% 6.迭代寻优
    while gen<genmax
        % 6.1更新迭代次数与惯性因子
        gen=gen+1;
        w = ws - (ws-we)*(gen/genmax)^2;
    
        % 6.2更新速度
        %个体极值修正部分
        change1=position_minus_position(Pbest,pop);
        change1=constant_times_velocity(c1,change1);
        %群体极值修正部分
        change2=position_minus_position(repmat(Gbest(gen-1,:),m,1),pop);
        change2=constant_times_velocity(c2,change2);
        %原速度部分
        v=constant_times_velocity(w,v);
        %修正速度
        for i=1:m
            for j=1:n
                if change1(i,j)~=0
                    v(i,j)=change1(i,j);
                end
                if change2(i,j)~=0
                    v(i,j)=change2(i,j);
                end
            end
        end
    
        % 6.3更新位置
        pop=position_plus_velocity(pop,v);
    
        % 6.4适应度函数值更新
        fitness=zeros(m,1);
        for i=1:m
            for j=1:n-1
                fitness(i)=fitness(i) + D(pop(i,j),pop(i,j+1));
            end
            fitness(i)=fitness(i) + D(pop(i,end),pop(i,1));
        end
    
        % 6.5个体极值与群体极值更新
        for i=1:m
            if fitness(i)<Pbest_fitness(i)
                Pbest_fitness(i)=fitness(i);
                Pbest(i,:)=pop(i,:);
            end
        end
    
        [minvalue,min_index]=min(fitness);
        if minvalue<Gbest_fitness(gen-1)
            Gbest_fitness(gen)=minvalue;
            Gbest(gen,:)=pop(min_index,:);
        else
            Gbest_fitness(gen)=Gbest_fitness(gen-1);
            Gbest(gen,:)=Gbest(gen-1,:);
        end
    
        Length_ave(gen)=mean(fitness);
    
    end
    
    %% 7.结果显示
    [Shortest_Length,index] = min(Gbest_fitness);
    Shortest_Route = Gbest(index,:);
    disp(['最短距离:' num2str(Shortest_Length)]);
    disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
    
    %% 8.绘图
    figure(1)
    plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
         [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
    grid on
    for i = 1:size(citys,1)
        text(citys(i,1),citys(i,2),['   ' num2str(i)]);
    end
    text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'       起点');
    text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'       终点');
    xlabel('城市位置横坐标')
    ylabel('城市位置纵坐标')
    title(['粒子群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
    
    figure(2)
    plot(1:genmax,Gbest_fitness,'b',1:genmax,Length_ave,'r:')
    legend('最短距离','平均距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('各代最短距离与平均距离对比')
    

    position_minus_position.m

    function change=position_minus_position(best,pop)
    %记录将pop变成best的交换序列
    for i=1:size(best,1)
        for j=1:size(best,2)
            change(i,j)=find(pop(i,:)==best(i,j));
            temp=pop(i,j);
            pop(i,j)=pop(i,change(i,j));
            pop(i,change(i,j))=temp;
        end
    end
    end
    

    constant_times_velocity.m

    function change = constant_times_velocity(constant,change)
    % 以一定概率保留交换序列
    for i=1:size(change,1)
        for j=1:size(change,2)
            if rand>constant
                change(i,j)=0;
            end
        end
    end
    end
    

    position_plus_velocity.m

    function pop = position_plus_velocity(pop,v)
    %利用速度记录的交换序列进行位置修正
    for i=1:size(pop,1)
        for j=1:size(pop,2)
            if v(i,j)~=0
                temp=pop(i,j);
                pop(i,j)=pop(i,v(i,j));
                pop(i,v(i,j))=temp;
            end
        end
    end
    end
    

    五、总结

    遗传算法蚁群算法粒子群算法
    优化推进方式选择交叉变异操作信息素浓度的更新速度位置更新
    信息传递种群互相共享信息信息素个体极值和群体极值
    展开全文
  • 基于混合粒子群算法TSP搜索算法 标准粒子群算法通过追随个体极值和群体极值完成极值寻优,虽然操作简单,且能够快速收敛,但是随着迭代次数的不断增加,在种群收敛集中的同时,各粒子也越来越相似,可能在局部最优...

    基于混合粒子群算法的TSP搜索算法

    标准粒子群算法通过追随个体极值和群体极值完成极值寻优,虽然操作简单,且能够快速收敛,但是随着迭代次数的不断增加,在种群收敛集中的同时,各粒子也越来越相似,可能在局部最优解周边无法跳出。混合粒子群算法摒弃了传统粒子群算法中的通过跟踪极值来更新粒子位置的方法,而是引入了遗传算法中的交叉和变异操作,通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。

    问题描述

    旅行商问题( traveling saleman problem,TSP)又译为旅行推销员问题、货郎担问题,简称为TSP,是最基本的路线问题,该问题寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到起点的最小路径成本,最早的旅行商问题的数学模型是由 Dantzig(1959)等人提出。旅行商问题是车辆路线问题(VRP)的特例,已证明旅行商问题是NP难题。
    在这里插入图片描述

    其中,种群初始化模块初始化粒子群种群;适应度值计算模块计算粒子群个体的适应度值;更新粒子模块根据粒子适应度值更新个体最优粒子和群体最优粒子;个体最优交叉把个体和个体最优粒子进行交叉得到新粒子;群体最优交叉把个体和群体最优粒子进行交叉得到新粒子;粒子变异是指粒子自身变异得到新粒子。

    算法实现

    1.个体编码粒子个体编码采用整数编码的方式,每个粒子表示历经的所有城市,比如当历经的城市数为10,个体编码为【94213761085】,表示城市遍历从9开始,经过4,2,1,3,…最终返回城市9,从而完成TSP遍历。
    2.适应度值粒子适应度值表示为遍历路径的长度,计算公式为
    fitness(i)=∑path;
    其中,n为城市数量;path,为城市i,j间路径长度。

    MATLAB程序实现

    根据混合粒子群算法原理,在 MATLAB中编程实现基于混合粒子群的TSP搜索算法。

    适应度函数

    适应度函数计算个体适应度值,个体适应度值为路径总长度,代码如下:

    function indiFit=fitness(x,cityCoor,cityDist)
    %% 该函数用于计算个体适应度值
    %x           input     个体
    %cityCoor    input     城市坐标
    %cityDist    input     城市距离
    %indiFit     output    个体适应度值 
    
    m=size(x,1);
    n=size(cityCoor,1);
    indiFit=zeros(m,1);
    for i=1:m
        for j=1:n-1
            indiFit(i)=indiFit(i)+cityDist(x(i,j),x(i,j+1));
        end
        indiFit(i)=indiFit(i)+cityDist(x(i,1),x(i,n));
    end
    

    主程序

    %% 该文件演示基于TSP-PSO算法
    clc;clear
    
    %% 下载数据
    data=load('eil51.txt');
    cityCoor=[data(:,2) data(:,3)];%城市坐标矩阵
    
    figure
    plot(cityCoor(:,1),cityCoor(:,2),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')
    legend('城市位置')
    ylim([4 78])
    title('城市分布图','fontsize',12)
    xlabel('km','fontsize',12)
    ylabel('km','fontsize',12)
    %ylim([min(cityCoor(:,2))-1 max(cityCoor(:,2))+1])
    
    grid on
    
    %% 计算城市间距离
    n=size(cityCoor,1);            %城市数目
    cityDist=zeros(n,n);           %城市距离矩阵
    for i=1:n
        for j=1:n
            if i~=j
                cityDist(i,j)=((cityCoor(i,1)-cityCoor(j,1))^2+...
                    (cityCoor(i,2)-cityCoor(j,2))^2)^0.5;
            end
            cityDist(j,i)=cityDist(i,j);
        end
    end
    nMax=200;                      %进化次数
    indiNumber=1000;               %个体数目
    individual=zeros(indiNumber,n);
    %^初始化粒子位置
    for i=1:indiNumber
        individual(i,:)=randperm(n);    
    end
    
    %% 计算种群适应度
    indiFit=fitness(individual,cityCoor,cityDist);
    [value,index]=min(indiFit);
    tourPbest=individual;                              %当前个体最优
    tourGbest=individual(index,:) ;                    %当前全局最优
    recordPbest=inf*ones(1,indiNumber);                %个体最优记录
    recordGbest=indiFit(index);                        %群体最优记录
    xnew1=individual;
    
    %% 循环寻找最优路径
    L_best=zeros(1,nMax);
    for N=1:nMax
        N
        %计算适应度值
        indiFit=fitness(individual,cityCoor,cityDist);
        
        %更新当前最优和历史最优
        for i=1:indiNumber
            if indiFit(i)<recordPbest(i)
                recordPbest(i)=indiFit(i);
                tourPbest(i,:)=individual(i,:);
            end
            if indiFit(i)<recordGbest
                recordGbest=indiFit(i);
                tourGbest=individual(i,:);
            end
        end
        
        [value,index]=min(recordPbest);
        recordGbest(N)=recordPbest(index);
        
        %% 交叉操作
        for i=1:indiNumber
           % 与个体最优进行交叉
            c1=unidrnd(n-1); %产生交叉位
            c2=unidrnd(n-1); %产生交叉位
            while c1==c2
                c1=round(rand*(n-2))+1;
                c2=round(rand*(n-2))+1;
            end
            chb1=min(c1,c2);
            chb2=max(c1,c2);
            cros=tourPbest(i,chb1:chb2);
            ncros=size(cros,2);      
            %删除与交叉区域相同元素
            for j=1:ncros
                for k=1:n
                    if xnew1(i,k)==cros(j)
                        xnew1(i,k)=0;
                        for t=1:n-k
                            temp=xnew1(i,k+t-1);
                            xnew1(i,k+t-1)=xnew1(i,k+t);
                            xnew1(i,k+t)=temp;
                        end
                    end
                end
            end
            %插入交叉区域
            xnew1(i,n-ncros+1:n)=cros;
            %新路径长度变短则接受
            dist=0;
            for j=1:n-1
                dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));
            end
            dist=dist+cityDist(xnew1(i,1),xnew1(i,n));
            if indiFit(i)>dist
                individual(i,:)=xnew1(i,:);
            end
            
            % 与全体最优进行交叉
            c1=round(rand*(n-2))+1;  %产生交叉位
            c2=round(rand*(n-2))+1;  %产生交叉位
            while c1==c2
                c1=round(rand*(n-2))+1;
                c2=round(rand*(n-2))+1;
            end
            chb1=min(c1,c2);
            chb2=max(c1,c2);
            cros=tourGbest(chb1:chb2); 
            ncros=size(cros,2);      
            %删除与交叉区域相同元素
            for j=1:ncros
                for k=1:n
                    if xnew1(i,k)==cros(j)
                        xnew1(i,k)=0;
                        for t=1:n-k
                            temp=xnew1(i,k+t-1);
                            xnew1(i,k+t-1)=xnew1(i,k+t);
                            xnew1(i,k+t)=temp;
                        end
                    end
                end
            end
            %插入交叉区域
            xnew1(i,n-ncros+1:n)=cros;
            %新路径长度变短则接受
            dist=0;
            for j=1:n-1
                dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));
            end
            dist=dist+cityDist(xnew1(i,1),xnew1(i,n));
            if indiFit(i)>dist
                individual(i,:)=xnew1(i,:);
            end
            
           %% 变异操作
            c1=round(rand*(n-1))+1;   %产生变异位
            c2=round(rand*(n-1))+1;   %产生变异位
            while c1==c2
                c1=round(rand*(n-2))+1;
                c2=round(rand*(n-2))+1;
            end
            temp=xnew1(i,c1);
            xnew1(i,c1)=xnew1(i,c2);
            xnew1(i,c2)=temp;
            
            %新路径长度变短则接受
            dist=0;
            for j=1:n-1
                dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));
            end
            dist=dist+cityDist(xnew1(i,1),xnew1(i,n));
            if indiFit(i)>dist
                individual(i,:)=xnew1(i,:);
            end
        end
    
        [value,index]=min(indiFit);
        L_best(N)=indiFit(index);
        tourGbest=individual(index,:); 
        
    end
    
    %% 结果作图
    figure
    plot(L_best)
    title('算法训练过程')
    xlabel('迭代次数')
    ylabel('适应度值')
    grid on
    
    
    figure
    hold on
    plot([cityCoor(tourGbest(1),1),cityCoor(tourGbest(n),1)],[cityCoor(tourGbest(1),2),...
        cityCoor(tourGbest(n),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')
    hold on
    for i=2:n
        plot([cityCoor(tourGbest(i-1),1),cityCoor(tourGbest(i),1)],[cityCoor(tourGbest(i-1),2),...
            cityCoor(tourGbest(i),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')
        hold on
    end
    legend('规划路径')
    scatter(cityCoor(:,1),cityCoor(:,2));
    title('规划路径','fontsize',10)
    xlabel('km','fontsize',10)
    ylabel('km','fontsize',10)
    
    grid on
    ylim([4 80])
    

    数据集

    1 37 52
    2 49 49
    3 52 64
    4 20 26
    5 40 30
    6 21 47
    7 17 63
    8 31 62
    9 52 33
    10 51 21
    11 42 41
    12 31 32
    13 5 25
    14 12 42
    15 36 16
    16 52 41
    17 27 23
    18 17 33
    19 13 13
    20 57 58
    21 62 42
    22 42 57
    23 16 57
    24 8 52
    25 7 38
    26 27 68
    27 30 48
    28 43 67
    29 58 48
    30 58 27
    31 37 69
    32 38 46
    33 46 10
    34 61 33
    35 62 63
    36 63 69
    37 32 22
    38 45 35
    39 59 15
    40 5 6
    41 10 17
    42 21 10
    43 5 64
    44 30 15
    45 39 10
    46 32 39
    47 25 32
    48 25 55
    49 48 28
    50 56 37
    51 30 40
    
    

    结果展示

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    仿真结果采用混合粒子群算法规划TSP路径,各城市的初始位置如图所示。
    混合粒子群算法的进化次数为100,种群规模为100,算法进化过程中最优粒子适应度值变化和规划出的最优路径如所示从可以看到,混合粒子群算法能够较快找到连接各个城市的最优路径。

    展开全文
  • 基于混合粒子群算法TSP算法,粒子群算法解决tsp问题,matlab源码
  • 1、粒子群算法简介 粒子群优化算法(Particle Swarm Optimization——PSO), 由James Kennedy(社会心理学博士)和Russell Eberhart(电子工程学博士,于1995年提出的一种基于种群的随机优化算法。 鸟被抽象为...

    1、粒子群算法简介

    粒子群优化算法(Particle Swarm Optimization——PSO), 由James Kennedy(社会心理学博士)和Russell Eberhart(电子工程学博士,于1995年提出的一种基于种群的随机优化算法。

    鸟被抽象为没有质量和体积的微粒(点),并延伸到N维空间,粒子I 在N维空间的位置表示为矢量Xi=(x1,x2,…,xn),飞行速度表示为矢量Vi=(v1,v2,…,vn),每个粒子都有一个由目标函数决定的适应值(fitness value);并且知道自己到目前为止发现的最好位置(pbest);除此之外,每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)。   

    2、粒子群算法核心概念

    如果鸟群觅食的过程中会有信息的交流,则每一个小鸟都会向最优的路径进行觅食的。每一个小鸟其对应的位置矢量和速度矢量,所以在寻优的过程中会对每一个粒子的位置和速度进行更新。

        (1)式

                                     (2)式

    其中(1)式为粒子i在第k+1次迭代时的速度更新公式,(2)式为相对应的位置更新公式。

    rand()是介于0~1之间的实数,ω为惯性因子,c1为个体学习因子,c2为群体认知因子。

    从社会学的角度来看,公式(1)的第一部分称为记忆项,表示上次速度大小和方向的影响;公式第二部分称为自身认知项,是从当前点指向粒子自身最好点的一个矢量,表示粒子的动作来源于自己经验的分;公式的第三部分称为群体认知项,是一个从当前点指向种群最好点的矢量,反映了粒子间的协同合作和知识共享。

    粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。ω值较大,全局寻优能力强,局部寻优能力弱,ω较小,则反之。初始时,ω取为常数,后来实验发现,动态能够获得比固定值更好的寻优结果。动态可以在PSO搜索过程中线性变化,也可根据PSO性能的某个测度函数动态改变。

    在解决TSP问题中,每一个粒子相当于遗传算法中的每一个个体,粒子的位置则相当于该个体访问所有城市的路径,粒子的速度则是一个交换序列的矩阵。该交换序列是把个体最优或群体最优的粒子与粒子群的路径关系。就是说在最优个体的粒子其中一个元素在待优化的粒子中的位置记录下来,并且在接下来的更新粒子位置时,尽量复制最优个体的元素序列。

    3、粒子群算法流程

    Step1:初始化一群微粒(群体规模为M),包括随机位置和速度;

    Step2:评价每个微粒的适应度;

    Step3:对每个微粒,将其适应值与其经过的最好位置pbest作比较,如果较好,则将其作为当前的最好位置pbest;

    Step4:对每个微粒,将其适应值与其经过的最好位置gbest作比较,如果较好,则将其作为当前的最好位置gbest;

    Step5:根据(1)、(2)式调整微粒速度和位置;

    Step6:未达到结束条件则转Step2。

    4、粒子群算法实例及代码

    解决TSP问题的Matlab代码如下:

    function Psorout = PSO_TSP(xy,dmat,Popsize,IterNum,showProg,showResult)
    %利用粒子群优化算法解决TSP问题
    nargs = 6;%代表函数要输入参数的个数
    
    for i = nargin:nargs-1
        switch i
            case 0  %产生城市数据
                xy = [488,814;1393,595;2735,2492;4788,4799;4825,1702;789,2927;4853,1120;4786,3757;2427,1276;4002,2530;710,3496;2109,4455;4579,4797;3962,2737;4798,694;3279,747;179,1288;4246,4204;4670,1272;3394,4072;3789,1218;3716,4647;
                    1962,1750];
    %            xy = 5000*rand(39,2);%产生40个城市坐标40*2矩阵
            case 1  %计算距离矩阵
                N = size(xy,1);
                a = meshgrid(1:N);%生成N*N升序矩阵
                dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);% '为矩阵的转置,reshape把数据生成N*N的矩阵
            case 2  %设置粒子群数目
                Popsize = 500;
            case 3  %设置迭代次数
                IterNum = 2000;
            case 4  %是否展示迭代过程
                showProg = 1;
            case 5  %是否展示结果
                showResult = 1;
            otherwise
        end
    end
    %对输入参数进行检查
    [N,~] = size(xy);%城市个数、维数
    [nr,nc] = size(dmat);%距离矩阵的行数和列数
    if N~=nr || N~=nc
        error('城市坐标或距离矩阵输入有误')
    end
    showProg = logical(showProg(1));%将数值转变为逻辑值
    showResult = logical(showResult(1));
    %画出城市位置分布图
    figure(1);
    plot (xy(:,1),xy(:,2),'k.','MarkerSize',14);
    title('城市坐标位置');
    
    %% PSO参数初始化
    c1 = 0.1;                   %个体学习因子
    c2 = 0.075;                 %社会学习因子
    w = 1;                      %惯性因子
    pop = zeros(Popsize,N);     %粒子位置
    v = zeros(Popsize,N);       %粒子速度
    iter = 1;                   %迭代次数计时
    fitness = zeros(Popsize,1); %适应度函数值
    Pbest = zeros(Popsize,N);   %个体极值路径
    Pbest_fitness = zeros(Popsize,1);   %个体极值
    Gbest = zeros(IterNum,N);            %群体极值路径
    Gbest_fitness = zeros(Popsize,1);     %群体极值
    Length_ave = zeros(IterNum,1);
    ws = 1;                                %惯性因子最大值
    we = 0.5;                               %惯性因子最小值
    
    %% 产生初始位置和速度
    for i = 1:Popsize
        pop(i,:) = randperm(N);
        v(i,:) = randperm(N);
    end
    %计算粒子适应度值
    for i =1:Popsize
        for j =1:N-1
            fitness(i) = fitness(i) + dmat(pop(i,j),pop(i,j+1));
        end
        fitness(i) = fitness(i) + dmat(pop(i,end),pop(i,1));%加上终点回到起点的距离
    end
    %计算个体极值和群体极值
    Pbest_fitness = fitness;
    Pbest = pop;
    [Gbest_fitness(1),min_index] = min(fitness);
    Gbest(1,:) = pop(min_index);
    Length_ave(1) = mean(fitness);
    
    %% 迭代寻优
    while iter <IterNum
        %更新迭代次数与惯性系数
        iter = iter +1;
        w = ws-(ws-we)*(iter/IterNum)^2;%动态惯性系数
        %更新速度
        %个体极值序列交换部分
        change1 = positionChange(Pbest,pop);
        change1 = changeVelocity(c1,change1);%是否进行交换
        %群体极值序列交换部分
        change2 = positionChange(repmat(Gbest(iter-1,:),Popsize,1),pop);%将Gbest复制成m行
        change2 = changeVelocity(c2,change2);
        %原速度部分
        v = OVelocity(w,v);
        %修正速度
        for i = 1:Popsize
            for j =1:N
                if change1(i,j) ~= 0
                    v(i,j) = change1(i,j);
                end
                if change2(i,j) ~= 0
                    v(i,j) = change2(i,j);
                end
            end
        end
        %更新粒子位置
        pop = updatePosition(pop,v);%更新粒子的位置,也就是更新路径序列
        %适应度值更新
        fitness = zeros(Popsize,1);
        for i = 1:Popsize
            for j = 1:N-1
                fitness(i) = fitness(i) + dmat(pop(i,j),pop(i,j+1));
            end
            fitness(i) = fitness(i) + dmat(pop(i,end),pop(i,1));
        end
        
        %个体极值与群体极值的更新
        for i =1:Popsize
            if fitness(i) < Pbest_fitness(i)
                Pbest_fitness(i) = fitness(i);
                Pbest(i,:) = pop(i,:);
            end
        end
        [minvalue,min_index] = min(fitness);
        if minvalue <Gbest_fitness(iter-1)
            Gbest_fitness(iter) = minvalue;
            Gbest(iter,:) = pop(min_index,:);
            if showProg
                figure(2);
                for i = 1:N-1 %画出中间段
                    plot([xy(Gbest(iter,i),1),xy(Gbest(iter,i+1),1)],[xy(Gbest(iter,i),2),xy(Gbest(iter,i+1),2)],'bo-','LineWidth',2);
                    hold on;
                end
                plot([xy(Gbest(iter,end),1),xy(Gbest(iter,1),1)],[xy(Gbest(iter,end),2),xy(Gbest(iter,1),2)],'bo-','LineWidth',2);
                title(sprintf('最优路线距离 = %1.2f,迭代次数 = %d次',minvalue,iter));
                hold off
            end 
        else
            Gbest_fitness(iter) = Gbest_fitness(iter-1);
            Gbest(iter,:) = Gbest(iter-1,:);
        end
        Length_ave(iter) = mean(fitness);
    end
    %% 结果显示
    [Shortest_Length,index] = min(Gbest_fitness);
    BestRoute = Gbest(index,:);
    if showResult
       figure(3);
       plot([xy(BestRoute,1);xy(BestRoute(1),1)],[xy(BestRoute,2);xy(BestRoute(1),2)],'o-')
       grid on
       xlabel('城市位置横坐标');
       ylabel('城市位置纵坐标');
       title(sprintf('粒子群算法优化路径最短距离:%1.2f',Shortest_Length));
       figure(4);
       plot(1:IterNum,Gbest_fitness,'b',1:IterNum,Length_ave,'r:')
       legend('最短距离','平均距离');
       xlabel('迭代次数');
       ylabel('距离')
       title('各代最短距离与平均距离对比');
    end
    if nargout
        Psorout{1} = BestRoute;
        Psorout{2} = Shortest_Length; 
    end     
    end
    
    function change = positionChange(best,pop)
    %记录将pop变成best的交换序列
    for i = 1:size(best,1)
        for j =1:size(best,2)
            change(i,j) = find(pop(i,:)==best(i,j));%在粒子i中找到best(i,j)位置索引
            temp = pop(i,j);%将序列交换
            pop(i,j) = pop(i,change(i,j));
            pop(i,change(i,j)) = temp;
        end
    end
    end
    function change = changeVelocity(c,change)
    %以一定的概率保留序列
    for i =1:size(change,1)
        for j = 1:size(change,2)
            if rand > c
                change(i,j) = 0;
            end
        end
    end
    end
    function v = OVelocity(c,v)
    %以一定的概率保留上一次迭代的交换序列
    for i =1:size(v,1)
        for j = 1:size(v,2)
            if rand >c
                v(i,j) = 0;
            end
        end
    end
    end
    function pop = updatePosition(pop,v)
    %利用速度记录的交换序列进行位置的更新
    for i = 1:size(pop,1)
        for j =1:size(pop,2)
            if v(i,j) ~= 0
                temp = pop(i,j);
                pop(i,j) = pop(i,v(i,j));
                pop(i,v(i,j)) = temp;
            end
        end
    end
    end

    结果如下:

    若有小伙伴对机器人任务分配算法较为兴趣的,可以在下面评论交流一波,纯属互相学习!

    展开全文
  • MATLAB 粒子群算法解决经典31城市TSP问题
  • 用两种方法通过python编程对TSP问题的求解 , 一是通过gurobi求解器求解 , 二是通过智能算法PSO(粒子群算法)进行求解 . 并画出最优路径 . 资源中包括TSP问题的数学模型 , 两种求解方法的python代码 , 以及求解结果图...
  • 启发因子,信息素的重要程度期望因子,城市间距离的重要程度信息素增强系数蚂蚁数量表示每条边的能见度参数可修改
  • 粒子群优化(PSO)是一种群智能算法,其灵感来自于鸟类的群集或鱼群学习,用于解决许多科学和工程领域中出现的非线性、非凸性或组合优化问题。 1.1.1 算法思想 许多鸟类都是群居性的,并由各种原因形成不同的鸟群。...

    一、获取代码方式

    获取代码方式1:
    完整代码已上传我的资源:【TSP】基于matlab粒子群算法求解旅行商问题【含Matlab源码 445期】

    获取代码方式2:
    通过紫极神光博客主页开通CSDN会员,凭支付凭证,私信博主,可获得此代码。

    获取代码方式3:
    通过订阅紫极神光博客付费专栏,凭支付凭证,私信博主,可获得此代码。

    备注:开通CSDN会员,仅只能免费获得1份代码(有效期为开通日起,三天内有效);
    订阅紫极神光博客付费专栏,可免费获得2份代码(有效期为订阅日起,三天内有效);

    二、TSP简介

    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
    TSP的数学模型
    在这里插入图片描述

    三、粒子群算法简介

    1 引言
    自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣所在。生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型,在他的仿真中,每一个个体都遵循:避免与邻域个体相撞:匹配邻域个体的速度;飞向鸟群中心,且整个群体飞向目标。仿真中仅利用上面三条简单的规则,就可以非常接近地模拟出鸟群飞行的现象。1990年, 生物学家Frank Heppner也提出了鸟类模型, 它的不同之处在于:鸟类被吸引飞到栖息地。在仿真中,一开始每一只鸟都没有特定的飞行目标,只是使用简单的规则确定自己的飞行方向和飞行速度,当有一只鸟飞到栖息地时,它周围的鸟也会跟着飞向栖息地,最终整个鸟群都会落在栖息地。
    1995年, 美国社会心理学家James Kennedy和电气工程师RussellEberhart共同提出了粒子群算法(ParticleS warm Optimization, PSO) , 该算法的提出是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正,以使粒子飞向解空间并在最优解处降落。粒子群算法一经提出,由于其算法简单,容易实现,立刻引起了进化计算领域学者们的广泛关注, 形成一个研究热点。2001年出版的J.Kennedy与R.Eberhart合著的《群体智能》将群体智能的影响进一步扩大[] , 随后关于粒子群优化算法的研究报告和研究成果大量涌现,继而掀起了国内外研究热潮[2-7]。
    粒子群优化算法来源于鸟类群体活动的规律性,进而利用群体智能建立一个简化的模型。它模拟鸟类的觅食行为,将求解问题的搜索空间比作鸟类的飞行空间,将每只鸟抽象成一个没有质量和体积的粒
    子,用它来表征问题的一个可能解,将寻找问题最优解的过程看成鸟类寻找食物的过程,进而求解复杂的优化问题。粒子群优化算法与其他进化算法一样,也是基于“种群”和“进化”的概念,通过个体间
    的协作与竞争,实现复杂空间最优解的搜索。同时,它又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作,而是将群体中的个体看作在l维搜索空间中没有质量和体积的粒子,每个粒子以一定的速度在解空间运动, 并向自身历史最佳位置P best和邻域历史最佳位置g best聚集, 实现对候选解的进化。粒子群算法具有很好的生物社会背景而易于理解,由于参数少而容易实现,对非线性、多峰问题均具有较强的全局搜索能力,在科学研究与工程实践中得到了广泛关注。目前,该算法已广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域。

    2 粒子群算法理论
    2.1粒子群算法描述
    鸟类在捕食过程中,鸟群成员可以通过个体之间的信息交流与共享获得其他成员的发现与飞行经历。在食物源零星分布并且不可预测的条件下,这种协作机制所带来的优势是决定性的,远远大于对食物
    的竞争所引起的劣势。粒子群算法受鸟类捕食行为的启发并对这种行为进行模仿,将优化问题的搜索空间类比于鸟类的飞行空间,将每只鸟抽象为一个粒子,粒子无质量、无体积,用以表征问题的一个可行解,优化问题所要搜索到的最优解则等同于鸟类寻找的食物源。粒子群算法为每个粒子制定了与鸟类运动类似的简单行为规则,使整个粒子群的运动表现出与鸟类捕食相似的特性,从而可以求解复杂的优化问题。
    粒子群算法的信息共享机制可以解释为一种共生合作的行为,即每个粒子都在不停地进行搜索,并且其搜索行为在不同程度上受到群体中其他个体的影响[8],同时这些粒子还具备对所经历最佳位置的记
    忆能力,即其搜索行为在受其他个体影响的同时还受到自身经验的引导。基于独特的搜索机制,粒子群算法首先生成初始种群,即在可行解空间和速度空间随机初始化粒子的速度与位置,其中粒子的位置用于表征问题的可行解,然后通过种群间粒子个体的合作与竞争来求解优化问题。
    2.2粒子群算法建模
    粒子群优化算法源自对鸟群捕食行为的研究:一群鸟在区域中随机搜索食物,所有鸟知道自己当前位置离食物多远,那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。粒子群算法
    利用这种模型得到启示并应用于解决优化问题。在粒子群算法中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为粒子。所有的粒子都有一个由被优化的函数决定的适应度值,每个粒子还有一个速度决定它们飞翔的方向和距离。然后,粒子们就追随当前的最优粒子在解空间中搜索[9]。

    粒子群算法首先在给定的解空间中随机初始化粒子群,待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度,然后通过迭代寻优。在每一次迭代中,每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞行速度:一个极值就是单个粒子本身在迭代过程中找到的最优解粒子,这个粒子叫作个体极值:另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子,这个粒子是全局极值。上述的方法叫作全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子,那么在所有邻居粒子中的极值就是局部极值,该方法称为局部粒子群算法。

    2.3粒子群算法的特点
    粒子群算法本质是一种随机搜索算法,它是一种新兴的智能优化技术。该算法能以较大概率收敛于全局最优解。实践证明,它适合在动态、多目标优化环境中寻优,与传统优化算法相比,具有较快的计
    算速度和更好的全局搜索能力。
    (1)粒子群算法是基于群智能理论的优化算法,通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与其他算法相比,粒子群算法是一种高效的并行搜索算法。
    (2)粒子群算法与遗传算法都是随机初始化种群,使用适应值来评价个体的优劣程度和进行一定的随机搜索。但粒子群算法根据自己的速度来决定搜索,没有遗传算法的交叉与变异。与进化算法相比,粒子群算法保留了基于种群的全局搜索策略,但是其采用的速度-位移模型操作简单,避免了复杂的遗传操作。
    (3)由于每个粒子在算法结束时仍保持其个体极值,即粒子群算法除了可以找到问题的最优解外,还会得到若干较好的次优解,因此将粒子群算法用于调度和决策问题可以给出多种有意义的方案。
    (4)粒子群算法特有的记忆使其可以动态地跟踪当前搜索情况并调整其搜索策略。另外,粒子群算法对种群的大小不敏感,即使种群数目下降时,性能下降也不是很大。

    3 粒子群算法种类
    3.1基本粒子群算法
    在这里插入图片描述
    3.2标准粒子群算法
    引入研究粒子群算法经常用到的两个概念:一是“探索”,指粒子在一定程度上离开原先的搜索轨迹,向新的方向进行搜索,体现了一种向未知区域开拓的能力,类似于全局搜索;二是“开发”,指粒子在一定程度上继续在原先的搜索轨迹上进行更细一步的搜索,主要指对探索过程中所搜索到的区域进行更进一步的搜索。探索是偏离原来的寻优轨迹去寻找一个更好的解,探索能力是一个算法的全局搜索能力。开发是利用一个好的解,继续原来的寻优轨迹去搜索更好的解,它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例, 对一个问题的求解过程很重要。1998年, Shi Yuhui等人提出了带有惯性权重的改进粒子群算法[10],由于该算法能够保证较好的收敛效果,所以被默认为标准粒子群算法。其进化过程为:
    在这里插入图片描述
    在式(6.7)中,第一部分表示粒子先前的速度,用于保证算法的全局收敛性能;第二部分、第三部分则使算法具有局部收敛能力。可以看出,式(6.7)中惯性权重w表示在多大程度上保留原来的速度:W
    较大,则全局收敛能力较强,局部收敛能力较弱;w较小,则局部收敛能力较强,全局收敛能力较弱。
    当w=1时,式(6.7)与式(6.5)完全一样,表明带惯性权重的粒子群算法是基本粒子群算法的扩展。实验结果表明:w在0.8~1.2之间时,粒子群算法有更快的收敛速度;而当w>1.2时,算法则容易陷入局部极值。
    另外,在搜索过程中可以对w进行动态调整:在算法开始时,可给w赋予较大正值,随着搜索的进行,可以线性地使w逐渐减小,这样可以保证在算法开始时,各粒子能够以较大的速度步长在全局范围内探
    测到较好的区域;而在搜索后期,较小的w值则保证粒子能够在极值点周围做精细的搜索,从而使算法有较大的概率向全局最优解位置收敛。对w进行调整,可以权衡全局搜索和局部搜索能力。目前,采用较多的动态惯性权重值是Shi提出的线性递减权值策略, 其表达式如下:
    在这里插入图片描述
    3.3压缩因子粒子群算法
    Clerc等人提出利用约束因子来控制系统行为的最终收敛[11] , 该方法可以有效搜索不同的区域,并且能得到高质量的解。压缩因子法的速度更新公式为:
    在这里插入图片描述
    实验结果表明:与使用惯性权重的粒子群优化算法相比,使用具
    有约束因子的粒子群算法具有更快的收敛速度。
    3.4离散粒子群算法
    基本的粒子群算法是在连续域中搜索函数极值的有力工具。继基本粒子群算法之后, Kennedy和Eberhart又提出了一种离散二进制版的粒子群算法[12]。在此离散粒子群方法中,将离散问题空间映射到连续粒子运动空间,并适当修改粒子群算法来求解,在计算上仍保留经典粒子群算法速度-位置更新运算规则。粒子在状态空间的取值和变化只限于0和1两个值, 而速度的每一维vi y代表位置每一位xi取值为1的可能性。因此, 在连续粒子群中的vij更新公式依然保持不变, 但是P best和:best只在[0, 1] 内取值。其位置更新等式表示如下:
    在这里插入图片描述
    4 粒子群算法流程
    粒子群算法基于“种群”和“进化”的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索[13],其流程如下:
    (1)初始化粒子群,包括群体规模N,每个粒子的位置x;和速度Vio
    (2) 计算每个粒子的适应度值fit[i] 。
    (3) 对每个粒子, 用它的适应度值fit[门和个体极值P best(i)比较。如果fit[i] <P best(i) , 则用fit[i] 替换掉P best(i) 。
    (4) 对每个粒子, 用它的适应度值fit[i] 和全局极值g best比较。如果fit[i] < 8 best, 则用fit[i] 替换g best。
    (5)迭代更新粒子的速度v;和位置xj。
    (6)进行边界条件处理。
    (7)判断算法终止条件是否满足:若是,则结束算法并输出优化结果;否则返回步骤(2)。
    粒子群算法的运算流程如图6.1所示。
    在这里插入图片描述
    5 关键参数说明
    在粒子群优化算法中,控制参数的选择能够影响算法的性能和效率;如何选择合适的控制参数使算法性能最佳,是一个复杂的优化问题。在实际的优化问题中,通常根据使用者的经验来选取控制参数。
    粒子群算法的控制参数主要包括:粒子种群规模N,惯性权重w,加速系数c和c, 最大速度Via x, 停止准则, 邻域结构的设定, 边界条件处理策略等[14],
    粒子种群规模N
    粒子种群大小的选择视具体问题而定,但是一般设置粒子数为20~50。对于大部分的问题10个粒子,已经可以取得很好的结果:不过对于比较难的问题或者特定类型的问题,粒子的数量可以取到100或
    200。另外,粒子数目越大,算法搜索的空间范围就越大,也就更容易发现全局最优解;当然,算法运行的时间也越长。
    惯性权重w
    惯性权重w是标准粒子群算法中非常重要的控制参数,可以用来控制算法的开发和探索能力。惯性权重的大小表示了对粒子当前速度继承的多少。当惯性权重值较大时,全局寻优能力较强,局部寻优能力
    较弱:当惯性权重值较小时,全局寻优能力较弱,局部寻优能力较强。惯性权重的选择通常有固定权重和时变权重。固定权重就是选择常数作为惯性权重值,在进化过程中其值保持不变,一般取值为
    [0.8,1.2]:时变权重则是设定某一变化区间,在进化过程中按照某种方式逐步减小惯性权重。时变权重的选择包括变化范围和递减率。固定的惯性权重可以使粒子保持相同的探索和开发能力,而时变权重可以使粒子在进化的不同阶段拥有不同的探索和开发能力。
    加速常数c1和c2
    加速常数c和c 2分别调节向P best和g best方向飞行的最大步长, 它们分别决定粒子个体经验和群体经验对粒子运行轨迹的影响,反映粒子群之间的信息交流。如果cr=c2=0,则粒子将以当前的飞行速度飞到边界。此时,粒子仅能搜索有限的区域,所以难以找到最优解。如果q=0,则为“社会”模型,粒子缺乏认知能力,而只有群体经验,它的收敛速度较快,但容易陷入局部最优;如果oy=0,则为“认知”模
    型,没有社会的共享信息,个体之间没有信息的交互,所以找到最优解的概率较小,一个规模为D的群体等价于运行了N个各行其是的粒子。因此一般设置c1=C2,通常可以取c1=cg=1.5。这样,个体经验和群体经验就有了同样重要的影响力,使得最后的最优解更精确。
    粒子的最大速度vmax
    粒子的速度在空间中的每一维上都有一个最大速度限制值vd max,用来对粒子的速度进行钳制, 使速度控制在范围[-Vimax, +va max] 内,这决定问题空间搜索的力度, 该值一般由用户自己设定。Vmax是一个非常重要的参数,如果该值太大,则粒子们也许会飞过优秀区域:而如果该值太小,则粒子们可能无法对局部最优区域以外的区域进行充分的探测。它们可能会陷入局部最优,而无法移动足够远的距离而跳出局部最优, 达到空间中更佳的位置。研究者指出, 设定Vmax和调整惯性权重的作用是等效的, 所以!max一般用于对种群的初始化进行设定, 即将vmax设定为每维变量的变化范围, 而不再对最大速度进行细致的选择和调节。
    停止准则
    最大迭代次数、计算精度或最优解的最大停滞步数▲t(或可以接受的满意解)通常认为是停止准则,即算法的终止条件。根据具体的优化问题,停止准则的设定需同时兼顾算法的求解时间、优化质量和
    搜索效率等多方面性能。
    邻域结构的设定
    全局版本的粒子群算法将整个群体作为粒子的邻域,具有收敛速度快的优点,但有时算法会陷入局部最优。局部版本的粒子群算法将位置相近的个体作为粒子的邻域,收敛速度较慢,不易陷入局部最优
    值。实际应用中,可先采用全局粒子群算法寻找最优解的方向,即得到大致的结果,然后采用局部粒子群算法在最优点附近进行精细搜索。
    边界条件处理
    当某一维或若干维的位置或速度超过设定值时,采用边界条件处理策略可将粒子的位置限制在可行搜索空间内,这样能避免种群的膨胀与发散,也能避免粒子大范围地盲目搜索,从而提高了搜索效率。
    具体的方法有很多种, 比如通过设置最大位置限制Xmax和最大速度限制Vmax, 当超过最大位置或最大速度时, 在范围内随机产生一个数值代替,或者将其设置为最大值,即边界吸收。

    四、部分源代码

    %粒子群算法求解旅行商问题
    
    close all;
    clear all;
    clc;
    tic;
    PopSize=500;%种群大小
    CityNum = 14;%城市数
    
    OldBestFitness=0;%旧的最优适应度值
    
    Iteration=0;%迭代次数
    MaxIteration =2000;%最大迭代次数
    IsStop=0;%程序停止标志
    Num=0;%取得相同适应度值的迭代次数
    
    c1=0.5;%认知系数
    c2=0.7;%社会学习系数
    w=0.96-Iteration/MaxIteration;%惯性系数,随迭代次数增加而递减
    
    %节点坐标
    node=[16.47 96.10; 16.47 94.44; 20.09 92.54; 22.39 93.37; 25.23 97.24;...
         22.00 96.05; 20.47 97.02; 17.20 96.29; 16.30 97.38; 14.05 98.12;...
         16.53 97.38; 21.52 95.59; 19.41 97.13; 20.09 94.55];
    
    %初始化各粒子,即产生路径种群
    Group=ones(CityNum,PopSize);  
    for i=1:PopSize
        Group(:,i)=randperm(CityNum)';
    end
    Group=Arrange(Group);
    
    %初始化粒子速度(即交换序)
    Velocity =zeros(CityNum,PopSize);   
    for i=1:PopSize
        Velocity(:,i)=round(rand(1,CityNum)'*CityNum); %round取整
    end
    
    %计算每个城市之间的距离
    CityBetweenDistance=zeros(CityNum,CityNum);  
    for i=1:CityNum
        for j=1:CityNum
            CityBetweenDistance(i,j)=sqrt((node(i,1)-node(j,1))^2+...
                (node(i,2)-node(j,2))^2);
        end
    end
    
    %计算每条路径的距离
    for i=1:PopSize   
            EachPathDis(i) = PathDistance(Group(:,i)',CityBetweenDistance);
    end
    
    IndivdualBest=Group;%记录各粒子的个体极值点位置,即个体找到的最短路径
    IndivdualBestFitness=EachPathDis;%记录最佳适应度值,即个体找到的最短路径的长度
    [GlobalBestFitness,index]=min(EachPathDis);%找出全局最优值和相应序号
     OldBestFitness=GlobalBestFitness;
    %初始随机解
    figure;
    subplot(2,2,1);
    PathPlot(node,CityNum,index,IndivdualBest);
    title('随机解');
    
    %寻优
    while(IsStop == 0) & (Iteration < MaxIteration)
        %迭代次数递增
        Iteration = Iteration +1;  
       
        %更新全局极值点位置,这里指路径
        for i=1:PopSize   
            GlobalBest(:,i) = Group(:,index);
        end
       
        %求pij-xij ,pgj-xij交换序,并以概率c1,c2的保留交换序
        pij_xij=GenerateChangeNums(Group,IndivdualBest);  
        pij_xij=HoldByOdds(pij_xij,c1);
        pgj_xij=GenerateChangeNums(Group,GlobalBest);
        pgj_xij=HoldByOdds(pgj_xij,c2);
       
        %以概率w保留上一代交换序
        Velocity=HoldByOdds(Velocity,w); 
    
        Group = PathExchange(Group,Velocity); %根据交换序进行路径交换
        Group = PathExchange(Group,pij_xij);
        Group = PathExchange(Group,pgj_xij);
        for i = 1:PopSize    % 更新各路径总距离
              EachPathDis(i) = PathDistance(Group(:,i)',CityBetweenDistance);
        end
    
        IsChange = EachPathDis<IndivdualBestFitness;%更新后的距离优于更新前的,记录序号
        IndivdualBest(:, find(IsChange)) = Group(:, find(IsChange));%更新个体最佳路径
        IndivdualBestFitness = IndivdualBestFitness.*...
            ( ~IsChange) + EachPathDis.*IsChange;%更新个体最佳路径距离
        [GlobalBestFitness, index] = min(EachPathDis);%更新全局最佳路径,记录相应的序号
    
    %     if GlobalBestFitness==OldBestFitness %比较更新前和更新后的适应度值;
    %         Num=Num+1; %相等时记录加一;
    %     else
    %         OldBestFitness=GlobalBestFitness;%不相等时更新适应度值,并记录清零;
    %         Num=0;
    %     end   
        if GlobalBestFitness>=OldBestFitness %比较更新前和更新后的适应度值;
            Num=Num+1; %相等时记录加一;      
        else
            OldBestFitness=GlobalBestFitness;%不相等时更新适应度值,并记录清零;
            Num=0;
        end   
    %初始化粒子速度(即交换序)
    Velocity =zeros(PopSize,CityNum);
    for i=1:PopSize
        Velocity(i,:)=round(rand(1,CityNum)'*CityNum); %round取整
    end
    
    IndivdualBest=var;%记录各粒子的个体极值点位置
    funb=fun;%记录最佳适应度值
    index=find(min(fun)==fun);
    fungbest=fun(index);
    vargbest=var(index);
    
    %% 主循环
    for Iteration=1:MaxIteration
        %     if ~mod(Iteration,MaxIteration)
        %         fprintf('current iter:%d\n',Iteration)
        %         disp([' Number of Repository Particles = ' num2str(size(varrep,1))]);
        %     end
        
        
        w=0.96-Iteration/MaxIteration;%惯性系数,随迭代次数增加而递减
        %更新全局极值点位置,这里指路径
        %     for i=1:PopSize
        %         select1=randi(numrep);
        %         Pg(i,:)=varrep(select1,:);%Randomly select a global best
        %     end
        for i=1:PopSize
            Pg(i,:)=vargbest;
        end
        %求pij-xij ,pgj-xij交换序,并以概率c1,c2的保留交换序
        pij_xij=GenerateChangeNums(var,IndivdualBest);
        pij_xij=HoldByOdds(pij_xij,c1);
        pgj_xij=GenerateChangeNums(var,Pg);
        pgj_xij=HoldByOdds(pgj_xij,c2);
        
        %产生变异(交换俩个位置)
        pmj_xij=zeros(PopSize,CityNum);
        for i=1:PopSize
            if rand>0.5
                m1=randi(CityNum);
                m2=randi(CityNum);
                while m1==c2
                    m1=randi(CityNum);
                    m2=randi(CityNum);
                end
                pmj_xij(i,m1)=m2;
            end
        end
        
        %以概率w保留上一代交换序
        Velocity=HoldByOdds(Velocity,w);
        
        %根据交换序进行路径交换
        var = PathExchange(var,Velocity);
        var = PathExchange(var,pij_xij);
        var = PathExchange(var,pgj_xij);
        var = PathExchange(var,pmj_xij);
        
        % 更新个体历史最优
        for i=1:PopSize
            cost(i,:)=costfunction(var(i,:),location1,location2);
            fun(i)=lanmt1*cost(i,1)+lanmt2*cost(i,2);
            if fun(i)<funb(i)
                IndivdualBest(i,:)=var(i,:);%记录各粒子的个体极值点位置
                funb(i)=fun(i);%记录最佳适应度值
            end
        end
    

    五、运行结果

    在这里插入图片描述

    六、matlab版本及参考文献

    1 matlab版本
    2014a

    2 参考文献
    [1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例(第2版)[M].电子工业出版社,2016.
    [2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社,2017.

    展开全文
  • 基于混合粒子群算法TSP问题求解Matlab版实现
  • 粒子群算法matlab代码及使用。自编function,可以直接嵌入使用
  • 中文说明:含逃逸变邻域的改进粒子群算法。内含三个城市群算例,可完美运行,含本人程序详细注释。含逃逸变邻域的改进粒子群算法。内含三个城市群算例,可完美运行,含本人程序详细注释。含逃逸变邻域的改进粒子群...
  • 实验7 粒子群优化算法求解tsp问题

    千次阅读 多人点赞 2019-01-31 22:45:53
    传送门(所有的实验都使用python实现) ...实验6 蚁群算法求解tsp问题 实验7 粒子群优化算法求解tsp问题 实验8 分布估计算法求解背包问题 实验9 模拟退火算法求解背包问题 实验10 禁忌搜索算法求解tsp问题   ...
  • 基于混合粒子群算法TSP搜索算法

    千次阅读 2020-12-29 15:30:52
    混合粒子群算法摒弃了传统粒子群算法中的通过跟踪极值来更新粒子位置的方法,而是引进了遗传算法中的交叉和变异操作,通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜寻全局最优解。 二、案例背景 1...
  • 1 粒子群算法的概念\ 粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的协作和信息...
  • 粒子群算法解决01背包问题,C语言编写,可直接运行并得到最优解
  • 本文档整理了粒子群算法的基本原理,也给出了粒子群算法MATLAB代码,结合原理看代码,很容易看懂,可以提供给初学者使用,简单易懂,赞。
  • 混合粒子群算法求解TSP问题matlab代码.zip
  • 数学建模源码集锦-基于混合粒子群算法TSP搜索算法应用实例

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 323
精华内容 129
关键字:

matlab粒子群算法解决tsp

matlab 订阅