基于遺傳算法的排課問題研究

吳 豐，萬 徑

（黃河水利職業(yè)技術(shù)學(xué)院，河南 開封 475004）

0 引言

2006 年，黃河水利職業(yè)技術(shù)學(xué)院（以下簡稱黃河水院）通過嚴(yán)格的評審程序，成為全國首批28 所國家示范性高等職業(yè)院校建設(shè)單位之一。 經(jīng)過3 年的不懈努力，于2009 年通過了驗收。 如今，學(xué)院已有兩個校區(qū)、14 個系（部）、3 個教學(xué)部和1 個成人教育學(xué)院，在校全日制?？粕?5 000 余人。 在學(xué)院借助示范性建設(shè)這一機遇快速發(fā)展期間，教學(xué)管理的理念和模式也在悄然轉(zhuǎn)變，其中教學(xué)信息化、管理科學(xué)化在提升學(xué)院管理水平方面發(fā)揮了不可替代的作用。

在進(jìn)行教學(xué)工作之前的排課工作是教學(xué)管理的重中之重，課表編排的合適與否，關(guān)系到教學(xué)能否正常運行，是最基本的保障。 排課工作的信息化程度也能夠從側(cè)面反映出高校的辦學(xué)實力、工作效率和教學(xué)質(zhì)量。

1 黃河水院排課問題分析

1.1 排課問題是組合規(guī)劃問題

課表指的是一張包含課程名、教師、上課地點和學(xué)時等信息的表，可以看做是這些信息的集合[1]。 課表編排則是嚴(yán)格依據(jù)教學(xué)計劃，在確保教師、學(xué)生、地點三者時空不沖突的基礎(chǔ)上，對所有要素進(jìn)行組合規(guī)劃，使得全校課表具有可實施性，并盡量滿足人性化要求。

排課問題是一個多目標(biāo)、有限資源、帶有模糊約束條件的組合規(guī)劃問題，而且是NP 完全的[2]。 多目標(biāo)意味著能夠解決課表問題的解有多種；有限資源是指高?？衫玫慕處煛⒔淌?、時間資源；模糊約束條件指的是從明確的教學(xué)計劃到明確的最終課表，而約束這一過程的條件卻是模糊的。

1.2 約束條件

基本硬約束、硬約束和軟約束是約束條件中的3 種類型[3]。

基本硬約束為：（1）在同一時間，同一學(xué)生不能上兩門不同的課；（2）在同一時間，同一教師不能教兩門不同的課程；（3）在同一時間，同一教室不能安排兩門不同課程。

硬約束為：（1） 按照最小單位兩節(jié)的形式上課；（2）實訓(xùn)課有自身的安排方式；（3）每門課程都有自己特定類型的教學(xué)資源；（4）教室必須足夠大，能夠容納上課的學(xué)生；（5）某些課程可以先行手工排定時間和教室；（6）某些教師、班級或教室在某個時間段可能不能夠利用。

軟約束為：（1）課程表的課程盡量分布均勻；（2）教師盡量不連續(xù)上課，并在上課時間上存在一定的喜好；（3）一周有多個課次的同一課程，兩次課之間應(yīng)當(dāng)有一定的時間間隔；（4）班級相鄰，上課地點盡可能距離較近。

2 遺傳算法設(shè)計

遺傳算法具有自適應(yīng)、 隨機搜索和高度并行的特殊功能，使用遺傳算法來近似求解排課這種帶有約束的多目標(biāo)優(yōu)化組合問題，具有實際意義[4]。

2.1 基因編碼

把一個三維立體的空間作為編碼方案的出發(fā)點，將教師、教室、班級、時間和課程這5 個元素進(jìn)行合理劃分，通過三維空間中的坐標(biāo)來進(jìn)行編碼。 假設(shè)這5 個元素為1 個5 元組，即：課程集合Subject=｛s1，s2，s3，…，sn｝；教師集合Teacher=｛t1，t2，t3，…，tn｝；班級集合Class=｛c1，c2，c3， …，cn｝； 時間集合Hour=｛h1，h2，h3，…，hn｝；教室集合Room=｛r1，r2，r3，…，rn｝。

