TSP_中国省会城市遗传算法.rar

中国省会的TSP问题. 亲手写的，注释详细，带图形演示，感兴趣的朋友来下载吧.

clcclear

hold on
%起点
global star_point;
star_point=5;
sj0=importdata（‘provincial_ capital_coordinate.txt‘）;       %加载数据（每个点的经纬度）
%整理好数据
x=sj0.data（:1）;   %经度
y=sj0.data（:2）;   %纬度

landcolor = [111];
%载入坐标轴范围（维度范围 经度范围）
ax = worldmap（[15 53][70 135]）;
%载入陆地地区shapefile文件 usegeocoord 将数据视为经纬度
land = shaperead（‘gadm36_CHN_1.shp‘ ‘UseGeoCoords‘ true）;
%显示陆地 以landcolor做填充颜色
h=geoshow（ax land ‘FaceColor‘ landcolor）;
%显示地点
point_data.Geometry=‘Point‘;
point_data.Lon=x;
point_data.Lat=y;
geoshow（point_data‘Marker‘ ‘*‘）;
textm（yxchar（sj0.textdata（2:362）））;   %第一个参数为纬度，第二个为经度


%选取起点 %起点要放在头和尾各一次
x（[1 star_point]:）=x（[star_point 1]:）;
y（[1 star_point]:）=y（[star_point 1]:）;
x=[x;x（1）];
y=[y;y（1）];

sj=[xy]; 
sj=sj*pi/180;  %单位化成弧度
point_number=size（sj1）;
d=zeros（（point_number））;  %距离矩阵d的初始值。 

%已知经纬度求两点之间大圆航线距离，配置好邻接矩阵d
for i=1:（point_number-1）
  for j=i+1:（point_number）
  d（ij）=6370*acos（cos（sj（i1）-sj（j1））*cos（sj（i2））*cos（sj（j2））+sin（sj（i2））*sin（sj（j2）））;
  end
end
d=d+d‘; w=50; g=（point_number-2）; %w为种群的个数，g为进化的代数
rand（‘state‘sum（clock））; %初始化随机数发生器
for k=1:w  %通过改良圈算法选取初始种群
    c=randperm（（point_number-2））; %产生1，...，（point_number-2）的一个全排列  
    c1=[1c+1（point_number）]; %生成初始解
    for t=1:（point_number） %该层循环是修改圈 
        flag=0; %修改圈退出标志
    for m=1:（point_number-2）
      for n=m+2:（point_number-1）
        if d（c1（m）c1（n））+d（c1（m+1）c1（n+1））           c1（m+1:n）=c1（n:-1:m+1）;  flag=1; %修改圈
        end
      end
    end
   if flag==0
      J（kc1）=1:（point_number）; break %记录下较好的解并退出当前层循环
   end
   end
end
J（:1）=0; J=J/（point_number）; %把整数序列转换成[01]区间上的实数，即转换成染色体编码
for k=1:g  %该层循环进行遗传算法的操作 
    A=J; %交配产生子代A的初始染色体
    c=randperm（w）; %产生下面交叉操作的染色体对 
    for i=1:2:w  
        F=2+floor（（point_number-2）*rand（1））; %产生交叉操作的地址
        temp=A（c（i）[F:（point_number）]）; %中间变量的保存值
        A（c（i）[F:（point_number）]）=A（c（i+1）[F:（point_number）]）; %交叉操作
        A（c（i+1）F:（point_number））=temp;  
    end
    by=[];  %为了防止下面产生空地址，这里先初始化
while ~length（by）
    by=find（rand（1w）<0.1）; %产生变异操作的地址
end
B=A（by:）; %产生变异操作的初始染色体
for j=1:length（by）
   bw=sort（2+floor（（point_number-2）*rand（13）））;  %产生变异操作的3个地址
   B（j:）=B（j[1:bw（1）-1bw（2）+1:bw（3）bw（1）:bw（2）bw（3）+1:（point_number）]）; %交换位置
end
   G=[J;A;B]; %父代和子代种群合在一起
   [SGind1]=sort（G2）; %把染色体翻译成1，...（point_number）的序列ind1
   num=size（G1）; long=zeros（1num）; %路径长度的初始值
   for j=1:num
       for i=1:（point_number-1）
           long（j）=long（j）+d（ind1（ji）ind1（ji+1））; %计算每条路径长度
       end
   end
     [slongind2]=sort（long）; %对路径长度按照从小到大排序
     J=G（ind2（1:w）:）; %精选前w个较短的路径对应的染色体
     
     %记录下平均路径长度数据
     long_mean（k）=mean（long）;
end
path=ind1（ind2（1）:） flong=slong（1）  %解的路径及路径长度
sj=sj.*180./pi;                       %坐标弧度化成角度
xx=sj（path1）;yy=sj（path2）;

lujin.Geometry=‘Line‘;
lujin.Lon=xx;
lujin.Lat=yy;
geoshow（lujin ‘Color‘ ‘blue‘） %画出路径

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件   14278656  2018-05-07 03:46  TSP_中国省会城市\gadm36_CHN_1.shp

     文件       3466  2019-05-17 15:04  TSP_中国省会城市\My_Genetic_Algorithm.asv

     文件       3518  2019-05-17 15:07  TSP_中国省会城市\My_Genetic_Algorithm.m

     文件       1760  2019-05-09 14:03  TSP_中国省会城市\provincial_ capital_coordinate.txt

     目录          0  2019-05-17 15:04  TSP_中国省会城市

----------- ---------  ---------- -----  ----

             14287400                    5