李承敬

摘 要：文章針對(duì)高職排課系統(tǒng)中精度搜索效率較差的問(wèn)題，通過(guò)對(duì)排課系統(tǒng)中6個(gè)關(guān)鍵屬性和屬性間的約束的分析，建立了排課系統(tǒng)模型和屬性約束模型，基于該模型在高職排課系統(tǒng)中采用啟發(fā)式模擬退火搜索算法進(jìn)行排課，最后通過(guò)實(shí)驗(yàn)仿真，驗(yàn)證了SA算法在排課系統(tǒng)中的有效性，可以得到近似最優(yōu)解。

關(guān)鍵詞：模擬退火算法；排課系統(tǒng)；啟發(fā)式搜索

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1673-8454（2014）12-0084-03

一、引言

隨著教育和技術(shù)的深度融合，高職教育中教務(wù)管理也經(jīng)歷了手工、計(jì)算機(jī)輔助、信息系統(tǒng)自動(dòng)管理三個(gè)階段，其中排課問(wèn)題的求解更是體現(xiàn)了信息技術(shù)在高職教務(wù)管理中的優(yōu)勢(shì)。[1]教務(wù)排課問(wèn)題是教學(xué)計(jì)劃安排和教學(xué)過(guò)程管理的保證，研究人員對(duì)排課問(wèn)題的研究由來(lái)已久，該項(xiàng)研究具有較高的理論和現(xiàn)實(shí)意義。[2-3]

上世紀(jì)70年代，Cooper等從計(jì)算復(fù)雜性的角度證明了排課問(wèn)題是NP完全問(wèn)題，說(shuō)明排課問(wèn)題可以通過(guò)建立問(wèn)題的數(shù)學(xué)模型找到問(wèn)題的近似最優(yōu)解。[4]NP完全問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)判定給定結(jié)果是否正確，可以通過(guò)精確搜索和啟發(fā)式搜索來(lái)求近似解，精確搜索過(guò)程中，計(jì)算復(fù)雜性呈指數(shù)增長(zhǎng)，對(duì)中間結(jié)果沒(méi)有充分利用，存在盲目性，不利于解決大型問(wèn)題，此方法適用于小規(guī)模的搜索問(wèn)題。啟發(fā)式搜索對(duì)中間搜索位置進(jìn)行評(píng)估，根據(jù)評(píng)價(jià)函數(shù)，在較好的位置再進(jìn)行搜索，求得近似最優(yōu)解，此方法可以用于排課算法等大規(guī)模搜索問(wèn)題的解決，常用的啟發(fā)式搜索方法有蟻群算法、遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、免疫算法等。[5]

模擬退火算法（Simulated annealing SA）是針對(duì)組合優(yōu)化問(wèn)題，采用迭代求解的思路，隨機(jī)進(jìn)行尋優(yōu)的一種通用概率啟發(fā)式算法，適用于較大空間的搜索問(wèn)題，在多項(xiàng)式時(shí)間內(nèi)期望找到全局最優(yōu)解或最優(yōu)近似解，排課算法是典型的大空間組合優(yōu)化問(wèn)題，因此可以在排課算法中采用模擬退火SA算法。[6]

排課算法其實(shí)質(zhì)是一個(gè)周期時(shí)間內(nèi)，關(guān)鍵屬性（教師、班級(jí)、課程、教室、課時(shí)段）滿足一定的約束條件、使得排課時(shí)間分布合理，并一定程度上達(dá)到近似最優(yōu)解。[7]在排課過(guò)程中為了避免屬性之間沖突，同時(shí)兼顧教學(xué)過(guò)程的合理性和師生的上課效率，還需要根據(jù)教務(wù)實(shí)際情況設(shè)置一些排課附加條件。本文主要采用模擬退火的方法對(duì)高職排課系統(tǒng)中的排課算法進(jìn)行多目標(biāo)的優(yōu)化，尋求較優(yōu)的解決方法，下面從排課系統(tǒng)相關(guān)概念、系統(tǒng)模型、模擬退火算法、系統(tǒng)實(shí)現(xiàn)四個(gè)方面進(jìn)行分析。