在此5 元組中，由于課程、班級和教師已經(jīng)在各系部錄入教學(xué)計劃任務(wù)的時候確定，所以將此3 元素捆綁在一起進(jìn)行考慮，并叫做班級元組。 下面構(gòu)造一個三維立體空間作為種群個體的模型，如圖1所示。

親子談話是家庭中父母與子女間信息、觀點、情感和態(tài)度的交流，以達(dá)到相互了解、信任與合作的過程(王爭艷，劉紅云，雷靂，張雷，2002)。同時，親子談話也是傳遞父母的信仰及信念的重要方式(Boyatzis et al., 2006)，實現(xiàn)家庭教育功能的途徑之一(鄧林園, 武永新, 孔榮, 方曉義, 2014; 房超, 方曉義, 2003)。因此，父母的來生信念可能會通過親子談話影響兒童對死亡和來世信念的理解，其中的關(guān)系及其作用機制仍值得進(jìn)一步探討。

圖1 三維立體個體模型Fig.1 Three-dimensional individual model

圖中，H 坐標(biāo)軸代表的是時間段，即從周一至周五，每2 小節(jié)為1 個時間段，1d 有4 個時間段，每周共計20 個時間段（H1~H20）。 R 坐標(biāo)軸代表的是教室資源（R1~Rn，n 代表學(xué)校擁有教室的總數(shù)量）。 C 坐標(biāo)軸代表的是班級元組。 這樣，三維空間中的某個坐標(biāo)就對應(yīng)為某個班級的一門課程安排， 這里稱為一個“基因”。 通過這種三維立體的個體模型將已知元素捆綁在一起考慮，此外只需要考慮時間要素和教室要素，減輕了編碼的復(fù)雜程度。

2.2 基因編碼

種群的生成是由計算機隨機生成一個小于全校開課總?cè)蝿?wù)數(shù)的隨機整數(shù)， 然后從此整數(shù)開始，為每個開課任務(wù)分配上課的教室和上課時間，即可構(gòu)成初始種群。 但是，這種隨機生成種群的方法有可能引起種群個體在空間內(nèi)分布不均，使得初始種群不能夠代表整體種群的信息。 為解決這個問題，可以事先劃分出多個子空間，在每個子空間中先各自產(chǎn)生自己的初始種群，然后再將這些初始種群匯總起來。 這樣，構(gòu)建的初始種群信息就相對均勻了一些，整體均勻性從而可以得到有效改善。

2.3 構(gòu)造適應(yīng)度函數(shù)

由于各個學(xué)校的實際情況不同，導(dǎo)致軟約束條件不同，進(jìn)而量化的方法也不盡相同。這里從3 個方面定義期望度值（課程離散度、黃金時段度、教師滿意度），并將這3 個期望度值合理組合，構(gòu)造適應(yīng)度函數(shù)。

（1）課程離散度。 用全校所有班級大于“2 學(xué)時/周”的課程離散度期望值的平均值來衡量班級課程組合的優(yōu)劣程度，即：

式中：di表示課程離散度期望值；n 代表全校所有班級大于“2 學(xué)時/周”的課程的總數(shù)。

（2）黃金時段度。 用全校黃金時段平均值來衡量每節(jié)課安排的優(yōu)劣程度，即對所有開課計劃的黃金時段期望值進(jìn)行累加，再除以開課總數(shù)，即：

式中：hi代表課次的黃金時間期望值；n 代表總的開課數(shù)；為黃金時段度，其值越大，表明排課方案在周課表中的安排越好。

（3）教師滿意度。 教師對課表的滿意度用α1=1（滿意）、α2=0.5（一般）和α3=0（不滿意）表示，對應(yīng)的滿意與否的節(jié)數(shù)用β1、β2和β3表示。 這樣，即可用公式（3）間接衡量教師的意愿，將θi累計再除以總體教師的個數(shù)，就是全體教師的滿意度。

