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