摘 要： 遺傳算法是當(dāng)前計(jì)算機(jī)領(lǐng)域的熱門課題，將這一熱門課題引入到教育技術(shù)學(xué)領(lǐng)域中來(lái)加以研究應(yīng)用。排課問(wèn)題本身是一個(gè)資源分配問(wèn)題，隨著多媒體教室的功能日益增加，需要引入一種將教室設(shè)備作為影響授課因素之一的排課算法。分析了多媒體教室排課算法的數(shù)學(xué)模型、約束條件以及算法設(shè)計(jì)。
關(guān)鍵詞： 遺傳算法；多媒體教室；排課問(wèn)題
隨著國(guó)家對(duì)教育的投入逐漸加大以及各高校對(duì)現(xiàn)代教育技術(shù)設(shè)備的重視，目前國(guó)內(nèi)大多數(shù)高校的普通教室均已換為多媒體教室。有些多媒體教室還配備有數(shù)字展示臺(tái)或者高解析度的多媒體液晶投影機(jī)以及帶觸摸功能的投影白板等設(shè)備。還有一些多媒體教室安裝有攝錄像系統(tǒng)，即裝配有攝像機(jī)和拾音話筒，可以用來(lái)對(duì)老師和學(xué)生的教學(xué)活動(dòng)過(guò)程進(jìn)行攝錄，并將攝像所得的視頻信號(hào)以及話筒采集的音頻信號(hào)傳送到中心控制室，然后后臺(tái)的教育技術(shù)工作人員可以將信息記錄儲(chǔ)存或直播到其他教學(xué)場(chǎng)所，從而實(shí)現(xiàn)大范圍的觀摩傳播[1]。
但是考慮到實(shí)際需要，為所有多媒體教室全部配置這么多的電教設(shè)備是非常浪費(fèi)的。因此大多數(shù)的多媒體教室仍然遵循著“少而精”的原則，只配備有最基本的設(shè)備包括：計(jì)算機(jī)、投影機(jī)、幕布、功放和話筒音箱。這就對(duì)傳統(tǒng)的排課算法提出了一個(gè)新的要求，及要將需要特殊教學(xué)設(shè)備的教師排到有這些設(shè)備的多媒體教室之中。
1 高校多媒體教室排課問(wèn)題分析以及描述
1.1 高校多媒體教室排課目標(biāo)
高校多媒體教室的排課問(wèn)題實(shí)際上是一個(gè)資源分配的問(wèn)題,其本質(zhì)就是要在滿足一定條件的前提下，將教學(xué)資源分配給各個(gè)需要的教師[2]。即將有授課任務(wù)的教師、普通多媒體教室、帶特殊設(shè)備的多媒體教室、班級(jí)、課程安排在一周內(nèi)不發(fā)生任何沖突的授課時(shí)間段里。
1.2 影響多媒體教室排課的若干因素以及約束條件
在進(jìn)行多媒體教室排課時(shí)，需要考慮如下約束條件以及若干因素[3]。
⑴排課算法的約束條件
約束條件可以分為硬性約束條件和軟性約束條件兩類[4]，硬性約束條件是指排課時(shí)所必須遵循的條件，有如下4條：①某一班級(jí)在某一授課時(shí)段內(nèi)只能安排不大于一門課的課程任務(wù)；②某一多媒體教室在某一授課時(shí)段內(nèi)只能安排不大于一門課的課程任務(wù)；③一個(gè)教師在某一授課時(shí)段內(nèi)不能同時(shí)安排有一門以上的課程任務(wù)；④某些課程對(duì)于多媒體教室的特殊要求應(yīng)得到滿足，并且教室的容量要大于上課的學(xué)生數(shù)。
軟性約束條件是指在排課過(guò)程中需要盡量滿足，但是無(wú)法滿足時(shí)亦可以接受的條件。比如：①盡量滿足教師對(duì)于授課時(shí)間和授課教室的要求；②要盡量將人文類課程與自然科學(xué)類學(xué)科交叉安排；理論課與實(shí)踐課交叉安排；同一門課程的授課時(shí)間不宜安排過(guò)密，應(yīng)進(jìn)行間斷而不要連排；③將課程盡量安排在授課效果比較好的授課時(shí)段內(nèi)，如上午8:00~11:30的授課時(shí)段，或下午14:00~15:30的授課時(shí)段內(nèi)；④盡量將課程安排在授課效果比較好，設(shè)備比較新的多媒體教室內(nèi)。軟性約束條件雖然不是一定要滿足的，但它卻是衡量一個(gè)排課算法優(yōu)劣的重要條件。
?、婆耪n算法的若干因素
在排課時(shí)需要涉及如下若干因素。
①授課時(shí)間段：在排課時(shí)需要以教學(xué)周為單位來(lái)安排授課時(shí)間，而教學(xué)周的每一天又可分為上午一、二節(jié)，三、四節(jié)，下午五、六節(jié)，七、八節(jié)，晚上九、十、十一節(jié)，授課的最小單位是節(jié)，一門課的授課時(shí)間通常是兩節(jié)或三節(jié)。
?、诙嗝襟w教室：首先要保證教室的容量要大于上課學(xué)生的數(shù)量，其次要保證多媒體教室內(nèi)擁有上這門課的必要設(shè)備。
?、凵险n教師：每一個(gè)教師都要有一個(gè)唯一的編號(hào)。
④授課班級(jí)：每一個(gè)班級(jí)都有一個(gè)唯一的編號(hào)并有學(xué)生的數(shù)量信息。
2 交互式遺傳算法的高校自動(dòng)排課模型設(shè)計(jì)
2.1 交互式遺傳算法簡(jiǎn)介
現(xiàn)在智能優(yōu)化是目前國(guó)內(nèi)信息學(xué)科的一個(gè)研究熱點(diǎn)，而交互式遺傳算法又是智能優(yōu)化的研究方向之一。交互式遺傳算法的主要特點(diǎn)是將傳統(tǒng)的遺傳算法進(jìn)化機(jī)制與人的智能評(píng)價(jià)相結(jié)合，從而解決一些傳統(tǒng)算法所不能解決的隱式性能指標(biāo)優(yōu)化問(wèn)題[5]。
2.2 各個(gè)因素的數(shù)學(xué)模型建立
可以把學(xué)校內(nèi)的各個(gè)班級(jí)定義為集合C={c1,c2,c3,…,cc},并且每個(gè)班級(jí)對(duì)應(yīng)著{p1,p2,p3,…,pc}個(gè)學(xué)生數(shù)。
課程集合K={k1,k2,k3,…,kk},這里需要將所有的課程都編上唯一的號(hào)，即使同一教師為不同班級(jí)上的同一門課也要有自己的編號(hào)，這樣做可以簡(jiǎn)化問(wèn)題的求解。并且每一門課程都要有自己對(duì)于多媒體教室設(shè)備的要求{y1,y2,y3,…,yk}。
多媒體教室集合R={r1,r2,r3,…,rr},以及各個(gè)教室的最大容量{m1,m2,m3,…,mr}，并且可以根據(jù)多媒體教室的設(shè)備多少給他們加上一個(gè)設(shè)備屬性{z1,z2,z3,…,zr}。并且可以將多媒體教室分級(jí)，即包含設(shè)備最全的給與其等級(jí)5，其次的分別為4,3,2,1。這樣定義的課程對(duì)于設(shè)備的要求屬性{y1,y2,y3,…,yk}以及多媒體教室的設(shè)備屬性{z1,z2,z3,…,zr}就均可用1~5的數(shù)值來(lái)進(jìn)行賦值。
上課教師定義為集合T={t1,t2,…,tt}，并且每一位老師都對(duì)應(yīng)著集合K內(nèi)的若干課程。
授課時(shí)間段集合S={s1,s2,s3,…,ss}。在這里考慮求解問(wèn)題的需要，求出授課時(shí)間段集合S與多媒體教室集合R的笛卡爾積為：D=S×R=(s1,r1),(s1,r2),(s1,r3),…,(s2,r2),…，(ss,rr)。這樣多媒體教室排課問(wèn)題就可以轉(zhuǎn)化為一個(gè)目標(biāo)分配問(wèn)題，也就是將課程集合K分配到授課時(shí)間段集合S與多媒體教室集合R的笛卡爾積集合D之中，亦可以將D寫(xiě)為{d11,d12,d13,…,d1r,…,dsr}。
2.3 約束條件的數(shù)學(xué)模型
之前所規(guī)定的硬性約束條件也可以轉(zhuǎn)化為如下的數(shù)學(xué)模型即：
。即任意班級(jí)Cc在任意一個(gè)多媒體教室的某一授課時(shí)段Dsr內(nèi)能上課程數(shù)目為1或者是0。而由于對(duì)課程編號(hào)時(shí)已經(jīng)將同一教師為不同班級(jí)(非合班課程)上的同一門課也分別編號(hào)，因此也就排除了一個(gè)教師在某一授課時(shí)段內(nèi)同時(shí)安排有一門以上的課程任務(wù)的可能。而且采用授課時(shí)間段集合S與多媒體教室集合R的笛卡爾積來(lái)進(jìn)行計(jì)算也保證了某一多媒體教室在某一授課時(shí)段內(nèi)只能安排不大于一門課的課程任務(wù)。
并且還要滿足多媒體教室的容量mr≥班級(jí)Cc所對(duì)應(yīng)著的學(xué)生個(gè)數(shù)Pc。而且多媒體教室的設(shè)備屬性Zr應(yīng)當(dāng)≥課程Kk對(duì)于教室設(shè)備的要求屬性Yk。
3 算法設(shè)計(jì)
3.1 編碼方案
本文跟據(jù)實(shí)際情況將編碼結(jié)構(gòu)采用如表1所示的形式。
在單個(gè)染色體中，根據(jù)實(shí)際情況可以對(duì)教師ID、班級(jí)ID、課程ID、時(shí)間ID及多媒體教室ID，分別賦予不同位數(shù)十進(jìn)制數(shù)據(jù)。由于本校在用的正方教務(wù)系統(tǒng)設(shè)計(jì)教師ID為6位十進(jìn)制數(shù)，而班級(jí)ID為7位十進(jìn)制數(shù)，課程ID為9位十進(jìn)制數(shù)，而時(shí)間ID需要給與其6位十進(jìn)制數(shù)，而多媒體教室ID則根據(jù)實(shí)際情況僅需要4位十進(jìn)制數(shù)。這樣例如一個(gè)編號(hào)為200021的教師，如果要對(duì)B11英語(yǔ)1班編號(hào)為1111011的同學(xué)教授“現(xiàn)代教育技術(shù)”編號(hào)為048972635這門課（現(xiàn)代教育技術(shù)，周學(xué)時(shí)4，總學(xué)時(shí)32，上課周數(shù)為1~8周），隨機(jī)產(chǎn)生上課時(shí)間，并選擇總?cè)藬?shù)以及教室設(shè)備等級(jí)符合課程要求的任意教室，即可產(chǎn)生染色體：“20002104897263511110111813331216”。其中最后面的181333表示上課時(shí)間是1~8周的周一下午一二節(jié)，周三下午一二節(jié)，1216表示多媒體教室編號(hào)為1號(hào)樓216教室。
這樣按照如上的編碼方式，僅需要讓染色體的后8位產(chǎn)生交叉變異，就既不會(huì)影響教師教授本課程，也不會(huì)影響其他課程的數(shù)據(jù)。
3.2 優(yōu)化方案
在完成編碼之后，還需要設(shè)計(jì)一些適應(yīng)度函數(shù)，來(lái)使得算法可以盡量滿足軟性約束條件，從而可以實(shí)現(xiàn)資源分配的最優(yōu)效果。
?、疟M量滿足教師對(duì)于授課時(shí)間和授課教室的要求。可以將教師的集合T={t1,t2,…,tt}按照職稱加權(quán)，比如按照助教、講師、副教授、教授，分別賦權(quán)1、2、3、4，然后將其意愿分為α1=0和α2=1，表示不愿意和愿意。 排課的最后目標(biāo)應(yīng)實(shí)現(xiàn)max(f1)=Σ(ti×αj)。
?、茖⒄n程盡量安排在授課效果比較好的授課時(shí)段內(nèi)。首先將課程k根據(jù)其類型和重要程度分別給予賦權(quán)ε={1,2,3,4}，然后將授課時(shí)間s為上午一二節(jié)，三四節(jié)和下午五六節(jié)的時(shí)間段賦權(quán)為2，其余賦權(quán)為1。 最后再?gòu)乃惴ㄉ傻慕Y(jié)果中挑出符合max(f2)= Σ(k×s)的來(lái)獲取下一段種群。
?、峭婚T課程的授課時(shí)間不宜安排過(guò)密，應(yīng)進(jìn)行間斷而不要連排。當(dāng)一門課在一周內(nèi)的授課節(jié)數(shù)≥4的時(shí)候，應(yīng)當(dāng)考慮將其分隔1天以上的時(shí)間來(lái)進(jìn)行授課。這里保留第一條中根據(jù)課程重要程度而進(jìn)行的賦權(quán)ε，并且引入新的集合θ={1,2,3,4}分別表示課程間隔為0天，3天，1天和2天。然后最終目標(biāo)應(yīng)當(dāng)實(shí)現(xiàn)max(f3)= Σ(k ×θ)。
?、纫岣咴O(shè)備較新的教室的利用率。所用的思路同上述方法一樣，也是根據(jù)多媒體教室R的設(shè)備屬性賦值{z1,z2,z3,…,zr}，將盡量多的課程k(保留第一條中根據(jù)課程重要程度而進(jìn)行的賦權(quán)ε)排在其中，以實(shí)現(xiàn)max(f4)= Σ{r×k}。
3.3 算法的實(shí)現(xiàn)
本算法的具體流程圖如圖1所示。
在具體實(shí)現(xiàn)上，可以通過(guò)英國(guó)The University of Sheffield所開(kāi)發(fā)的基于MATLAB的遺傳算法工具箱來(lái)完成[6]。
這里調(diào)用函數(shù)crttrp來(lái)完成種群初始化，schedule =crttrp(nind,FieldDR)可以創(chuàng)建一個(gè)隨機(jī)實(shí)值矩陣，這里的nind制定了種群中的個(gè)體數(shù)量，F(xiàn)ieldDR則限定了每個(gè)個(gè)體變量的邊界。在本例中需要通過(guò)FieldDR來(lái)保證每一個(gè)個(gè)體都是符合上文所述的編碼邏輯。
?、艥M足停止準(zhǔn)則。這里可以設(shè)計(jì)算法的迭代數(shù)，當(dāng)完成最后一次迭代時(shí)，算法終止。
⑵計(jì)算個(gè)體適應(yīng)值。在這里需要計(jì)算符合算法硬性條件和軟性條件的最優(yōu)值。
?、沁x擇?？梢哉{(diào)用工具箱中的select函數(shù)來(lái)從種群schedule中選擇優(yōu)良個(gè)體，并將選擇的個(gè)體返回到子種群selSC中。具體調(diào)用方法為selSC=select（sel_f, schedule,Fitnv,Ggap）,其中sel_f是一字符串，它包含低級(jí)選擇的函數(shù)名，它決定函數(shù)進(jìn)行選擇的方式是sus(隨機(jī)變量抽樣)或者rws（輪盤賭選擇）。這里采用sus即按照個(gè)體在當(dāng)前種群中的適應(yīng)度，fitnv為繁殖概率性選擇個(gè)體。Fitnv是一個(gè)列向量，包含種群schedule中個(gè)體適應(yīng)度的值，表明了每個(gè)個(gè)體被選擇的與其概率。Ggap是一可選參數(shù)，指出了代溝，部分種群被復(fù)制。
?、冉徊妗１纠兄恍枰獙?duì)染色體的后8位產(chǎn)生交叉變異即可，在這里選用兩點(diǎn)交叉即指在個(gè)體編碼串中設(shè)置兩個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。具體過(guò)程如圖2所示。
在MATLAB工具箱中可以調(diào)用函數(shù)xovdp來(lái)實(shí)現(xiàn)，具體調(diào)用方法為newschedule=xovdp(oldschedule,xovr)，Xovr為一可選參數(shù)。
?、勺儺?。為了改善算法的局部搜索能力以及維持群體的多樣性，避免早熟現(xiàn)象出現(xiàn)，需要對(duì)個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來(lái)替換。在MATLAB工具箱中可以調(diào)用函數(shù)mutate來(lái)實(shí)現(xiàn)。具體調(diào)用方法為newschedule=mutate(mut_f,oldschedule,FieldDR),mutate執(zhí)行種群oldschedule中個(gè)體的變異，并在新種群中返回變異后的個(gè)體。
通過(guò)這些工具箱函數(shù)，就可以在MATLAB中實(shí)現(xiàn)本算法。
遺傳算法是自然遺傳學(xué)和計(jì)算機(jī)科學(xué)相互結(jié)合滲透而成的新的計(jì)算方法，是目前計(jì)算機(jī)科學(xué)方面的研究熱點(diǎn)之一。而如何將這一技術(shù)運(yùn)用到教育技術(shù)學(xué)領(lǐng)域中，讓其運(yùn)用到教育教學(xué)工作之中也是教育技術(shù)工作者所要關(guān)注的事情。教育技術(shù)工作者們不能僅限于成熟技術(shù)的移植，還應(yīng)當(dāng)考慮從算法層面來(lái)對(duì)目前的教育教學(xué)設(shè)備進(jìn)行改良。
參考文獻(xiàn)
[1] 辛蔚峰.高校信息技術(shù)應(yīng)用成本—效益評(pí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)勢(shì)遺傳算法的高校排課問(wèn)題研究[J]. 計(jì)算機(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)，郝國(guó)生，周勇，等. 交互式遺傳算法原理及其應(yīng)用[M]. 北京：國(guó)防工業(yè)出版社，2007.
[6] 雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用[M]. 西安：西安電子科技大學(xué)出版社，2011.