摘 要： 遺傳算法是當(dāng)前計算機領(lǐng)域的熱門課題，將這一熱門課題引入到教育技術(shù)學(xué)領(lǐng)域中來加以研究應(yīng)用。排課問題本身是一個資源分配問題，隨著多媒體教室的功能日益增加，需要引入一種將教室設(shè)備作為影響授課因素之一的排課算法。分析了多媒體教室排課算法的數(shù)學(xué)模型、約束條件以及算法設(shè)計。

　　關(guān)鍵詞： 遺傳算法；多媒體教室；排課問題

　　隨著國家對教育的投入逐漸加大以及各高校對現(xiàn)代教育技術(shù)設(shè)備的重視，目前國內(nèi)大多數(shù)高校的普通教室均已換為多媒體教室。有些多媒體教室還配備有數(shù)字展示臺或者高解析度的多媒體液晶投影機以及帶觸摸功能的投影白板等設(shè)備。還有一些多媒體教室安裝有攝錄像系統(tǒng)，即裝配有攝像機和拾音話筒，可以用來對老師和學(xué)生的教學(xué)活動過程進行攝錄，并將攝像所得的視頻信號以及話筒采集的音頻信號傳送到中心控制室，然后后臺的教育技術(shù)工作人員可以將信息記錄儲存或直播到其他教學(xué)場所，從而實現(xiàn)大范圍的觀摩傳播[1]。

　　但是考慮到實際需要，為所有多媒體教室全部配置這么多的電教設(shè)備是非常浪費的。因此大多數(shù)的多媒體教室仍然遵循著“少而精”的原則，只配備有最基本的設(shè)備包括：計算機、投影機、幕布、功放和話筒音箱。這就對傳統(tǒng)的排課算法提出了一個新的要求，及要將需要特殊教學(xué)設(shè)備的教師排到有這些設(shè)備的多媒體教室之中。

1 高校多媒體教室排課問題分析以及描述

　　1.1 高校多媒體教室排課目標(biāo)

　　高校多媒體教室的排課問題實際上是一個資源分配的問題,其本質(zhì)就是要在滿足一定條件的前提下，將教學(xué)資源分配給各個需要的教師[2]。即將有授課任務(wù)的教師、普通多媒體教室、帶特殊設(shè)備的多媒體教室、班級、課程安排在一周內(nèi)不發(fā)生任何沖突的授課時間段里。

　　1.2 影響多媒體教室排課的若干因素以及約束條件

　　在進行多媒體教室排課時，需要考慮如下約束條件以及若干因素[3]。

　?、排耪n算法的約束條件

　　約束條件可以分為硬性約束條件和軟性約束條件兩類[4]，硬性約束條件是指排課時所必須遵循的條件，有如下4條：①某一班級在某一授課時段內(nèi)只能安排不大于一門課的課程任務(wù)；②某一多媒體教室在某一授課時段內(nèi)只能安排不大于一門課的課程任務(wù)；③一個教師在某一授課時段內(nèi)不能同時安排有一門以上的課程任務(wù)；④某些課程對于多媒體教室的特殊要求應(yīng)得到滿足，并且教室的容量要大于上課的學(xué)生數(shù)。

　　軟性約束條件是指在排課過程中需要盡量滿足，但是無法滿足時亦可以接受的條件。比如：①盡量滿足教師對于授課時間和授課教室的要求；②要盡量將人文類課程與自然科學(xué)類學(xué)科交叉安排；理論課與實踐課交叉安排；同一門課程的授課時間不宜安排過密，應(yīng)進行間斷而不要連排；③將課程盡量安排在授課效果比較好的授課時段內(nèi)，如上午8:00~11:30的授課時段，或下午14:00~15:30的授課時段內(nèi)；④盡量將課程安排在授課效果比較好，設(shè)備比較新的多媒體教室內(nèi)。軟性約束條件雖然不是一定要滿足的，但它卻是衡量一個排課算法優(yōu)劣的重要條件。

　?、婆耪n算法的若干因素

　　在排課時需要涉及如下若干因素。