二、相關(guān)概念

排課問(wèn)題是一個(gè)涉及多屬性約束組合優(yōu)化的問(wèn)題，其中涉及到的關(guān)鍵屬性包括校區(qū)、時(shí)段、教室、教師、學(xué)生、課程等6個(gè)方面。通過(guò)合理安排屬性，滿足約束條件是排課問(wèn)題的關(guān)鍵。

校區(qū)屬性是學(xué)校在地理位置上不同分布的區(qū)域，由于空間跨度大，是排課首要考慮的關(guān)鍵屬性，校區(qū)用代碼進(jìn)行區(qū)分。

時(shí)段屬性在排課過(guò)程中涉及周、天、天時(shí)段三個(gè)屬性組成，周分為單周和雙周，天分為5個(gè)工作日，天時(shí)段包括上午5個(gè)時(shí)段，下午4個(gè)時(shí)段，晚上3個(gè)時(shí)段。

教室屬性是上課的地點(diǎn)，主要包括教室類型、教室容量、所在教學(xué)樓等信息。教室類型主要包括普通教室、多媒體教室、機(jī)房、體育館、琴房、畫(huà)室、報(bào)告廳等多種類型，排課過(guò)程中，教室屬性首要滿足教室類型，在功能上吻合，其次上課人數(shù)要不大于教室的容量，也不宜選擇容量過(guò)大的教室，浪費(fèi)教學(xué)資源。在相連課程的教室的選擇上，兼顧教室所在教學(xué)樓的距離，盡量減少學(xué)生的奔波。

學(xué)生屬性對(duì)于排課系統(tǒng)是一個(gè)邏輯概念，由上同一門(mén)課程的學(xué)生組成的集合，學(xué)生來(lái)源可以是同一個(gè)行政班、多個(gè)行政班或者多個(gè)行政班的部分學(xué)生，如公共課，學(xué)生來(lái)自多個(gè)專業(yè)不同的班級(jí)，基礎(chǔ)課一般是同一專業(yè)的不同班級(jí)，專業(yè)課一般是同一專業(yè)的同一個(gè)班級(jí)。排課根據(jù)學(xué)生屬性的限制條件多少，確定排課的優(yōu)先級(jí)，先對(duì)限制條件多的學(xué)生屬性優(yōu)先排課。

教師屬性主要包括專業(yè)課教師、基礎(chǔ)課教師、外聘教師，對(duì)于外聘教師在排課時(shí)要考慮校區(qū)距離的因素，優(yōu)先安排。

課程屬性在教務(wù)系統(tǒng)中主要分為掛牌課、公共課、專業(yè)基礎(chǔ)課、專業(yè)課。掛牌課是由知名教授主講面向全校學(xué)生開(kāi)設(shè)的公共課程，該類課程具有知名度高、選修學(xué)生多、跨校區(qū)和專業(yè)性強(qiáng)等特點(diǎn)。 公共課是面向全校各專業(yè)開(kāi)設(shè)，通常是必修的與學(xué)位掛鉤的課程，對(duì)于學(xué)生來(lái)說(shuō)較為重要，如計(jì)算機(jī)基礎(chǔ)、大學(xué)英語(yǔ)等，該類課程具有跨校區(qū)和專業(yè)，教師學(xué)生數(shù)量較多，通常存在合班上課，對(duì)上課時(shí)間和教學(xué)地點(diǎn)座位數(shù)量要求較高，因此此類課程應(yīng)該優(yōu)先處理。專業(yè)基礎(chǔ)課是針對(duì)各個(gè)專業(yè)開(kāi)設(shè)的本專業(yè)的重要課程，為專業(yè)的教學(xué)做好理論知識(shí)準(zhǔn)備，該類課程主要面向特定專業(yè)，對(duì)教學(xué)地點(diǎn)限制較多，如語(yǔ)音室、琴房、舞蹈房、機(jī)房等。專業(yè)課是面向較小規(guī)模的師生，在排課系統(tǒng)中優(yōu)先級(jí)較低，與其他屬性沖突時(shí)，可以安排在特殊時(shí)間點(diǎn)，如晚間10-12課時(shí)段。

