genetic-algorithm - 为一群不同出身的推销员计划一次旅行

Question

我可以将这个问题命名为“具​​有互节点的多个旅行推销员问题”。我有一群来自城市不同地点的人。他们想计划参观特定的商店。我怎么解决这个问题？如何对问题建模以使用元启发式算法，例如 GA 或 ACO？

Answer 1

我将假设问题如下；

• 每个人都可能想去大地图上的任何一组城市。

• 两个或更多人可以同时在同一个城市

• 两个或更多人可以同时使用相同的边缘。

对于遗传算法，每个染色体看起来像这样；

人 1 的路线| 人 2 的路线| 人 3 的路线..

一个示例生成可以是；

染色体1= 2,6,7,1|4,7,2|3,5,6
染色体2= 6,7,2,1|2,4,7|3,5,6

您将需要分别为每条路线应用交叉和变异操作。您可以使用 PMX（部分映射交叉）之类的交叉方法进行排列表示。您可以使用随机交换、插入、争夺突变等操作。

对于蚁群优化，每只蚂蚁都需要在每次迭代中为每个人构建解决方案。此外，应该为每个人的路线存储不同的信息素值。因为，即使他们有共同的位置（例如他们都有城市 2 和 3），这并不意味着这些城市之间的边缘应该具有相同的合意性（2 和 3 之间的边缘可能适合 person1 但它可以不适合person2）。

所以，我认为最好分别为每个人找到路线。因为每个人的路线的解决方案之间不可能有信息交换。