本项目提供了一种利用遗传算法解决旅行商问题(TSP)的具体代码实现方案。通过编码、交叉和变异等操作优化路径长度，适用于初学者学习与研究参考。
实验内容与步骤
TSP 问题是一个经典的 NP 完全问题，在实际应用中很难找到最优解。然而，通过使用遗传算法可以较快地找到接近于最优的解决方案。本实验采用 TSPLIB 数据集，并利用遗传算法进行求解。
染色体设计是遗传算法中的关键部分之一。在本次实验中，我们选择基于路径的方法来构建染色体模型——即一个完整的合法路径被视为一条染色体，例如：12345678 或 51834762（以城市数量为8为例）。
交叉编码方式设计
为了实现有效的遗传操作，在本实验中采用部分匹配交叉的方法。具体步骤如下：
- 首先根据两个父代染色体建立基因对应规则；
- 确定这两个父母的交叉起始位置和结束位置，然后交换需要进行交叉的部分得到子代。
- 对于每一个生成的后代，如果在新的路径中发现重复的城市，则依据先前设定好的映射关系找到合适的替换城市。
例如：假设父代1为 12345678, 父代2为 51834762。交叉过程如下：
步骤1: 建立两个父代之间的基因对应规则。
- 视角从父代1来看，映射关系是：1->5、 2->1、 3->8、 4->3、 5->4、 6->7、 7->6 和8 ->2
- 反过来视角从父代2看，则对应为：5->1, 1->2, 8->3，以此类推。
步骤2: 确定交叉的起始位置和结束位置。例如选择第4个基因到第6个基因进行交换。
- 因此，在本例中，父代1需要互换的部分为：456
- 对应地从父代2选取347作为要替换的内容。
步骤3: 通过上述规则生成子代个体。例如：
对于第一个后代（基于父代1视角）：
首先保持前三个和后两个基因不变，得到123***78
然后根据交叉位置来决定需要替换成什么：第四个为4, 对应于5；第五个是5对应的是4；
第六位6应该替换为7。由于在生成的子代中已经存在重复的城市（如数字），因此按照映射规则进行修正，最终确定第一个后代的编码。
变异操作设计
本次实验采用交换变异来增加种群多样性，即随机选择染色体内的两个基因位置并互换它们的位置。
程序实现步骤：
1. 设定初始群体规模；
2. 随机初始化一个由多个路径组成的初代群体，并计算每个个体的适应度值。
3. 根据适应度比例选取父代进行遗传操作（依据交叉概率决定是否执行染色体间的部分匹配交叉）。
4. 按照设定好的变异率对子代中随机选择的部分基因实施交换变异；
5. 计算新生成群体的适应度值。如果满足终止条件或达到最大迭代次数，则停止算法；否则回到步骤3继续进行遗传操作。
5星
