1701007700
1701007701
1701007702
1701007703
1701007704
1701007705
1701007706
其中，K是V的全部非空子集，｜K｜是集合K中包含图G的全部顶点的个数。
1701007707
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