问用遗传算法求解费用最小的运输问题

EN

首先，你应该了解什么是遗传算法，以及为什么我们这么叫它。因为我们的行为就像一个单细胞有机体，进行交叉和突变以达到更好的状态。

所以，你需要首先实现你的染色体。在你的情况下，让我们站在一边，客户或工厂。让我们以客户为例。您的解决方案将如下所示

1个-> A

2个-> B

3 -> C

因此，您的示例染色体是"ABC"。然后创建另一个染色体(例如“BCA”)，现在您需要一个想要最小化/最大化的拟合函数。此函数将计算您的染色体的繁殖机会。在你的情况下，这将是总成本。编写一个函数来计算给定工厂和给定客户的成本。

现在，你要做的是，

• 随机选取2条染色体。(权重通过拟合函数计算)
• 从2条染色体中选择一个索引，并通过使用它们的切换部分来创建新的染色体。
• 如果新的染色体有无效的部分(如您的情况下的"ABA" )，请进行修复移动(例如，使“A”之一，"C“)。如果之前没有新的染色体，我们称它为"mutation".
• Add。
• 再次转到first process。

您将在一些迭代中执行此操作。你可能有上千条染色体。当你认为“足够了”时，停止这个过程，并对染色体集进行升序/降序排序。第一条染色体就是你的结果。

我意识到这使得这个过程依赖于时间/染色体。我知道，如果你运行得不够充分，你可能会也可能找不到最优的(生物学上认为是最合适的)染色体。这就是所谓的遗传算法。即使你的第一次运行和第二次运行也可能会产生或不会产生相同的结果，这很好。

就你的情况而言，可能的染色体集非常小，所以我保证你会在一两秒内找到最优的。因为整个染色体组对你来说都是["ABC", "BCA", "CAB", "BAC", "CBA", "ACB"]。

总而言之，应用遗传算法需要3个信息：

• 我的染色体应该是怎样的？(和初始染色体组)在chromosomes?

中进行交叉时，我的合适function?

• How是什么？

这个问题还有其他一些需要关心的事情：

• 在没有变异的情况下，遗传算法可以陷入局部最优。它仍然可以用于constraints.
• Even的优化问题如果存在一个染色体，而选择交叉的机会非常低，那么在迭代结束之前，您不应该对染色体集进行排序和截断。否则，你可能会陷入局部极值，甚至更糟，你可能会得到一个普通的候选解，而不是全局最优。
• 为了加快你的过程，选择不相似的初始染色体。如果没有足够的突变率，寻找全局最优可能是一件很痛苦的事情。

正如nejdetckenobi的答案中所提到的，在这种情况下，解决方案搜索空间太小，即只有8个可行解决方案["ABC", "BCA", "CAB", "BAC", "CBA", "ACB"]。我假设这只是您的问题的简化版本，并且您的问题实际上包含更多的工厂和客户(但工厂和客户的数量是相等的)。在这种情况下，你可以利用特殊的变异和交叉来避免重复客户的不可行解，例如["ABA", 'CCB', etc.]。

对于突变，我建议使用交换突变，即随机选择两个客户，交换他们对应的工厂(位置)：

ABC突变为ACB

ABC变异为CBA