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
采用遗传算法的旅行商问题求解程序如下：
1701007783
1701007784
function varargout = tsp_ga(xy，dmat，popSize，numIter，showProg，showResult) %Process Inputs and Initialize Defaults nargs = 6; for k = nargin:nargs-1 switch k case 0 xy = 10*rand(50，2); case 1 N = size(xy，1); a = meshgrid(1:N); dmat = reshape(sqrt(sum((xy(a，:)-xy(a’，:)).^2，2))，N，N); %矩阵维数变换 case 2 popSize = 100; case 3 numIter = 1e4; case 4 showProg = 1; case 5 showResult = 1; otherwise end end %Verify Inputs [N，dims] = size(xy); [nr，nc] = size(dmat); if N ~= nr || N ~= nc error(‘Invalid XY or DMAT inputs!’) end n = N; %Sanity Checks popSize = 4*ceil(popSize/4); numIter = max(1，round(real(numIter(1)))); %求取最大值 showProg = logical(showProg(1)); showResult = logical(showResult(1)); %Initialize the Population 初始化种群 pop = zeros(popSize，n); pop(1，:) = (1:n); for k = 2:popSize pop(k，:) = randperm(n); end %Run the GA globalMin = Inf; totalDist = zeros(1，popSize); distHistory = zeros(1，numIter); tmpPop = zeros(4，n); newPop = zeros(popSize，n); if showProg pfig = figure(‘Name’，‘TSP_GA | Current Best Solution’，‘Numbertitle’，‘off’); end for iter = 1:numIter %迭代次数 %Evaluate Each Population Member (Calculate Total Distance) for p = 1:popSize d = dmat(pop(p，n)，pop(p，1)); %Closed Path 选择算子 for k = 2:n d = d + dmat(pop(p，k-1)，pop(p，k)); %交叉算子、变异算子 end totalDist(p) = d; %计算适应度 end %找到最小和最大适应度的染色体及它们在种群中的位置 %Find the Best Route in the Population [minDist，index] = min(totalDist); distHistory(iter) = minDist; %代替上一次进化中最好的染色体 if minDist < globalMin globalMin = minDist; optRoute = pop(index，:); if showProg %Plot the Best Route figure(pfig); rte = optRoute([1:n 1]); if dims > 2， plot3(xy(rte，1)，xy(rte，2)，xy(rte，3)，‘r.-‘); else plot(xy(rte，1)，xy(rte，2)，‘r.-‘); end title(sprintf(‘Total Distance = %1.4f， Iteration = %d’，minDist，iter)); end end %Genetic Algorithm Operators randomOrder = randperm(popSize); for p = 4:4:popSize rtes = pop(randomOrder(p-3:p)，:); dists = totalDist(randomOrder(p-3:p)); [ignore，idx] = min(dists); %#ok bestOf4Route = rtes(idx，:); routeInsertionPoints = sort(ceil(n*rand(1，2))); I = routeInsertionPoints(1); J = routeInsertionPoints(2); for k = 1:4 %Mutate the Best to get Three New Routes tmpPop(k，:) = bestOf4Route; switch k case 2 %倒置 tmpPop(k，I:J) = tmpPop(k，J:-1:I); case 3 %交换位置 tmpPop(k，[I J]) = tmpPop(k，[J I]); case 4 %后一刻的值替换当前值 tmpPop(k，I:J) = tmpPop(k，[I+1:J I]); otherwise %不做任何操作 end end newPop(p-3:p，:) = tmpPop; end pop = newPop; end %画图 if showResult %绘制 GA算法求解结果 figure(‘Name’，‘TSP_GA | Results’，‘Numbertitle’，‘off’); %subplot(2，2，1); figure(1)， pclr = ~get(0，‘DefaultAxesColor’); if dims > 2， plot3(xy(:，1)，xy(:，2)，xy(:，3)，’.’，‘Color’，pclr); else plot(xy(:，1)，xy(:，2)，’.’，‘Color’，pclr); end title(‘城市位置’); grid on % subplot(2，2，2); figure(2)， %画图 imagesc(dmat(optRoute，optRoute)); title(‘距离矩阵-imagesc’); % subplot(2，2，3); figure(3)， %画图 rte = optRoute([1:n 1]); if dims > 2， plot3(xy(rte，1)，xy(rte，2)，xy(rte，3)，‘r.-‘) ; else plot(xy(rte，1)，xy(rte，2)，‘r.-‘); %画图 end title(sprintf(‘最短距离 = %1.4f’，minDist)); grid on % subplot(2，2，4); figure(4)， %画图 plot(distHistory，‘b’，‘LineWidth’，2); title(‘最佳适应度曲线’); grid on set(gca，‘XLim’，[0 numIter+1]，‘YLim’，[0 1.1*max([1 distHistory])]); end %Return Outputs if nargout varargout{1} = optRoute; varargout{2} = minDist; end
1701007785
1701007786
运行程序得如图6-14所示。
1701007787
1701007788
1701007789
1701007790
1701007791
图6-14 最优路径
1701007792
1701007793
遍布每一个城市，通过程序找到了一条遍历所有城市且每个城市只被访问一次的路径。
1701007794
1701007795
当然，由于城市位置较少，用户可以手动进行计算绘图，然而当城市有50个或者更多时，人眼看都要看花，更何况还是求解最优解，因此智能化程序应用，给我们更大的平台去挖掘事物的本质。
1701007796
1701007797
1701007798
1701007799