1701007733
Step6：变异操作，计算适应值并保存当前最优染色体Tmax，跳转到Step3。
1701007734
1701007735
Step7：选择操作，计算适应值并保存当前最优染色体Tmax，跳转到Step3。
1701007736
1701007737
了解基于遗传算法的旅行商求解流程后，接下来就是选择求解问题背景了。
1701007738
1701007739
之所以选取湖北省地图作为研究对象，是因为笔者作为湖北人，对湖北省还是情有独钟的，当然大家也可以选取自己的目标地。基于湖北省地图，对湖北省各市进行旅行节点设置。
1701007740
1701007741
【问题】一个旅行者如何遍布全部节点（各城市），且使得旅行路径最短。
1701007742
1701007743
【分析】
1701007744
1701007745
具体的湖北省板块地图如图6-11所示。
1701007746
1701007747
1701007748
1701007749
1701007750
图6-11 湖北省地图
1701007751
1701007752
选取湖北省地图上的各市作为节点，旅行者将通过这些节点，各市所在地图坐标具体如表6-10所示。
1701007753
1701007754
表6-10 各市地图坐标
1701007755
1701007756
坐标 坐标x 坐标y 十堰市 312 95 襄樊市 474 181 恩施土家族苗族自治州 144 499 宜昌市 385 387 荆门市 488 342 荆州市 503 444 随州市 639 224 孝感市 713 343 武汉市 760 395 黄冈市 840 406 鄂州市 828 418 黄石市 862 449 咸宁市 769 508 根据表6-10，在地图上进行标记，编程如下：
1701007757
1701007758
clc,clear,close all %清屏和清除变量 warning off %消除警告 im = imread(‘hubei.bmp’); %读图 figure(1),imshow(im) %显示图像 %城市点坐标 x1 = 312; y1 = 95; %十堰市 x2 = 474; y2 = 181; %襄樊市 x3 = 144; y3 = 499; %恩施土家族苗族自治州 x4 = 385; y4 = 387; %宜昌市 x5 = 488; y5 = 342; %荆门市 x6 = 503; y6 = 444; %荆州市 x7 = 639; y7 = 224; %随州市 x8 = 713; y8 = 343; %孝感市 x9 = 760; y9 = 395; %武汉市 x10 = 840; y10 = 406; %黄冈市 x11 = 828; y11 = 418; %鄂州市 x12 = 862; y12 = 449; %黄石市 x13 = 769; y13 = 508; %咸宁市 xy = [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13; y1,y2,y3,y4,y5,y6,y7,y8,y9,y10,y11,y12,y13]’; %城市的位置坐标 n = 13; %城市的数量 hold on %图像保持句柄 plot(xy(:,1),xy(:,2),‘r.’,‘Markersize’,20) %绘制图形
1701007759
1701007760
运行程序得到如图6-12所示图形。
1701007761
1701007762
1701007763
1701007764
1701007765
图6-12 旅行节点标记
1701007766
1701007767
为了清晰地表示各城市之间的位置关系，采用欧式距离矩阵进行显示，如图6-13所示。
1701007768
1701007769
1701007770
1701007771
1701007772
图6-13 各城市之间的距离图
1701007773
1701007774
由图6-13可知，不同城市之间的距离是不同的，城市1距离城市6、城市7、城市8较远。图中颜色越深，表示相距越远。
1701007775
1701007776
一个旅行者如何游遍整个湖北省各城市使得路径最短呢，这是一个优化问题，笔者采用遗传算法进行求解分析，遗传算法基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。
1701007777
1701007778
具体的MATLAB程序如下：
1701007779
1701007780
popSize = 60; %种群的大小，一般被4整除 numIter = 1e4; %算法迭代的次数 showProg = 1; %如果满足条件，执行遗传算法的步骤 showResult = 1; %如果满足条件，执行遗传算法的结果 a = meshgrid(1:n); dmat = reshape(sqrt(sum((xy(a,:)-xy(a’,:)).^2,2)),n,n); %城市之间的距离/成本 [optRoute,minDist] = tsp_ga(xy,dmat,popSize,numIter,showProg, showResult); %%Output: %optRoute 遗传算法得出的最优路径 %minDist 最优路径下的成本值或距离值 %% figure, imshow(im); %显示图形 for i=1:n hold on plot(xy(:,1),xy(:,2),‘r.’,‘Markersize’,20); %绘制图形 text(xy(i,1),xy(i,2)+0.08,num2str(i)); %标记文本 end for i=1:n-1 plot([xy(optRoute(1,i),1),xy(optRoute(1,i+1),1)],[xy(optRoute (1,i),2),xy(optRoute(1,i+1),2)],‘r-‘,‘linewidth’,2) hold on %图像保持句柄 end for i=n plot([xy(optRoute(1,i),1),xy(optRoute(1,1),1)],[xy(optRoute (1,i),2),xy(optRoute(1,1),2)],‘r-‘,‘linewidth’,2) hold on %图像保持句柄 end
1701007781
1701007782
采用遗传算法的旅行商问题求解程序如下：