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 仿真結果