排課算法中約束主要包括下面幾種情況：

1.常規(guī)約束

常規(guī)約束是排課算法中必須要滿足的約束條件，如同一課時(shí)段、同一教室只能安排一個(gè)教師，一個(gè)學(xué)生集合最多一個(gè)課程。

2.附加約束

根據(jù)排課算法的相關(guān)屬性，附加約束是根據(jù)教務(wù)要求，人為附加的約束條件，主要包括對(duì)教師、學(xué)生、教室、課程的排他約束，以及對(duì)課程密度的約束。

排他約束如教師張三在每周三課時(shí)段6-9不安排課程，工商管理二班第5-6周異地實(shí)習(xí)，實(shí)驗(yàn)樓第一階梯教室第2周維修，不安排課程，數(shù)據(jù)庫(kù)原理第15周要安排在機(jī)房做課程設(shè)計(jì)。

課程密度約束，如學(xué)生每天課時(shí)數(shù)限制，每周課時(shí)數(shù)限制，教師每天最多課時(shí)數(shù)限制，以及教師、學(xué)生連續(xù)課時(shí)數(shù)限制，保證教學(xué)的質(zhì)量和師生的合理作息。

3.組合屬性約束

組合約束是在常規(guī)約束和附件約束的基礎(chǔ)上，進(jìn)行合理的約束條件組合，產(chǎn)生更加細(xì)的約束條件，如課程動(dòng)畫(huà)設(shè)計(jì)第16周安排在Apple機(jī)房進(jìn)行課程設(shè)計(jì)。在排課系統(tǒng)中優(yōu)先滿足組合屬性約束。

三、排課系統(tǒng)模型

在排課系統(tǒng)模型中，假設(shè)課程的排課周期為一周，那么排課問(wèn)題可以描述為在一個(gè)學(xué)習(xí)周期內(nèi)W={w1，w2……wj}j

課程ci的任課教師表示為tea(ci)，學(xué)生集合表示為stuset(ci)，某課時(shí)段內(nèi)是否安排該課程表示為assign(ci,tdp)∈[0.1]。排課系統(tǒng)模型就是求解滿足約束條件的解的集合S={s1，s2…si}，si=(ci，tdp，ri)。

根據(jù)第二節(jié)描述，排課約束條件可以分為常規(guī)約束、附加約束、組合約束。約束條件可以采用如下方式進(jìn)行描述：

Constraints1：排課系統(tǒng)完成所有課程的編排

?ci，?（ci，tdp，ri)∈S

Constraints2：同一課時(shí)段，同一教室，有且僅有一門(mén)課程

