Page 136 - 2025年第56卷第8期

4 经典算例仿真分析

为验证本研究所提方法的普适性，通过经典 TSP 问题算例对单亲遗传算法、单亲遗传算法（哈密
顿回路筛选）、单亲遗传算法（混沌映射确定变异区间）、高约束遗传算法 4 种不同智能优化算法进行寻
优性能比较。由于本研究是针对特殊情况的路径规划，故而仿真过程中需考虑工程施工的紧前紧后
关系。
4.1 经典 TSP 算例基本信息

4.1.1 算例基本信息 算例是 6 座城市组成的交通网，通过交通网达到城市之间货物流通的目的，6
座城市之间的距离信息如表 1 所示。

表 1 经典 TSP 算例的各城市间距 单位：km
A B C D E F
A 18 8 13 15 8
B 18 18 6 15 19
C 8 18 9 14 5
D 13 6 9 16 14
E 15 15 14 16 9
F 8 19 5 14 9

4.1.2 算例约束条件 由于本研究情景的特殊性，需要对经典案例中货物到达各城市的先后顺序设置
约束以满足本文的研究背景。具体约束规则可根据逻辑自洽进行自主设置，具体约束结果如表 2。
除表 2 中的约束条件外，还需设置起始（终点）城市，以此城市类比为交通运输中的停车场点位，
本算例以城市 F 为起始（终点）城市。
4.1.3 算例任务设置 本研究并不是单一的对一组 A\B\C\D\E\F 城市进行排列，而是每个城市有其运
输车对应的到达次数，结合本算例特点及仿真需求设置任务见表 3。

表 2 经典 TSP 算例约束设置结果表 表 3 算例城市任务

城市 紧后城市 城市 到达次数
A C A 20
B D\E B 20
C A\B\F C 20
D A\B\F D 10
E A\B\F E 10
F A\B F 6

4.2 经典 TSP 算例仿真结果 在设置 TSP 算例的基础上，应用传统单亲遗传算法（PGA）、单亲遗传算
法结合哈密顿回路筛选（PGA（H））、单亲遗传算法结合混沌映射（PGA（L））以及本文提出的高约束单亲
遗传算法（HC-PGA）对其进行仿真模拟。为控制变量 4 种算法均设置迭代 400 次。各算法迭代图像如图
4 所示。
由图 4 中 4 种算法所得最小运输距离分别为 828、823、827 和 805 km，故本研究所提出的高约束
单亲遗传算法在解决此经典案例时寻优效果最好。虽然 PGA（L）在 90 代左右开始收敛，但陷入局部最
优导致最终优化效果不佳。综上，多算法性能评价下高约束单亲遗传算法在解决此类型问题时有较强
的鲁棒性与优越性。

— 1100 —