（4）適應(yīng)度函數(shù)。 通過以上描述，適應(yīng)度函數(shù)Fn可以構(gòu)造為

這里λ1、λ2和λ3分別代表各期望值在總期望值中的權(quán)重。 該權(quán)重可以根據(jù)學(xué)院實際需求，由教務(wù)員自行設(shè)定。

2.4 設(shè)計選擇遺傳算子

這里采用輪盤賭選擇法，其數(shù)學(xué)表達(dá)式為

式中：m 為群體大小；Fn為個體n 的適應(yīng)度；Pn為遺傳到下一代種群的概率。

具體做法是：為群體中所有個體都計算出適應(yīng)度值，然后使用公式（5）計算每個個體被遺傳到下一代種群中的概率，最后模擬輪盤賭操作，隨機生成0至1 之間的隨機數(shù)，與之前計算出的每個個體的概率進(jìn)行匹配，確定某些個體是否被遺傳到下一代種群中。

2.5 設(shè)計交叉遺傳算子

這里采用的是單點交叉。 在進(jìn)行交叉前，將眾多排課方案按照“班級元組-時間-教室”的順序排列下去，目的是將個體相互對應(yīng)。 在交叉過程中，只需交叉對應(yīng)班級元組的上課時間和所在教室即可。

2.6 設(shè)計變異遺傳算子

個體變量的變異概率Pm不僅是產(chǎn)生新個體的輔助方法，而且還能對種群多樣性起到保持作用，能夠防止出現(xiàn)非成熟性的收斂。其值不能太大，如果取值大于0.5，遺傳算法就變?yōu)殡S機搜索，從而使得遺傳算法的數(shù)學(xué)特性和搜索功能不復(fù)存在。變異算法為：

（1） 在種群中隨機選取個體的時間基因或教室基因。

（2）將此基因隨機跳轉(zhuǎn)為其他時間或教室。

（3）檢測沖突。 如果檢測到?jīng)_突，則再次跳轉(zhuǎn)到其他時間或教室，并再次檢測；如果沒有發(fā)現(xiàn)沖突，則結(jié)束。

2.7 檢測沖突

以三維立體空間編碼方法為基礎(chǔ)，將班級作為縱軸，將時間段作為橫軸，再將課表的其他3 元素按“課程-教師-教室”的順序排列，放置在由班級和時間段組成的二維坐標(biāo)中。 通過這種二維坐標(biāo)模型，只需根據(jù)硬約束條件對每個縱坐標(biāo)中的課程、 教師和教室3 個元素進(jìn)行檢測，即可檢測出沖突。

3 結(jié)語

通過實際的測試可以發(fā)現(xiàn)，適應(yīng)度函數(shù)的值在較短的時間內(nèi)收斂于“最優(yōu)解”附近，其變化呈現(xiàn)出先劇烈后平緩趨勢。 這充分驗證了遺傳算法中適應(yīng)度函數(shù)的進(jìn)化特征?？偟膩碚f，該算法在解決實際問題時取得了良好的效果，排課結(jié)果符合預(yù)期設(shè)計的目的。

[1] 騰姿,鄧輝文,楊久俊. 基于遺傳算法的排課系統(tǒng)的設(shè)計與實現(xiàn)[J]. 計算機應(yīng)用,2007(27):199-201.

[2] 張海濤. 高等學(xué)校計算機排調(diào)課專家系統(tǒng)研究[D]. 阜新：遼寧工程技術(shù)大學(xué)，2005:48-49.

[3] 閻威. 排課系統(tǒng)中遺傳算法的應(yīng)用[J]. 內(nèi)江科技,2008(3):3.

[4] 王小平,曹立明. 遺傳算法：理論、應(yīng)用與軟件實現(xiàn)[M]. 西安交通大學(xué)出版社,2002:9.