我正在考虑一个假设性问题,并寻求有关如何从算法角度解决该问题的指导。
问题:
考虑一所大学。您有以下对象:
- 教职员工。每位工作人员教授一篇或多篇论文。
- 学生。每个学生拿一篇或多篇论文。
- 房间。房间可容纳一定数量的学生,并包含特定类型的设备。
- 论文。需要某种类型的设备,每周需要一定的时间。
根据有关注册的信息(即每篇论文注册了多少学生,以及分配给每篇论文的教职员工),我如何计算遵守以下限制的时间表:
- 员工一次只能教授一件事。
- 学生一次只能参加一篇论文。
- 房间只能容纳一定数量的学生。
- 需要特定类型设备的论文只能在提供该类型设备的房间内举行。
- 工作时间为周一至周五、8 点至 12 点和 1 点至 5 点。
讨论:
实际上,我并不太关心上面概述的情况 - 这是我很好奇的一般问题类别。乍一看,在我看来,它很适合遗传算法,但这种算法的适应度函数会非常复杂。
尝试解决此类约束满足问题的好方法是什么?
我想可能没有办法完美地解决这个问题,因为学生很可能会把论文组合起来导致不可能的情况,尤其是随着学生和论文数量的增长。
最佳答案
继续使用遗传算法,我认为适应度函数不会非常复杂,恰恰相反。
您基本上只需检查每个约束(您只有 5 个)的候选解决方案(无论编码如何)并为它们分配权重,以便在不满足约束时将权重添加到总分中代表健身。
在这种情况下,您只需最小化适应度函数(因为可能的最佳适应度为 0,这意味着满足所有约束条件)并让 GA 处理数字。
编码需要花点功夫,但一旦完成,它应该很简单,除非我遗漏了什么,当然 :)
关于给定限制条件下计算时间表的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4800813/