　?、偈谡n時間段：在排課時需要以教學(xué)周為單位來安排授課時間，而教學(xué)周的每一天又可分為上午一、二節(jié)，三、四節(jié)，下午五、六節(jié)，七、八節(jié)，晚上九、十、十一節(jié)，授課的最小單位是節(jié)，一門課的授課時間通常是兩節(jié)或三節(jié)。

　　②多媒體教室：首先要保證教室的容量要大于上課學(xué)生的數(shù)量，其次要保證多媒體教室內(nèi)擁有上這門課的必要設(shè)備。

　?、凵险n教師：每一個教師都要有一個唯一的編號。

　?、苁谡n班級：每一個班級都有一個唯一的編號并有學(xué)生的數(shù)量信息。

2 交互式遺傳算法的高校自動排課模型設(shè)計

　　2.1 交互式遺傳算法簡介

　　現(xiàn)在智能優(yōu)化是目前國內(nèi)信息學(xué)科的一個研究熱點，而交互式遺傳算法又是智能優(yōu)化的研究方向之一。交互式遺傳算法的主要特點是將傳統(tǒng)的遺傳算法進化機制與人的智能評價相結(jié)合，從而解決一些傳統(tǒng)算法所不能解決的隱式性能指標(biāo)優(yōu)化問題[5]。

　　2.2 各個因素的數(shù)學(xué)模型建立

　　可以把學(xué)校內(nèi)的各個班級定義為集合C={c1,c2,c3,…,cc},并且每個班級對應(yīng)著{p1,p2,p3,…,pc}個學(xué)生數(shù)。

　　課程集合K={k1,k2,k3,…,kk},這里需要將所有的課程都編上唯一的號，即使同一教師為不同班級上的同一門課也要有自己的編號，這樣做可以簡化問題的求解。并且每一門課程都要有自己對于多媒體教室設(shè)備的要求{y1,y2,y3,…,yk}。

　　多媒體教室集合R={r1,r2,r3,…,rr},以及各個教室的最大容量{m1,m2,m3,…,mr}，并且可以根據(jù)多媒體教室的設(shè)備多少給他們加上一個設(shè)備屬性{z1,z2,z3,…,zr}。并且可以將多媒體教室分級，即包含設(shè)備最全的給與其等級5，其次的分別為4,3,2,1。這樣定義的課程對于設(shè)備的要求屬性{y1,y2,y3,…,yk}以及多媒體教室的設(shè)備屬性{z1,z2,z3,…,zr}就均可用1~5的數(shù)值來進行賦值。

　　上課教師定義為集合T={t1,t2,…,tt}，并且每一位老師都對應(yīng)著集合K內(nèi)的若干課程。

　　授課時間段集合S={s1,s2,s3,…,ss}。在這里考慮求解問題的需要，求出授課時間段集合S與多媒體教室集合R的笛卡爾積為：D=S×R=(s1,r1),(s1,r2),(s1,r3),…,(s2,r2),…，(ss,rr)。這樣多媒體教室排課問題就可以轉(zhuǎn)化為一個目標(biāo)分配問題，也就是將課程集合K分配到授課時間段集合S與多媒體教室集合R的笛卡爾積集合D之中，亦可以將D寫為{d11,d12,d13,…,d1r,…,dsr}。

　　2.3 約束條件的數(shù)學(xué)模型

　　之前所規(guī)定的硬性約束條件也可以轉(zhuǎn)化為如下的數(shù)學(xué)模型即：

　　。即任意班級Cc在任意一個多媒體教室的某一授課時段Dsr內(nèi)能上課程數(shù)目為1或者是0。而由于對課程編號時已經(jīng)將同一教師為不同班級(非合班課程)上的同一門課也分別編號，因此也就排除了一個教師在某一授課時段內(nèi)同時安排有一門以上的課程任務(wù)的可能。而且采用授課時間段集合S與多媒體教室集合R的笛卡爾積來進行計算也保證了某一多媒體教室在某一授課時段內(nèi)只能安排不大于一門課的課程任務(wù)。

　　并且還要滿足多媒體教室的容量mr≥班級Cc所對應(yīng)著的學(xué)生個數(shù)Pc。而且多媒體教室的設(shè)備屬性Zr應(yīng)當(dāng)≥課程Kk對于教室設(shè)備的要求屬性Yk。

