0

我不确定我是否完全理解遗传算法及其工作原理,我正在尝试通过 ai4r http://ai4r.rubyforge.org/geneticAlgorithms.html学习

如果在我认为可以通过 GA(?)解决的 Job Shop Scheduling 中,任何单个工作的成本不是基于它与它的前辈的关系吗?我在想我会根据染色体的位置来计算成本,并用它的放置程度而不是二进制值的动态分数来计算成本,但我不确定这是否有效。

有人有这方面的经验吗?还是只有当任何两个基因组之间的差异是静态的时,GA 才起作用?

我希望我在这里有正确的术语,正如我所提到的,我只是在学习。

- - - - - - - - - - - -更新 - - - - - - - - - - - - - ---------

我想我在这里使用了一些错误的术语。当我认为我真正想要使用的是cost matrix.

我将要使用的示例描述了这一点

每个染色体必须代表该问题的可能解决方案。此类包含一个包含访问节点列表(旅游城市)的数组。旅行的规模是从旅行成本矩阵中自动获得的。您必须在运行遗传搜索之前分配成本矩阵。以下成本矩阵可用于解决仅 3 个城市的问题:


数据集 = [ [ 0, 10, 5],
        [ 6, 0, 4],
        [25, 4, 0]
    ]
Ai4r::GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)

所以在我的例子中,我认为每条染色体的“成本”是基于它的邻居的动态的。

4

2 回答 2

2

既然您在评论中要求将其作为答案,我也冒昧地总结了我之前的回答,以便将所有内容集中在一个地方。“什么是惩罚条款”的具体问题的答案在下面的第 3 项中。

标准遗传算法的工作方式是每个“染色体”都是问题的完整解决方案。在您的情况下,提交作业的顺序。我认为,混淆的中心是这样一个概念,即由于该时间表中特定工作对健康的个人贡献会根据时间表的其余部分而有所不同,因此您必须需要一些“动态”的东西。这不是真的。从 GA 的角度来看,唯一具有适应度的就是整个解。因此,动态问题是整个时间表的适应度可以随时间变化的问题。回到 TSP,一个动态问题是这样一个问题,即按照 A、B、C、D 和 E 的顺序游览城市,每次尝试时实际上都有不同的距离。即使通过 B 游览的成本取决于游览中 B 之前和之后的城市,但一旦你决定了,成本就是静态的,而且因为 GA 只收到整个旅行的成本,它所知道的只是 [ A,B,C,D,E] 具有恒定的适应度。不需要动态诡计。

现在,您的第二个问题是如何处理约束,例如,对于 TSP 示例,如果您需要确保推销员在特定时间到达巴黎怎么办?通常,有三种方法可以尝试处理此问题。

  1. 永远不要让他在 2:00 之前到达那里的解决方案生成。有时这很容易,有时却非常困难。例如,如果约束条件是“他不能从 X 市开始”,那么很容易不生成不以 X 开头的解决方案。但通常,简单地找到有效的解决方案可能很困难,因此这种方法不会真的工作。

  2. 允许违反约束,但之后修复它们。在 TSP 示例中,您让交叉和突变产生任何可能的巡回演出,但然后扫描它以查看他是否太晚到达巴黎。如果是这样,请在游览中将巴黎的位置与一些较早的城市交换。不过,有时很难找到修复违规行为的好方法。

  3. 惩罚不可行解决方案的适用性。在这里,我的想法是,即使我不能阻止他去巴黎太晚,如果他这样做我也无法解决,我至少可以任意让身体状况变得更糟。对于 TSP,健身是游览的长度。所以你可能会说如果一次旅行让他去巴黎太晚了,适应度是旅行的长度+100。那让我们把解决方案留在人群中(否则可能会很好,所以你希望它有机会传递它的一些基因),但你降低了它被选中的可能性,因为你的选择和替换方法会选择具有更好适应度值的个体。

对于您的 JSP 问题,通常您希望最小化制造时间。如果您确实有一些限制,则可以使用相同的三个选项。但据我所知,你并没有这样的限制。我认为你试图在这个过程中注入太多的知识,而不是让进化算法自己想出它。也就是说,您不必担心告诉 GA 某些工作安排比其他工作安排更好。您只需将更高的适应度分配给更好的适应度,然后让过程收敛。

也就是说,注入这样的信息通常是一件非常好的事情,但你首先要对基本算法有一个很好的理解。假设我们知道对于 TSP,一个好的解决方案更有可能将彼此靠近的城市连接起来。我在 GA 中使用该信息的方式是非均匀地生成随机解决方案(可能使用贪婪的启发式)。我也可以用定制的东西替换标准的交叉和变异算法。突变通常比交叉更容易做到这一点。为了改变 TSP 解决方案,我可能会选择两个连接的城市,断开连接,然后寻找一种“更近”的方式重新连接它们。也就是说,如果一个游览是[A,B,C,D,E,F,G,H],我可能会随机选择边[B,C],然后再寻找另一个边,可能是[F,G ], 这样当我将它们交叉连接以获得 [A,B,G,D,E,F,C,H] 时,总行程长度较短。我什至可以将这种突变扩展到一步以上——创建一个循环,不断尝试断开和重新连接边缘,直到找不到更短的路径。这导致了通常称为混合 GA,因为它是与本地搜索混合的 GA;有时也称为模因算法。这些类型的算法通常优于黑盒 GA,因为您正在给算法“提示”,使其偏向于尝试您期望好的事情。这导致了通常称为混合 GA,因为它是与本地搜索混合的 GA;有时也称为模因算法。这些类型的算法通常优于黑盒 GA,因为您正在给算法“提示”,使其偏向于尝试您期望好的事情。这导致了通常称为混合 GA,因为它是与本地搜索混合的 GA;有时也称为模因算法。这些类型的算法通常优于黑盒 GA,因为您正在给算法“提示”,使其偏向于尝试您期望好的事情。

我认为这个模因算法的想法非常接近你在最初的问题中遇到的问题,即想知道如何处理特定工作对健康的贡献取决于其他工作在日程表中的位置。唯一的绊脚石是您有点不走运,因为将其视为“动态”的合理想法会导致您误入歧途,因为“动态”实际上在这里意味着完全不同的东西。

所以总结一下,你的问题没有什么“动态的”,所以人们用 GA 对动态问题所做的事情将完全没有帮助。标准 GA 无需花哨的技巧即可工作。但是,可以将使用您所拥有的关于哪些时间表工作得更好的信息的想法引入到遗传算子中,并且可能会导致明显更好的整体算法。

于 2012-03-22T14:53:30.927 回答
0

您将使用 GA 来查找执行多项工作的最佳顺序,或者说最好地利用一天资源的那些工作。所以是的,它们会相互关联。

因此,您的健康指标将针对 seq 1、3、4、5、6、2。

看看说找到最短路径算法,然后开始有意义

于 2012-03-21T12:40:51.513 回答