【路径规划】基于萤火虫算法求解旅行商问题matlab源码

基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下.

clear;clc;close all;X=[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,92.55   13.04 23.12;   36.39 13.15;   41.77 22.44;   37.12 13.99;   34.88 15.35;   33.26 15.56;   32.38 12.29;  41.96 10.44;   43.12  7.90;   43.86  5.70;   30.07 9.70;    25.62 17.56;   27.88 14.91;   23.81 16.76;  13.32  6.95;   37.15 16.78;   39.18 21.79;   40.61 23.70;   37.80 22.12;   36.76 25.78;   40.29 28.38;     42.63 29.31;   34.29 19.08;   35.07 23.76;   33.94 26.43;   34.39 32.01;   29.35 32.40;   31.40 35.50;  25.45 23.57;   27.78 28.26;   23.70 29.75];R=45;MAXGEN=100;NIND=100;D=Distanse(X);N=size(D,1);%%初始化种群Chrom=InitPop(NIND,N);%%在二维图上画出所有坐标点figureplot(X(:,1),X(:,2),'o');%%画出随机解的路线图DrawPath(Chrom(1,:),X);pause(0.0001)%%输出随机解的路线和总距离disp('初始种群中的一个随机解：')OutputPath(Chrom(1,:));Rlength=PathLength(D,Chrom(1,:));disp(['总距离：',num2str(Rlength)]);disp('-------------------------------------------------------------------------------------------------')%%优化gen=0;figure;hold on;box onxlim([0,MAXGEN])title('优化过程')xlabel('代数')ylabel('最优值')ObjV=PathLength(D,Chrom);                           %计算路线长度title('优化过程')xlable('代数')ylable('最优值')preObjV=min(ObjV);while gen   %%计算适应度   ObjV=PathLength(D,Chrom);                        %计算路线长度   %fprintf('%d   %1.10f\n',gen,min(ObjV))   line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001)   preObjV=min(ObjV);   FitnV=Fitness(ObjV);   for i=1:NIND       K=0;       subject=zeros(NIND,N);       for j=1:i-1           dij=ristanse(Chrom(i,:),Chrom(j,:));           if dij               K=K+1;               subject(K,:)=Chrom(j,:);           end       end       for j=i+1:NIND           dij=ristanse(Chrom(i,:),Chrom(j,:));            if dij               K=K+1;               subject(K,:)=Chrom(j,:);            end       end       if K==0       subject1=zeros(1,N);       else subject1=zeros(K,N);       end       for v=1:K           subject1(v,:)=subject(v,:);       end       if K~=0       ObjV1=PathLength(D,subject1);       FitnVS=Fitness(ObjV1);      [minObjV1,minInd]=min(ObjV1);       minChrom=subject1(minInd,:);       ObjVi=PathLength(D,Chrom(i,:));        if ObjVi>minObjV1      [Chrom(i,:),minChrom]=placechange(Chrom(i,:),minChrom);       end       end   end    gen=gen+1;end%%画出最优解的路线图ObjV=PathLength(D,Chrom);[minObjV,minInd]=min(ObjV);DrawPath(Chrom(minInd(1),:),X)%%输出最优解的路线和总距离disp('最优解')p=OutputPath(Chrom(minInd(1),:));disp(['总距离:',num2str(ObjV(minInd(1)))]);disp('-------------------------------------------------------------------')

[1]周永权, 黄正新, & 刘洪霞. (2012). 求解tsp问题的离散型萤火虫群优化算法. 电子学报, 40(6), 1164-1164.