基于遗传算法的旅行商问题优化方案咨询

针对你用遗传算法求解固定起点（id1）TSP时总距离无法达标（当前约9500，目标≤9000）且适应度计算次数受限（≤250000）的问题，以下是具体优化方向：

1. 优化初始种群质量 #

• 加入启发式种子个体：用最近邻算法生成3-5条初始路径（从id1出发，每次选择最近的未访问节点），将这些路径加入初始种群，直接提升种群的平均路径质量，减少后续迭代的计算成本。
• 避免随机冗余：初始种群中不要完全随机生成路径，限制重复路径的数量，减少无效个体占用适应度计算次数。

2. 减少无效适应度计算 #

• 缓存节点间距离：预先计算所有节点对的距离，存入二维数组或字典distance_matrix，后续计算路径总距离时直接查表，避免重复计算节点间距离，节省大量计算资源。示例：

  # 预先计算距离矩阵
  distance_matrix = [[0]*n for _ in range(n)]
  for i in range(n):
      for j in range(n):
          distance_matrix[i][j] = calculate_distance(node[i], node[j])
  

• 路径去重：每次迭代后对种群中的路径去重，避免相同路径重复计算适应度，变相增加有效迭代次数。

3. 适配约束的遗传算子调整 #

交叉算子（保证起点终点为id1） #

• 使用约束兼容的顺序交叉（OX）：交叉时固定首尾的id1，仅对中间的节点序列进行交叉操作，避免破坏起点终点的约束。
• 降低交叉概率：将交叉概率从0.7-0.9调整为0.5-0.7，减少对优秀个体基因的破坏，尤其是当种群中出现接近目标的路径时。

变异算子（定向优化局部路径） #

• 引入2-opt局部优化作为变异操作：对个体路径随机选取两个非首尾节点，反转中间的路径段，仅计算前后4条线段的距离变化（而非整条路径），如果新路径更短则保留。这种变异能快速优化局部路径，且计算量小。
• 定向变异：针对路径中距离最长的20%相邻节点对，进行交换或反转操作，提升变异的针对性，避免无意义的随机变异。
• 适度提高变异概率：将变异概率从0.1调整为0.2-0.3，增加种群多样性，避免算法陷入局部最优。

4. 选择策略与精英保留 #

• 采用锦标赛选择：每次从种群中随机选取3-5个个体，选择其中最优的进入下一代，相比轮盘赌选择，既能保证优秀个体被选中，又能保留种群多样性。
• 精英保留策略：每次迭代保留种群中前10%的最优个体直接进入下一代，避免优秀基因丢失，加快收敛速度。

5. 种群规模与迭代次数平衡 #

在适应度计算次数≤250000的约束下，调整种群规模和迭代次数的比例：

• 比如将种群规模从200缩小到100，迭代次数可从1250次增加到2500次，更多的迭代次数有助于算法跳出局部最优，同时总计算次数保持在约束内。
• 加入种群多样性检测：当种群中超过80%的个体路径距离差小于5%时，随机引入2-3条新的启发式路径，避免算法早熟。

6. 适应度函数与终止条件优化 #

• 加入约束惩罚项：当路径总距离超过9000时，在适应度中额外加上(总距离-9000)*k的惩罚（k建议设为2-3），让算法更倾向于搜索符合约束的解，同时避免过度惩罚导致算法收敛停滞。
• 提前终止：当连续50代最优解没有提升，且当前最优距离接近9000时，提前终止迭代，将剩余的适应度计算资源用于对当前最优解进行局部优化（比如多次2-opt操作）。

内容的提问来源于stack exchange，提问作者zellez11