进化算法 - 旅行推销员 - 适应度函数

计算科学 算法 图论 组合学
2021-11-28 09:16:35

我正在尝试使用遗传算法解决这个问题,并且很难选择适应度函数。我的问题与最初的旅行商问题略有不同,因为人口和获胜单位不一定包含所有城市。

因此,我为每个单位设置了 2 个值:他访问的城市数量、总时间和他访问城市的顺序。我尝试了 2-3 健身功能,但他们没有给出好的解决方案。

我需要一个良好的健身功能的想法,它考虑到他访问过的城市数量以及总时间。

编辑:更准确的描述

PTSP 的目标是在最少的时间步长内访问地图的最大数量的航路点。该地图采用二维板的形式,其中分布着十个航路点,并存在多个障碍物。下图是带有障碍物和航点的地图示例

谢谢!

1个回答

你有一个多目标优化问题:你想最大化城市数量,同时最小化时间。这本身并不是一个很好的问题,因为您需要说出两种解决方案中的哪一种(N1,T1)(N2,T2)如果两条路径访问更好Ni城市并采取Ti时间单位。那么,您需要做的是首先定义此类元组的部分排序,以描述您认为哪个更好。一旦你有了它,提出一个目标函数就会变得很明显。