我正在用 Java 编写一个时间表生成器，使用人工智能方法来满足硬约束并帮助找到最佳解决方案。到目前为止，我已经实现了迭代构造(最受约束的第一启发式)和模拟退火，并且我正在实现遗传算法。
有关该问题的一些信息，以及我如何表示它: 我有一组事件、房间、功能(事件需要且房间满足)、学生和时段 问题在于为每个事件分配一个时段和一个房间，这样学生就不需要在一个时段参加两个事件，所有分配的房间都满足必要的要求。
我有一个评分函数，对于每组作业，如果作业对软约束违规进行评分，因此重点是尽量减少这种情况。
我实现 GA 的方式是从迭代构建生成的群体开始(这可以使事件未分配)，然后执行正常步骤:评估、选择、交叉、变异并保留最好的。冲洗并重复。
我的问题是我的解决方案似乎改进太少。无论我做什么，种群都会趋于随机适应并被困在那里。请注意，这种适应度总是不同的，但仍然会出现一个下限。
我怀疑问题出在我的交叉函数中，这是其背后的逻辑:
随机选择两个作业进行交叉。我们将它们称为分配 A 和 B。对于所有 B 的事件，执行以下过程(选择 B 的事件的顺序是随机的):
获取A中对应的事件并比较赋值。可能会发生 3 种不同的情况。
- 如果只有其中一个未分配并且是否可以复制 child 的其他作业，则选择此作业。
- 如果两者都被赋值，但只有其中一个不创建
分配给 child 时发生冲突，则选择该 child 。 - 如果两者都已分配且没有产生冲突，则 它们是随机选择的。
在任何其他情况下，事件都处于未分配状态。
这会创建一个 child ，其中包含一些 parent 的作业，一些母亲的作业，所以在我看来这是一个有效的函数。而且，它没有打破任何硬性约束。
对于突变，我使用 SA 的邻近函数根据子项给我另一个分配，然后替换该子项。
再说一遍。通过这种设置，初始种群为 100，GA 运行并始终趋于稳定在某个随机(高)适应度值。有人可以告诉我我可能做错了什么吗？
谢谢
编辑:格式化并清除一些内容
最佳答案
我认为只有当解的一部分(向量的一部分)作为解的独立部分具有意义时，遗传算法才有意义，这样交叉函数就可以整合两个解向量之间解的有效部分。就像 DNA 序列的某个部分控制或影响个体的特定方面一样，例如眼睛的颜色就是一个基因。然而，在这个问题中，解向量的不同部分相互影响，使得交叉几乎毫无意义。这导致(我的猜测)算法很快地收敛到单个解决方案，不同的交叉和突变仅对适应度产生负面影响。
我不认为 GA 是解决这个问题的正确工具。
关于artificial-intelligence - 遗传交叉函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10618579/