实验内容与步骤 TSP 问题是一个经典的 NP 问题,很难得到最优解,利用遗传算法,可以比较快的找到近似最优。本实验采用 TSPLIB 的数据,利用遗传算法进行求解。 染色体设计 染色体设计是遗传算法的关键之一,在本实验中,采用基于路径的方法进行设计,即一条完整合法的路径为一个染色体。如 12345678 或 51834762 (以 8 个城市为例)。 交叉编码方式设计 在本实验中采用部分交叉编码方式,编码过程如下: 根据两个父代染色体建立基因对应规则 确定父代中交叉的起始位置、结束位置 互换需要交叉的编码得到子代,对于每一个子代,如果交叉的部分已经在存在,则根据基因对应规则对寻找替换基