-6

如果我有一个节点网络，我如何使用遗传算法来计算任意两个节点之间的最短路径？

4

1 回答 1

3

用 GA 解决 TSP 问题怎么样？

TSP 是一个 NP 完全问题。也就是说，不可能在多项式时间内找到 TSP 问题的解决方案。但是，给定一个解，可以验证它是否是多项式时间内的解。

元启发式方法（例如遗传算法）可以作为解决 TSP 问题的工具进行研究，因为它们采用基于群体的方法。通过这种方式，他们可以在算法运行时“处理”大量解决方案。要使用 GA 解决任何问题，我们需要定义以下内容：

  • 健身功能
  • 单个染色体
  • 交叉算子
  • 突变

适应度函数：这里的适应度函数很容易定义。它应该是推销员在可能的城市中进行一定的旅行所必须穿越的距离。我们力求在 TSP 中尽量减少这种情况。

染色体：一条染色体可以简单地定义如下——假设我们有五个城市 A、B、C、D 和 E。然后想象一个长度为 5 的染色体，染色体的每个“槽”包含 5 个城市中的任何一个。例如，在我们的例子中，A,C,D,B,E 是一个有效的染色体。

交叉算子：在遗传算法中使用交叉算子来“混合”两个父母，希望得到更健康的孩子。GA 文献中提供了各种交叉算子，每个算子都有不同的方法来实现相同的目标。例如，考虑单点交叉。它随机选择一个交叉点，然后在两者之间交换位。在不涉及其他专业分频器的情况下，让我们看看对我们来说什么是好的分频器。在我们的例子中，两条亲本染色体将分别具有 A、B、C、D、E 的排列。无论我们选择哪种交叉方法，我们都必须在这里注意一个事实：交叉运算符不应该创建一个城市不止一次出现的孩子，即无效染色体。一种这样的交叉运算符是“Order Crossover”

突变：突变可以简单到在这里简单地交换单个染色体中的两个位置。

总的来说，这就是使用 GA 的 TSP 的工作方式：

  • 您创建了一个个体群体，每个个体的大小为 5，并包含 A、B、C、D、E 的排列（将有很多相同排列的重复）

  • 您开始 GA 并在每次运行中，通过使用提供给您的距离参数计算距离，根据适应度函数评估每个个体

  • Crossover，Mutation 改进了个体，最后最好的解决方案是具有最佳游览的个体，即。A,B,C,D,E 的最优排列。

希望有帮助！

于 2009-12-16T04:31:18.643 回答