課程表組成的遺傳算法

Question

我正在爲自動化大學課程表編寫一個應用程序，並用於此遺傳算法。但現在我遇到了一些實現問題。

剛開始時我假設我們有1個時隙（時隙= 1小時）的持續時間類，我們可以簡單地把它放在數組中（表示時間表網格：一維數組的容量爲numberOfRoom * numberOfDays * numberOfTimeslots），並且可以執行突變和交叉以及沒有問題。

但知道我想改進應用程序，並允許有幾個時間段的持續時間類。這裏出現了很多問題：

我們怎樣才能把一個類對象放入一個數組中，並填充哪個類必須佔用的所有槽（幾個數組單元格）（一個對象 - 幾個單元格）？ 並且遵從我們如何將它放入數組中，可以如何執行變異和交叉操作？ 在此先感謝！我非常感謝你的幫助！

Answer 1

一個很好的規則可能只會跨越具有相同時隙的類。例如，你可以跨過一個需要兩個時隙的類，其中兩個類需要一個時隙。

表示具有多時隙的持續時間類，最簡單的，但取巧的辦法是有一個標誌，每個時間槽就會告訴你，如果該時隙是由一類新的或只是一個是開始的一類繼續佔據之前。當你越過時，你會看着那面旗幟，以確保你不會穿越課堂的一部分。

另一種（更好的）方法是創建更復雜的數據結構：DailyRoomOccupation。此數據結構將包含：

• 房間的日常容量，以時隙數表示;
• 一個（雙鏈接的）該房間當天排定的班級列表;
• 函數用於計算列表中的類是否適合時隙;
• 一個允許跨越兩個不同的DailyRoomOccupation的函數，負責僅跨越相等數量的時隙。