需要帮助构建遗传算法的染色体

Question

我需要设计一个使用遗传算法的时间表问题。问题的参数为:教师:8个科目:16个教室:4天:5个时段:5个

染色体结构应该是什么？

Answer 1

完全公开，这个答案引用了我自己的npm包。不过，我会尝试让我的答案尽可能通用。

如果我们使用像geneticalgorithm这样的东西来解决问题，您将需要实现以下内容：

fitness Function

• mutation Function

• crossover Function

• diversity Function (或doesABeatBFunction)

)

1. fitness Function

你的问题真的跨越了所有4个函数。让我们假设您的染色体函数只是普通的老式JSON，并遍历每个函数并进行讨论。

适应度函数

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

变异函数

你能为你的JSON编写一个变异函数吗？是。换两个老师，或者换几天，或者换一个教室。它不必创建有效的子项(但这可能是一个优势)

交叉函数

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

多样性函数

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

结论

遗传算法的核心依赖于上述功能的实现，并且与染色体无关。只有您的函数实现必须与染色体一起工作。

干杯!