用于计算时间表的算法给出限制

Question

我正在考虑一个假设的问题,并从算法的角度寻找如何解决问题的指导.

问题:

考虑一所大学.您有以下对象:

• 教学人员.每个工作人员都会教一篇或多篇论文.
• 学生们.每个学生需要一篇或多篇论文.
• 客房.客房容纳一定数量的学生,并包含某些类型的设备.
• 文件.需要某种类型的设备,并且每周需要一定的时间.

考虑到有关入学的信息(即每篇论文中有多少学生注册,以及分配哪些人员来教授每篇论文),我如何计算遵守以下限制的时间表:

1. 工作人员一次只能教一件事.
2. 学生一次只能参加一篇论文.
3. 客房只能容纳一定数量的学生.
4. 需要某种类型设备的纸张只能放在提供该类设备的房间内.
5. 营业时间为周一至周五,8-12和1-5.

讨论:

实际上,我并不太关心上面概述的情况 - 这是我很好奇的一般问题.乍一看在我看来,它似乎非常适合遗传算法,但这种算法的适应度函数将非常复杂.

尝试解决这种约束满足问题的好方法是什么？

我想可能没有办法完美地解决这个问题,因为学生们很可能会结合导致不可能出现的情况,特别是随着学生和论文数量的增加.

Answer 1

继续遗传算法，我认为适应度函数不会非常复杂，恰恰相反。

您基本上只需检查每个约束（您只有 5 个）的候选解决方案（无论编码如何）并为其分配权重，以便在不满足约束时将权重添加到可以代表适应性的总分中。

在这种情况下，您只需最小化适应度函数（因为最佳适应度可能为 0，这意味着满足所有约束）并让 GA 处理数字。

编码需要一些时间来弄清楚，但是一旦完成，它应该很简单，除非我遗漏了一些东西，当然:)