1701007716
1701007717
1701007718
1701007719
图6-10 简单遗传算法流程图
1701007720
1701007721
基于遗传算法的旅行商算法流程详细步骤如下。
1701007722
1701007723
Step1：采用邻近算法生成初始种群。
1701007724
1701007725
Step2：计算适应值，保存当前最优染色体Tmax。
1701007726
1701007727
Step3：交叉操作。
1701007728
1701007729
Step4：计算适应值，保存最优染色体到Tmax。
1701007730
1701007731
Step5：判断是否满足变异条件，Yes跳转到Step7，No跳转到Step7。
1701007732
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 旅行节点标记