3 算法設(shè)計

　　3.1 編碼方案

　　本文跟據(jù)實際情況將編碼結(jié)構(gòu)采用如表1所示的形式。

　　在單個染色體中，根據(jù)實際情況可以對教師ID、班級ID、課程ID、時間ID及多媒體教室ID，分別賦予不同位數(shù)十進制數(shù)據(jù)。由于本校在用的正方教務(wù)系統(tǒng)設(shè)計教師ID為6位十進制數(shù)，而班級ID為7位十進制數(shù)，課程ID為9位十進制數(shù)，而時間ID需要給與其6位十進制數(shù)，而多媒體教室ID則根據(jù)實際情況僅需要4位十進制數(shù)。這樣例如一個編號為200021的教師，如果要對B11英語1班編號為1111011的同學(xué)教授“現(xiàn)代教育技術(shù)”編號為048972635這門課（現(xiàn)代教育技術(shù)，周學(xué)時4，總學(xué)時32，上課周數(shù)為1~8周），隨機產(chǎn)生上課時間，并選擇總?cè)藬?shù)以及教室設(shè)備等級符合課程要求的任意教室，即可產(chǎn)生染色體：“20002104897263511110111813331216”。其中最后面的181333表示上課時間是1~8周的周一下午一二節(jié)，周三下午一二節(jié)，1216表示多媒體教室編號為1號樓216教室。

　　這樣按照如上的編碼方式，僅需要讓染色體的后8位產(chǎn)生交叉變異，就既不會影響教師教授本課程，也不會影響其他課程的數(shù)據(jù)。

　　3.2 優(yōu)化方案

　　在完成編碼之后，還需要設(shè)計一些適應(yīng)度函數(shù)，來使得算法可以盡量滿足軟性約束條件，從而可以實現(xiàn)資源分配的最優(yōu)效果。

　?、疟M量滿足教師對于授課時間和授課教室的要求?？梢詫⒔處煹募蟃={t1,t2,…,tt}按照職稱加權(quán)，比如按照助教、講師、副教授、教授，分別賦權(quán)1、2、3、4，然后將其意愿分為α1=0和α2=1，表示不愿意和愿意。 排課的最后目標(biāo)應(yīng)實現(xiàn)max(f1)=Σ(ti×αj)。

　?、茖⒄n程盡量安排在授課效果比較好的授課時段內(nèi)。首先將課程k根據(jù)其類型和重要程度分別給予賦權(quán)ε={1,2,3,4}，然后將授課時間s為上午一二節(jié)，三四節(jié)和下午五六節(jié)的時間段賦權(quán)為2，其余賦權(quán)為1。 最后再從算法生成的結(jié)果中挑出符合max(f2)= Σ(k×s)的來獲取下一段種群。

　?、峭婚T課程的授課時間不宜安排過密，應(yīng)進行間斷而不要連排。當(dāng)一門課在一周內(nèi)的授課節(jié)數(shù)≥4的時候，應(yīng)當(dāng)考慮將其分隔1天以上的時間來進行授課。這里保留第一條中根據(jù)課程重要程度而進行的賦權(quán)ε，并且引入新的集合θ={1,2,3,4}分別表示課程間隔為0天，3天，1天和2天。然后最終目標(biāo)應(yīng)當(dāng)實現(xiàn)max(f3)= Σ(k ×θ)。

　?、纫岣咴O(shè)備較新的教室的利用率。所用的思路同上述方法一樣，也是根據(jù)多媒體教室R的設(shè)備屬性賦值{z1,z2,z3,…,zr}，將盡量多的課程k(保留第一條中根據(jù)課程重要程度而進行的賦權(quán)ε)排在其中，以實現(xiàn)max(f4)= Σ{r×k}。

　　3.3 算法的實現(xiàn)

　　本算法的具體流程圖如圖1所示。

　　在具體實現(xiàn)上，可以通過英國The University of Sheffield所開發(fā)的基于MATLAB的遺傳算法工具箱來完成[6]。