?(ci，tdp，ri)，(ci，tdp，ri)∈S，(ci=ci′）∧（tdp=tdp′）∧（ri=ri′）

Constraints3：同一課時(shí)段，不同的課程，教師和學(xué)生不能重復(fù)

?(ci，tdp，ri)，(ci，tdp，ri)∈S，sea(ci）≠tea(ci′)∧stuset(ci)∧stuset(ci′)

Constraints4：教師某課時(shí)段不安排課程

?(ci∈sea(ci）,assign(ci，tdp)=0,(ci，tdp，ri)∈S

四、模擬退火算法

模擬退火算法（Simulated Annealing，SA）包括產(chǎn)生函數(shù)、評(píng)價(jià)函數(shù)、冷卻策略、穩(wěn)定準(zhǔn)則、退火結(jié)束標(biāo)準(zhǔn)。SA算法初始化較高的溫度，采用Metropolis抽樣策略，在一定領(lǐng)域范圍內(nèi)進(jìn)行搜索，不斷重復(fù)抽樣進(jìn)行迭代，判斷是否滿足退火結(jié)束標(biāo)準(zhǔn)，尋找目標(biāo)函數(shù)的全局最優(yōu)解。為了形式化描述SA算法，定義J(x)狀態(tài)時(shí)的評(píng)價(jià)函數(shù)值，Xi表示時(shí)刻的狀態(tài)，T系統(tǒng)初始化的溫度，Tmin表示退火結(jié)束標(biāo)準(zhǔn)，溫度的下限，a(a∈(0.1))表示冷卻策略，a越大降溫越慢，a越小降溫越快。

SA算法流程形式化描述如下：

init(T)

while(t>Tmin){

tmp=J(Xi+1)-j(Xi)

if(tmp≥0）

J（Xi+1)=J(Xi)

else if (exp()>random(0,1))

J(Xi+1)=J(Xi)

T=a*T

i++}

對(duì)于SA算法中的冷卻策略a(a∈(0.1))，滿足非線性公式 ai=（i=1,2……K），使得溫度降低不至于過(guò)快，而陷入局部最優(yōu)，也不至于降低過(guò)慢，影響算法的性能。

通過(guò)對(duì)SA算法描述進(jìn)行分析，不難發(fā)現(xiàn)SA算法從初始化溫度開(kāi)始，對(duì)約束條件均勻的要求，求解效果較好，收斂速度快?？刂茀?shù)的選擇較難，對(duì)算法結(jié)果影響較大，還要在降溫策略和評(píng)價(jià)函數(shù)進(jìn)行多次仿真測(cè)試。

五、系統(tǒng)實(shí)現(xiàn)

為了驗(yàn)證模擬退火SA算法在排課系統(tǒng)的應(yīng)用，采用Microsoft C#實(shí)現(xiàn)基于標(biāo)準(zhǔn)鄰域的SA算法的排課系統(tǒng)，其系統(tǒng)工作流程如圖1所示。

測(cè)試過(guò)程中，選取電子商務(wù)專業(yè)25位教師、40門(mén)課程對(duì)排課系統(tǒng)進(jìn)行仿真測(cè)試，每個(gè)實(shí)例運(yùn)行50次，經(jīng)過(guò)測(cè)試，初始化參數(shù)T設(shè)置為38.6，降溫參數(shù)a(a∈(0.1))設(shè)置為，a=0.98,Tmin=23.87。測(cè)試結(jié)果表明基于模擬退火SA算法的排課系統(tǒng)是有效的，可以便捷的得到相對(duì)最優(yōu)解。

本文針對(duì)高職排課系統(tǒng)中精度搜索效率較差的問(wèn)題，通過(guò)對(duì)排課系統(tǒng)中6個(gè)關(guān)鍵屬性和屬性間的約束的分析，建立了排課系統(tǒng)模型和屬性約束模型，基于該模型在高職排課系統(tǒng)中采用啟發(fā)式模擬退火搜索算法進(jìn)行排課，最后通過(guò)實(shí)驗(yàn)仿真，驗(yàn)證了SA算法在排課系統(tǒng)中的有效性，可以得到近似最優(yōu)解。

參考文獻(xiàn)：

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

[2]譚保華,彭偉.基于蟻群遺傳算法的高校排課系統(tǒng)[J].計(jì)算機(jī)仿真,2008（12）:294-297.

[3]蘇明杰,陳建勛.基于線性規(guī)劃模型的高校排課系統(tǒng)[J].微計(jì)算機(jī)信息,2011（8）:197-200.

[4]宗薇.高校智能排課系統(tǒng)算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)仿真,2011（12）:389-392.

[5]于娟,尹積棟.面向排課系統(tǒng)的遺傳算法改進(jìn)研究[J].太原理工大學(xué)學(xué)報(bào),2012（5）:572-574，579.

[6]劉濤.農(nóng)林高校學(xué)分制排課系統(tǒng)的設(shè)計(jì)及績(jī)效分析[J].安徽農(nóng)業(yè)科學(xué),2009(28)：3927-3928，3950.

[7]李振,王曉全,張子蛟,候躍生.基于專家系統(tǒng)的交互式排課系統(tǒng)的實(shí)現(xiàn)[J].鄭州大學(xué)學(xué)報(bào)(工學(xué)版),2010（4）:124-128.

（編輯：魯利瑞）