0

我需要使用遗传算法设计一个时间表问题。该问题的参数是： 教师：8 学科：16 教室：4 天数：5 时隙：5

染色体结构应该是什么？

4

1 回答 1

0

完全披露，这个答案引用了我自己的 npm 包。我会尽量让我的答案尽可能通用。

如果我们使用遗传算法之类的方法来解决问题，则需要实现以下内容：

  1. 健身功能
  2. 变异函数
  3. 交叉功能
  4. 多样性函数（或dosABeatBFunction）

您的问题确实涵盖了所有 4 个功能。让我们假设您的染色体函数只是普通的旧 JSON，然后遍历每个函数并进行讨论。

健身功能

适应度函数可以处理 JSON 吗？当然，你可以这样做。如果 JSON 不是有效的时间表，您可以将其分配为零。如果您能以某种方式将 1 个无效的时间表评为比另一个更好，那就更好了。

突变函数

你可以为你的 JSON 编写一个突变函数吗？是的。调换 2 位老师，或调换天数或教室。它不必创建有效的孩子（但这可能是一个加号）

分频功能

无论格式如何，这都可能很棘手。在你完成变异函数并且可以看到你的算法实际上进化出更好的答案之后，然后在交叉上工作。交叉可能意味着从一个父母那里获得部分答案，从另一个父母那里获得部分答案。考虑到这一点，您可以使用其中一个的老师和另一个的教室。Crossover 不必涵盖所有可能的数据编码，它就非常有用。分阶段实施并独立于遗传算法对其进行测试。

多样性功能

你能衡量两个 JSON 配置是相似还是不同吗？这应该是相当直截了当的。检查 JSON 中的每个节点以查看它是否相等将是一个合理的第一个实现。

结论

我相信你的染色体结构几乎可以是任何东西，只要你能想象如何实现上述功能。我提出 JSON 是因为它不是一种结构，而是一种存储几乎任何结构的方式，只是为了证明这一点。

遗传算法的核心依赖于上述功能的实现，独立于染色体。只有您的函数实现必须与染色体一起使用。

干杯!

于 2017-05-18T15:05:24.497 回答