1701007708
旅行商问题为一个NP问题，有多种解，一般情况下，多采用生物智能算法进行寻优，找到一组可行解即可，笔者采用遗传算法进行分析。
1701007709
1701007710
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机优化搜索方法。它是由美国的J．Holland教授于1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
1701007711
1701007712
遗传进化操作简单、易懂，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。
1701007713
1701007714
遗传算法GA的流程图如图6-10所示。
1701007715
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