基于差分算法的高校排課系統的優化與實現

余彬　丁銳

【摘 要】差分算法借鑒優化選擇和差分機制，使用搜索技術，根據學生的學習進度情況，合理配置教學資源，對教學安排工作進行優化調整。高校調課涉及到學生學習基礎、教室容量、教學硬件設施配備、班級人數、教師要求和上課時間六方面相互關聯的因素。通過對差分算法進行優化改進，調整參數設置，對教學資源合理化使用有著比較顯著的作用。

【關鍵詞】差分算法；排課問題；優化條件

0 引言

目前差分基因算法的排課研究已經進行有一段時間了，大多是基于優化選擇和進化機制發展起來的自適應隨機搜索算法，但是對于約束條件存在漏洞。排課工作是一項教學服務性的工作，隨著教育的發展，人性化服務顯得越來越重要。之前的排課系統沒有考慮到每個學校教學資源的硬件配備和時空距離。隨著教育信息技術的發展，大多數高等院校都已實現了多媒體教室全覆蓋化，軟件集中管控化。以往的排課系統往往不能夠滿足這些方面的需要。比如，大學校園教學樓之間的距離較遠，課間休息時間較短，如果排課出現問題，在上課之前，老師和學生都很難抵達教室；在正常的教學過程中，很多課程是相互之間致命不可分的，有時候會因為老師調課學生請假，從而影響其他科目的教學進度。

本研究對差分算法進行了特定模擬參數設置以適應排課問題。根據參數設置，課程之間的關聯性、教師的時間分配、上課教室的位置關系作為主要優化參數，根據差分算法思想對調課算法設計，其過程如下：

（1）數據初始化：搜索教室，教師，班級等主要參數，對任務進行排序；

（2）根據人物排列順序，檢測查分選項中，教師時間安排、上課地點、班級信息進行自適應度評估；

（3）如果不存在沖突，則選擇差分項較小的教室號來進行排課；如果存在沖突，則跳過此任務繼續進行，并保留任務號；

（4）按照選擇算法部分的教室，進行差分優化；

（5）重新搜尋保留的任務號，自動生成優化區間，完成排課。

1 主要算法實現

1.1 數據收集和差分

數據收集函數完成以下功能：

1）定義任務序列，并設置課程信息、教師信息、學生信息、上課條件為基本參數；

2）對于任務進行排序，生成任務的擴展信息EXInfo；

3）對任務內容進行搜索優化，生成課程項EXItem；

4）設置系統信息鎖定狀態解鎖。

數據差分函數完成以下功能：

1）如果任務序列有未處理的數據，則判斷是否鎖定；如果沒有鎖定，則跳出函數；

2）刪除序列中的上課項EXItem、課程擴展信息EXInfo、條件設定EXRule；

3）刪除教師、班級、科目以及學生信息；

4）設置系統狀態復位。

1.2 安排課程項

課程上的安排是本次任務的關鍵所在，他負責將相鄰的時間序列中將空余教室號差值最小的信息優先安排，教室容量和相鄰時間段的判斷由其他參數判定，本算法主要完成任務序列的選取。

function Arrange EX Item （select AEX Item： PEX Item） ： Boolean；

while FEX Arrange do

{

If （not Time T Allow） or （not Room R Allow） then Continue

If FEX Arrange null then Add Time T ID， Room R ID to T R N

} then Result

Result： =Count （EX R T N）

If Result NULL

{

X ： =Random （Count（E X R T N））；

If AEX Item. Time ID=N-1 then F Arrange （A Item）：=null

NULL Arrange [EXRT[X]]：=AEX Item N escape

}

function End

1.3 對于已知任務號進行差分優化

優化模型是應用差分算法的核心，也是優化排課是否成功的關鍵。在任務項序列當中，設定任務序列N、時間序列T、教師序列I、班級序列C、上課地點R為基本參數，N為序列號每安排一項任務N=N+1，當T和I為固定值時候，計算C序列和R序列差值參數P1；當T和C為固定值時候，計算I序列和R序列差值參數P2；當T和R為固定值時候，計算C序列和I序列差值參數P3；以此類推，得出參數P4、P5、P6。然后計算，P1、P2、P3、P4、P5、P6之間的差值，將差值最小的參數PN設定為最佳配置，然后進行下一條任務。通過測試證明這種優化改進的差分算法是經過多種算法數據分析后決定的，效率比較高，參數設置簡單，置換性較強，優化操作也可針對有部分課程信息項進行。

1.4 排課結果進行調查分析

排課完成后需要對結果進行檢測并給出檢測結果。教師和學生的調課率，作為排課結果的認證標準。通過調查證明，這種排課方法調課率較低，成功率較高，安排的課程，比較合理。

2 結束語

本文在差分算法的基礎上進行了部分改動，靈活的設置了排課參數，將排課的合理性和調課率聯系起來，為今后此類型的研究提供一定的理論基礎。隨著信息化的發展和大數據的應用，此差分算法可增加參數設定，具有較好的延展性和前瞻性。

【參考文獻】

[1]李銳.高校排課系統算法的研究與實現[D].吉林大學，2010.

[2]熊衛衛.高校排課系統算法設計與實現[D].吉林大學，2004.

[3]商凌霞.高校排課系統的設計與實現[D].浙江工業大學，2012.

[4]齊萍.基于蟻群算法的高校排課系統優化策略[J].湖北工業大學學報，2010，02：68-69+78.

[5]林瑞金，卓清寅.基于遺傳算法的高校排課系統設計與實現[J].荊楚理工學院學報，2010，09：27-29.

[責任編輯：湯靜]