　　這里調(diào)用函數(shù)crttrp來完成種群初始化，schedule =crttrp(nind,FieldDR)可以創(chuàng)建一個隨機實值矩陣，這里的nind制定了種群中的個體數(shù)量，F(xiàn)ieldDR則限定了每個個體變量的邊界。在本例中需要通過FieldDR來保證每一個個體都是符合上文所述的編碼邏輯。

　?、艥M足停止準(zhǔn)則。這里可以設(shè)計算法的迭代數(shù)，當(dāng)完成最后一次迭代時，算法終止。

　?、朴嬎銈€體適應(yīng)值。在這里需要計算符合算法硬性條件和軟性條件的最優(yōu)值。

　?、沁x擇?？梢哉{(diào)用工具箱中的select函數(shù)來從種群schedule中選擇優(yōu)良個體，并將選擇的個體返回到子種群selSC中。具體調(diào)用方法為selSC=select（sel_f, schedule,Fitnv,Ggap）,其中sel_f是一字符串，它包含低級選擇的函數(shù)名，它決定函數(shù)進行選擇的方式是sus(隨機變量抽樣)或者rws（輪盤賭選擇）。這里采用sus即按照個體在當(dāng)前種群中的適應(yīng)度，fitnv為繁殖概率性選擇個體。Fitnv是一個列向量，包含種群schedule中個體適應(yīng)度的值，表明了每個個體被選擇的與其概率。Ggap是一可選參數(shù)，指出了代溝，部分種群被復(fù)制。

　?、冉徊妗１纠兄恍枰獙θ旧w的后8位產(chǎn)生交叉變異即可，在這里選用兩點交叉即指在個體編碼串中設(shè)置兩個交叉點，然后再進行部分基因交換。具體過程如圖2所示。

　　在MATLAB工具箱中可以調(diào)用函數(shù)xovdp來實現(xiàn)，具體調(diào)用方法為newschedule=xovdp(oldschedule,xovr)，Xovr為一可選參數(shù)。

　　⑸變異。為了改善算法的局部搜索能力以及維持群體的多樣性，避免早熟現(xiàn)象出現(xiàn)，需要對個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換。在MATLAB工具箱中可以調(diào)用函數(shù)mutate來實現(xiàn)。具體調(diào)用方法為newschedule=mutate(mut_f,oldschedule,FieldDR),mutate執(zhí)行種群oldschedule中個體的變異，并在新種群中返回變異后的個體。

　　通過這些工具箱函數(shù)，就可以在MATLAB中實現(xiàn)本算法。

　　遺傳算法是自然遺傳學(xué)和計算機科學(xué)相互結(jié)合滲透而成的新的計算方法，是目前計算機科學(xué)方面的研究熱點之一。而如何將這一技術(shù)運用到教育技術(shù)學(xué)領(lǐng)域中，讓其運用到教育教學(xué)工作之中也是教育技術(shù)工作者所要關(guān)注的事情。教育技術(shù)工作者們不能僅限于成熟技術(shù)的移植，還應(yīng)當(dāng)考慮從算法層面來對目前的教育教學(xué)設(shè)備進行改良。

　　參考文獻

　　[1] 辛蔚峰.高校信息技術(shù)應(yīng)用成本—效益評估模型建構(gòu)與分析[J].現(xiàn)代教育技術(shù)，2013（4）：16-20.

　　[2] Pillay N, Banzhaf W. A study of heuristic combinations for hyper-heuristic systems for the incapacitated examination timetabling problem[J]. European Journal of Operational Research ,2009,197(2):481-491.

　　[3]李紅嬋，戶剛，朱顥東.基于群體優(yōu)勢遺傳算法的高校排課問題研究[J]. 計算機工程與應(yīng)用，2011,47(10):233-236.

　　[4] Zhang Defu, Liu Yongkai,Hallah R M. A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems[J].European Journal of Operational Research,2010,203(3):550-558.

　　[5] 鞏敦衛(wèi)，郝國生，周勇，等. 交互式遺傳算法原理及其應(yīng)用[M]. 北京：國防工業(yè)出版社，2007.

　　[6] 雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用[M]. 西安：西安電子科技大學(xué)出版社，2011.