遗传算法用于课程表编排

Question

我正在开发一款用于自动生成大学课程表的应用程序，并使用遗传算法来实现。但目前我面临一些实现上的问题。

一开始，我假设每个课程只占用一个时间段（时间段为1小时），可以将其放入一个数组中（该数组表示课程表网格：具有numberOfRooms * numberOfDays * numberOfTimeSlots容量的一维数组），并且可以进行变异和交叉等操作，没有问题。

但是，现在我想改进这个应用程序，并允许课程占用多个时间段。这里涉及到很多问题：

我们如何将一个课程对象放入数组中，并填充所有课程必须占用的时间段（即一个对象 - 多个单元格）？ 根据我们如何将其放入数组中的规定，变异和交叉操作如何执行？ 提前感谢您的帮助！我非常感激！

- mr.nothing

Answer 1

一个好的规则是只交叉那些有相等时间段的课程。例如，你可以交叉一个占用两个时间段的课程和两个占用一个时间段的课程。

为了表示持续多个时间段的课程，最简单但也很棘手的方法是设置一个标志，对于每个时间段，它会告诉你这个时间段是否被新课程占用，还是仅仅是之前已经开始的课程的延续。当你进行交叉时，你需要观察这个标志，以确保你不会交叉课程的部分。

另一种（更好的）方法是创建一个更复杂的数据结构：DailyRoomOccupation。这个数据结构将包含：

- 房间每天的容量，以时间段数表示； - 在该房间安排的课程（双向）链表； - 一个计算列表中的课程是否适合在时间段内的函数； - 一个允许交叉两个不同的DailyRoomOccupation的函数，注意只交叉相等数量的时间段。

- Vitaly Olegovitch

---

嗯，我不确定仅交叉持续时间相等的类是一个好主意，因为在我们要交叉的区域中，父母双方都可能没有这样持续时间的课程。 所以，在DailyRoomOccupation结构的想法中，您建议存储填充有DailyRoomOccupation对象的列表（大小为房间数量），这些对象又安排了房间的课程，对吗？那么，如果我们要执行交叉和变异，您能否解释一下如何进行呢？ - mr.nothing

如果我们对DailyRoomOccupation执行这些运算符，那么我们将无法使用这些运算符重新排列对象内的类；如果我们对DailyRoomOccupation中的类执行运算符，则会遇到我在一开始描述的问题。 - mr.nothing