基于差分算法的高校排課系統(tǒng)的優(yōu)化與實(shí)現(xiàn)

余彬　丁銳

【摘 要】差分算法借鑒優(yōu)化選擇和差分機(jī)制，使用搜索技術(shù)，根據(jù)學(xué)生的學(xué)習(xí)進(jìn)度情況，合理配置教學(xué)資源，對(duì)教學(xué)安排工作進(jìn)行優(yōu)化調(diào)整。高校調(diào)課涉及到學(xué)生學(xué)習(xí)基礎(chǔ)、教室容量、教學(xué)硬件設(shè)施配備、班級(jí)人數(shù)、教師要求和上課時(shí)間六方面相互關(guān)聯(lián)的因素。通過對(duì)差分算法進(jìn)行優(yōu)化改進(jìn)，調(diào)整參數(shù)設(shè)置，對(duì)教學(xué)資源合理化使用有著比較顯著的作用。

【關(guān)鍵詞】差分算法；排課問題；優(yōu)化條件

0 引言

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

本研究對(duì)差分算法進(jìn)行了特定模擬參數(shù)設(shè)置以適應(yīng)排課問題。根據(jù)參數(shù)設(shè)置，課程之間的關(guān)聯(lián)性、教師的時(shí)間分配、上課教室的位置關(guān)系作為主要優(yōu)化參數(shù)，根據(jù)差分算法思想對(duì)調(diào)課算法設(shè)計(jì)，其過程如下：

（1）數(shù)據(jù)初始化：搜索教室，教師，班級(jí)等主要參數(shù)，對(duì)任務(wù)進(jìn)行排序；

（2）根據(jù)人物排列順序，檢測(cè)查分選項(xiàng)中，教師時(shí)間安排、上課地點(diǎn)、班級(jí)信息進(jìn)行自適應(yīng)度評(píng)估；

（3）如果不存在沖突，則選擇差分項(xiàng)較小的教室號(hào)來進(jìn)行排課；如果存在沖突，則跳過此任務(wù)繼續(xù)進(jìn)行，并保留任務(wù)號(hào)；

（4）按照選擇算法部分的教室，進(jìn)行差分優(yōu)化；

（5）重新搜尋保留的任務(wù)號(hào)，自動(dòng)生成優(yōu)化區(qū)間，完成排課。

1 主要算法實(shí)現(xiàn)

1.1 數(shù)據(jù)收集和差分

數(shù)據(jù)收集函數(shù)完成以下功能：

1）定義任務(wù)序列，并設(shè)置課程信息、教師信息、學(xué)生信息、上課條件為基本參數(shù)；

2）對(duì)于任務(wù)進(jìn)行排序，生成任務(wù)的擴(kuò)展信息EXInfo；

3）對(duì)任務(wù)內(nèi)容進(jìn)行搜索優(yōu)化，生成課程項(xiàng)EXItem；

4）設(shè)置系統(tǒng)信息鎖定狀態(tài)解鎖。

數(shù)據(jù)差分函數(shù)完成以下功能：

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

2）刪除序列中的上課項(xiàng)EXItem、課程擴(kuò)展信息EXInfo、條件設(shè)定EXRule；

3）刪除教師、班級(jí)、科目以及學(xué)生信息；

4）設(shè)置系統(tǒng)狀態(tài)復(fù)位。

1.2 安排課程項(xiàng)

課程上的安排是本次任務(wù)的關(guān)鍵所在，他負(fù)責(zé)將相鄰的時(shí)間序列中將空余教室號(hào)差值最小的信息優(yōu)先安排，教室容量和相鄰時(shí)間段的判斷由其他參數(shù)判定，本算法主要完成任務(wù)序列的選取。

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 對(duì)于已知任務(wù)號(hào)進(jìn)行差分優(yōu)化

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

1.4 排課結(jié)果進(jìn)行調(diào)查分析

排課完成后需要對(duì)結(jié)果進(jìn)行檢測(cè)并給出檢測(cè)結(jié)果。教師和學(xué)生的調(diào)課率，作為排課結(jié)果的認(rèn)證標(biāo)準(zhǔn)。通過調(diào)查證明，這種排課方法調(diào)課率較低，成功率較高，安排的課程，比較合理。

2 結(jié)束語

本文在差分算法的基礎(chǔ)上進(jìn)行了部分改動(dòng)，靈活的設(shè)置了排課參數(shù)，將排課的合理性和調(diào)課率聯(lián)系起來，為今后此類型的研究提供一定的理論基礎(chǔ)。隨著信息化的發(fā)展和大數(shù)據(jù)的應(yīng)用，此差分算法可增加參數(shù)設(shè)定，具有較好的延展性和前瞻性。

【參考文獻(xiàn)】

[1]李銳.高校排課系統(tǒng)算法的研究與實(shí)現(xiàn)[D].吉林大學(xué)，2010.

[2]熊衛(wèi)衛(wèi).高校排課系統(tǒng)算法設(shè)計(jì)與實(shí)現(xiàn)[D].吉林大學(xué)，2004.

[3]商凌霞.高校排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].浙江工業(yè)大學(xué)，2012.

[4]齊萍.基于蟻群算法的高校排課系統(tǒng)優(yōu)化策略[J].湖北工業(yè)大學(xué)學(xué)報(bào)，2010，02：68-69+78.

[5]林瑞金，卓清寅.基于遺傳算法的高校排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].荊楚理工學(xué)院學(xué)報(bào)，2010，09：27-29.

[責(zé)任編輯：湯靜]