排課問題的本質是將課程、教師和學生在合適的時間段內分配到合適的教室中，涉及到的因素較多，是壹個多目標的調度問題，在運籌學中被稱為時間表問題（Timetable Problem，TTP）。設壹個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師壹個星期上k節課，在不考慮其他限制的情況下，能夠推出的可能組合就有 種，如此高的復雜度是目前計算機所無法承受的。因此眾多研究者提出了多種其他排課算法，如模擬退火，列表尋優搜索和約束滿意等。
Github ： /xiaochus/GeneticClassSchedule
遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是壹種通過模擬自然進化過程搜索最優解的方法。遺傳算法的流程如下所示：
遺傳算法首先針對待解決問題隨機生成壹組解，我們稱之為種群（Population）。種群中的每個個體都是問題的解，在優化的過程中，算法會計算整個種群的成本函數，從而得到壹個與種群相關的適應度的序列。如下圖所示：
為了得到新的下壹代種群，首先根據適應度對種群進行排序，從中挑選出最優的幾個個體加入下壹代種群，這壹個過程也被稱為精英選拔。新種群余下的部分通過對選拔出來的精英個體進行修改得到。
對種群進行修改的方法參考了生物DAN進化的方法，壹般使用兩種方法： 變異 和 交叉 。 變異 的做法是對種群做壹個微小的、隨機的改變。如果解的編碼方式是二進制，那麽就隨機選取壹個位置進行0和1的互相突變；如果解的編碼方式是十進制，那麽就隨機選取壹個位置進行隨機加減。 交叉 的做法是隨機從最優種群中選取兩個個體，以某個位置為交叉點合成壹個新的個體。
經過突變和交叉後我們得到新的種群（大小與上壹代種群壹致），對新種群重復重復上述過程，直到達到叠代次數（失敗）或者解的適應性達到我們的要求（成功），GA算法就結束了。
算法實現
首先定義壹個課程類，這個類包含了課程、班級、教師、教室、星期、時間幾個屬性，其中前三個是我們自定義的，後面三個是需要算法來優化的。
接下來定義cost函數，這個函數用來計算課表種群的沖突。當被測試課表沖突為0的時候，這個課表就是個符合規定的課表。沖突檢測遵循下面幾條規則：
使用遺傳算法進行優化的過程如下，與上壹節的流程圖過程相同。
init_population ：隨機初始化不同的種群。
mutate ：變異操作，隨機對 Schedule 對象中的某個可改變屬性在允許範圍內進行隨機加減。
crossover ：交叉操作，隨機對兩個對象交換不同位置的屬性。
evolution ：啟動GA算法進行優化。
實驗結果
下面定義了3個班，6種課程、教師和3個教室來對排課效果進行測試。
優化結果如下，叠代到第68次時，課程安排不存在任何沖突。
選擇1203班的課表進行可視化，如下所示，算法合理的安排了對應的課程。