1 简介

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

2 部分代码

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);
%%在二维图上画出所有坐标点
figure
plot(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 on
xlim([0,MAXGEN])
title('优化过程')
xlabel('代数')
ylabel('最优值')
ObjV=PathLength(D,Chrom);                           %计算路线长度title('优化过程')xlable('代数')ylable('最优值')
preObjV=min(ObjV);
while gen<MAXGEN
   %%计算适应度
   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<=R
               K=K+1;
               subject(K,:)=Chrom(j,:);
           end
       end
       for j=i+1:NIND
           dij=ristanse(Chrom(i,:),Chrom(j,:));
            if dij<=R
               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('-------------------------------------------------------------------')

3 仿真结果

4 参考文献

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