基于遺傳算法完全學分制下排課系統模型的研究

侯若楠，范慶坤，張瀟元

隨著各大雙一流建設高校完全學分制改革的深入，以及師資力量的提升，未來各大雙一流建設高校能夠提供的課程種類、總數必將有所增長，學生跨專業選課的意愿也將有一定幅度的提高。因此如何在教學資源配置過程中進一步突出學生的學業需求成為各個高校雙一流建設中遇到的難點問題。為了解決這一難點，優化排課系統的算法必不可少。這是調度問題中關于排課問題的研究內容。研究方法是把師資力量、課程數量等相關教學資源按照有關約束條件放置在特定的教室和時間里面，目標是學生的選課組合數達到最大。因此本文通過對交叉和變異階段產生的個體采用蒙特卡洛概率接受的辦法，建立三維空間編碼的遺傳算法，即為構建出的排課系統算法模型。

1 問題分析及模型假設

從已有的研究來看，利用遺傳算法]1[求解排課問題，約束條件主要為避免班級、教室、課程、教室等排課要素之間發生沖突，有效利用各種資源，使排出的課表更加人性化，學生和老師的滿意度最高。本文假設師資力量和教室數目可以滿足所有開課需要，即排課問題中面臨的硬約束條件減少；但由于同一時間可以安排多門課程供學生自行選擇和一門課程下屬有許多子類別的影響，因此我們需要增設部分軟約束條件對算法進行優化。

2 排課系統數學模型的建立

經典遺傳算法具有早熟性，經過一定的迭代之后，種群的多樣性有所降低，從而導致算法過早地收斂，很可能只會獲得局部最優解。況且，在本文，已經假設教室數目和師資力量足以滿足所有開課需要，使得排課問題的硬約束條件有所減少，種群的基因多樣性有所降低。故本模型在遺傳算法的基礎上，結合排課所面臨的實際問題，采用時間、課程、起止周三維空間編碼的形式，并且對交叉和變異階段產生的個體采用蒙特卡洛概率接受的辦法，提高種群質量，避免求得局部最優解。

2.1 三維空間編碼排課系統的數學模型

變量描述：

三維空間編碼排課問題的數學模型變量定義為：

硬約束條件：

軟約束條件：

上述軟約束條件是為了在選課組合數基本最多的基礎下，對得到的方案進行進一步優化。

2.2 三維空間編碼排課基本流程

本模型中，排課是將課程按照一定約束條件安排在特定的時間中，得到選課組合數最多的方案。

排課的流程圖如圖1：

圖1 排課流程圖

2.3 具體編碼方案

在三維空間編碼排課問題的模型中，研究對象為不同類課程、不同子類課程、上課時間、課程起止周。課程子類所屬類別會隨課程子類確定。所以課程子類、上課時間、課程起止周可以作為三個不同的變量，分別對應三維坐標系中的X、Y、Z 軸。

圖2 三維空間染色體編碼方案[1]

從圖2 中可以看出，空間每個黑色小立方體表示一個個體基因，表示在第x1周第x2節可以選ci這門課這個事件。

具體編碼采用設計采用十進制編碼形式。

1）時間編碼。在中午兩節不安排課程和沒有特殊的三節課的假設下，每天上課分為1—2、3—4、7—8、9—10、11—12 五個時間段，可分別編碼為01、02、03、04、05。同樣的道理，周一到周五可同時編碼為01 07。將日期的編碼與節次編碼相連接，這樣每周具體的上課時間就會與一個唯一的編碼一一相應。例如0503 表示某課程在周五7～8節可選。

2）課程編碼。此課程集合C 中的i 值是所選課程的具體類別,為同一類課程不同子類別同樣分別編為相應的j 值，然后順次連接得到ij 這個編碼。例如：0015007 這個編碼表示這門課在某時間某周次可選。

3)課程起止周編碼。課程起止周編碼按照起始周與結束周的周序號進行連接即可。例如0108 表示該課程的起始周為第一周，在第八周結束。需說明的是，當課程編碼確定的時候，課程起止周的編碼是唯一確定的，即變量課程起止周依賴于變量課程序號的變化而變化的。

2.4 適應度函數設計

適應度函數是衡量一個個體好壞(一種課表好壞)程度的重要標準。本模型將重點從選課組合數最大對排課問題定義評價函數，同時加上其他一些必要的方面作為輔助評價。

1）選課組合數最大選課組合數的多少主要通過同一時間節次下，安排的同一類課程的不同子類數目；同一時間節次下，安排的不同類課程數目以及課表的空閑度來反映。即在課表的每一節次有適當種選擇的情況下，排列越分散，課表的選課沖突矛盾越小，最后得到的選課組合數越多。

2）課程間隔：根據實際情況，兩節相同的課程連在一起上是不合理的，所以需要設置一定的參數來衡量時間間隔的大小以并賦予一定的權重，作為評價函數中的次要影響因素。因此可得如下算法公式：

綜上所述，本模型的適應度評價函數 F 定義如下：