面向中學走班制排課的優(yōu)化遺傳算法①

張永宏,王永吉,付立軍,李 旭,胡勝文

1(中國科學院大學 工程科學學院,北京 100049)

2(中國科學院 軟件研究所,北京 100190)

3(中國科學院大學,北京 100049)

4(中國科學院 沈陽計算技術研究所,沈陽 110168)

5(山東大學 大數(shù)據(jù)技術與認知智能實驗室,濟南 250000)

6(北京市中關村中學,北京 100086)

1 引言

排課問題是一個組合優(yōu)化問題,20世紀60年代初,Gotlieb 提出了一個關于課程表,并使用算法求解了三維線性規(guī)劃問題.在這之后,學術界對這一問題展開了逐步深入的討論,討論關注在求解方法的復雜度及問題是否一定存在解這兩方面.20世紀60年代中期,Mihoc 和Balas 把求解課程表的數(shù)學表達式轉(zhuǎn)化為了一個優(yōu)化問題[1],之后有學者在排課的各種變量之間建立線性編程.有部分學者使用遺傳算法[2,3]來解決這一類問題.遺傳算法是模擬達爾文進化論自然選擇的思想,是一種優(yōu)勝劣汰的算法,適應環(huán)境能力差的個體,隨著時間會被淘汰,剩下總?cè)褐械膫€體都是適應環(huán)境的個體[4].有些學者基于遺傳算法做了一些優(yōu)化工作,如使用兩次遺傳算法分別對學生分組和排課[5],排課中將每個年級的班級分為若干個組再進行排課[6],基于模式的改進遺傳算法[7],二元變異算子代替?zhèn)鹘y(tǒng)的變異算子[8],結(jié)合水平集概念優(yōu)化遺傳算法[9],引入新的交叉算子及替換操作[10],提出退化混沌突變算子進行優(yōu)化[11],使用遺傳算法和其他算法組合的方式對排課問題進行求解[12,13]等.

這些探索使得遺傳算法在解決排課問題上,具有針對課表迭代過程中早熟收斂或停滯找不到解的問題,存在使解有可能達到全局最優(yōu)的優(yōu)勢.但同時存在收斂速度慢,迭代過程中產(chǎn)生很多無用解的問題.并且更多的是融合其他算法或?qū)z傳算法已有算子進行改進.

新課改走班制的推行,實現(xiàn)了學生的自主選科選課.大多數(shù)省份規(guī)定從物化生史地政6 門科目中學生選擇自己擅長的科目作為高考科目[14,15],有的省份還會多一門信息技術科目,有些省份還會出限選科目套餐,只能在規(guī)定的科目套餐里選擇科目.允許學生自己選擇科目,意味著學校需要根據(jù)每個科目的選擇人數(shù)對每個科目中的學生進行分班,再加上教師、教室、上課時間等多類軟硬件資源的約束,師、生、學校獲得一套可行課表成為一個新的典型的具有高復雜度的組合優(yōu)化問題.

針對新課改實行的走班制排課,本文把沖突染色體算子引入到遺傳算法中,提出沖突染色體算子優(yōu)化在使用遺傳算法解決走班制排課難題中存在的算法迭代過程中收斂速度慢的問題.沖突染色體可以剪掉算法迭代過程中產(chǎn)生的無用解,采用沖突染色體優(yōu)化的遺傳算法既可以保留遺傳算法本身解的搜索能力,又可以加速算法收斂,從而減少走班制排課所需時間,提升了走班制排課的效率.并依據(jù)此優(yōu)化算法及多種分班策略、集成的其他數(shù)據(jù)模塊構建了一套新的走班制排課系統(tǒng)用于驗證此優(yōu)化算法的有效性.

2 走班制排課問題

走班制教學前的排課按照行政班模式,不涉及學生選課問題.其排課時不需考慮學生自主選擇的課程造成的影響,排課的難度相對走班制排課要低,走班制排課與傳統(tǒng)行政班排課最大的區(qū)別在于是否考慮學生上課沖突問題.

走班排課過程中需考慮如何衡量排課算法的優(yōu)劣其實來源于排課算法的核心問題,那就是如何對學生、教師、時間、教室、課程等教育資源的組合與規(guī)劃[16],這種規(guī)劃必須是建立在各個資源沒有沖突且它們都能發(fā)揮出本身優(yōu)勢之上.

2.1 問題分析

學校硬件和軟件資源是否充裕,也直接影響著排課算法的結(jié)果,如是否對學生選課有限制,教師是否充裕,教室是否充裕等.還有一些中學對學生分班有特殊要求,如各班級成績要均勻；根據(jù)學生成績還要做分層,學習較快的同學進入快班,學習較慢的同學進入慢班等.

根據(jù)學生選課情況分班是排課的第一步,班級分的好對后期算法快速迭代效果明顯,沖突率也較低.班級分不好也可能排不出課表.學生分班后對其配備教師和課時.把課程、學生、教師綁定在一起,即每一門課程都包含一個班的學生和一個教師.再把課程和上課時間、上課教室組合找出一個滿足要求的課表.

以上是一款排課算法應滿足的最基礎要求,一款好的排課算法還應盡可能多的滿足學校提出的各種軟性要求,如教案齊頭,某個教師某天某節(jié)課不能排課等等,排課總用時也應盡可能少.

為解決以上問題,提出以沖突染色體算子為核心的遺傳算法優(yōu)化策略,并以實驗和系統(tǒng)驗證該優(yōu)化策略的有效性.

3 優(yōu)化遺傳算法

3.1 數(shù)學模型

走班制排課問題很容易忽略的一點是學生如何分班,排課前要根據(jù)學生的選課情況進行分班,分班策略做的不好,排課時遇到?jīng)_突的概率就會大大增加,導致排不出課表.學生選好課后,由教務老師負責按各科目分班,算法模型實現(xiàn)了按學生科目成績、隨機、學生選課組合等分班策略,滿足學校對分班的多需求,其中按選課組合分班可大程度降低排課過程中學排課沖突.

某個班的學生定義如下,n為此班級的人數(shù)：

老師集合定義如下,j為教師總數(shù)：

所有班級的集定義如下,k為班級總數(shù),包含行政班班級和教學班班級：

所有課程的集合定義如下,p表示所有課程總數(shù)：

所有教室的集合定義如下,m表示教室總數(shù)：

所有課位的集合表示如下,i表示課位總數(shù)：

則可使用如下五元組數(shù)據(jù)表示走班排課問題,五元組表示如下：

如選考班或行政班則表示為：物理選考1 班或數(shù)學1 班,由張三老師任課,在高中樓103 上課,上課時間為周一第3 節(jié)課

引入集合V：綁定教師、學生、課程的事件信息的集合.

式中,A可表示行政班或教學班學生集合.則排課問題由五元組轉(zhuǎn)換成三元組表示：

假設一個課程v一周有N個課時.每門課多少課時,由學校教務老師定義,則所有課時和有限的教室

上課時間,“ti”表示周幾,第幾節(jié)課等資源組合,找出一個實現(xiàn)任一必須滿足的約束和盡努力滿足的軟性約束的課表.

總課表表示為：

根據(jù)以上定義,則可得出排課程表中必須滿足的規(guī)則如下：

(1)同時間老師不能教兩門課程

(2)同時間學生不能排兩門課程

(3)同時間同教室不安排兩門課程

以及考慮課表可用性,還需滿足以下約束.

(4)課時均勻：當某個課程有多個課時,一周內(nèi)其課時應該均勻分布到每一天.

(5)課時連排：某些課程有連著排需求,如語文課周五上午排在第2 節(jié)和第3 節(jié)課,用于寫作文.

(6)教案齊頭：若一個教師帶兩個班,則要求兩個班的進度要相同.

(7)教師禁止或必須排課時間：教師進修或者有其他原因,需要設置教師禁止排課時間或必須排課時間.

在某個時間點是否允許排課表示如下,i是星期,j是課節(jié)：

在算法迭代過程中,算法的目標函數(shù)φ (X)計算公式為：

其中,F(X)和G(X)表示當前課表必須滿足的約束沖突數(shù).個體在當前排課方案中每違背一次約束條件,F(X)或G(X)值就加1.當φ (X)值為1 時,表示排課成功.

3.2 優(yōu)化策略

在使用相同計算硬件資源條件下,加入了以下優(yōu)化策略,排課效率提升了19.2%.

(1)變異率實現(xiàn)自縮放

遺傳算法可以設置初始交叉率和變異率,每次交叉或者變異時都會按照預先設定好的值進行,但隨著迭代的進行,考慮到每個個體對變異的需求不同,變異率若可動態(tài)調(diào)整,則可使迭代速度加快.

課表在編譯時的變異率adaptiveMutationRate 做了以下優(yōu)化：bestFitness 為當前代中適應度最好的課表的適應度；individual 表示某一代中的某個課表；population表示某一代所有的課表集合.

Opt1=bestFitness - individual.getFitness()

Opt2=bestFitness - population.getAvgFitness()

Opt1 表示當前代課表中最好適應度與當前代中某個課表適應度之間的差值,Opt2 表示當前代中某個課表與當前代課表中最好適應度之間的差值.adaptive-MutationRate 作為新的變異率參與迭代計算.

adaptiveMutationRate=(Opt1 / Opt2)*mutationRate Opt1/ Opt2 的比值作為原變異率的膨脹系數(shù).

(2)沖突染色體算子

沖突染色體算子是指構建長度與原有染色體一致的沖突染色體,并對原有染色體進行沖突基因記錄的過程.

沖突染色體結(jié)構如圖1所示.上方每一小格表示某一門課的1 個課時,小格內(nèi)有兩位數(shù)字,第一位表示教室編碼,第二位表示課位編碼.

圖1 沖突染色體

下方每位對應的0 或1 數(shù)字表示當前小格組合是否與其他組合存在沖突,若沖突,迭代時上方小格的值必改變,從而保證課表中的沖突個數(shù)是在不斷降低的,如前面提到的硬性約束不滿足,利用此結(jié)構可剪掉算法求解過程中的無用解.

優(yōu)化后的GA*算法流程如圖2所示.

基本的步驟如下：

步驟1.隨機初始一個大小為N的課表種群M.

步驟2.計算M中各個個體的適應度值,根據(jù)適應度值的大小按照降序排序.若個體最大適應度為1 或迭代次數(shù)超過設置最大值轉(zhuǎn)至步驟6.

步驟3.生成一個大小為N的沖突染色體總?cè)篜,P中每個個體長度與M中每個個體長度一致,初始化P中所有個體各基因為0,表示基因沒有沖突,計算M中各個體沖突基因的下標,并把P中這些下標對應位置的值賦為1,表示此處基因存在沖突.

步驟4.選擇M中排名前k的個體直接繼承到下一代.

步驟5.對種群M進行選擇交叉和自適應變異操作,其中交叉和自適應變異過程需要考慮個體對應的沖突染色體,存在沖突的基因,不遵循交叉率和變異率規(guī)律,此處基因100%交叉或者變異.生成新的種群,轉(zhuǎn)到步驟2.

步驟6.退出循環(huán),將結(jié)果解碼輸出課表.

圖2 GA* 算法流程圖

對算法迭代過程中優(yōu)化的核心內(nèi)容展開,如圖3.

圖3 沖突染色體作用圖

可以看到新一代個體的沖突個數(shù)整體上是下降的,證明算法的優(yōu)化是有效的.沖突染色體值為1 的基因在變異過程時保證100%變異,沖突染色體值為0 的基因,按自適應變異率變異.

4 實驗構建與系統(tǒng)實現(xiàn)

4.1 數(shù)據(jù)來源

本次實驗使用某市某中學高二上學期真實走班選課數(shù)據(jù),包括495 名學生,31 個教師,18 個教室,12 門課及學生的選課結(jié)果.對比此優(yōu)化算法.實驗以排課時間作為優(yōu)化后的遺傳算法的評價指標,以分班時間及排課時間驗證分班策略對走班排課的影響,都以秒為單位.各個科目的選課人數(shù)如表1所示.

表1 走班課程選課結(jié)果

由表1可以看出,物理選擇人數(shù)是最多的,接近一半學生選擇此科目作為選考科目,因為有些高校已經(jīng)發(fā)布專業(yè)錄取條件,如要求選擇報考計算機專業(yè)時高中必須把物理作為選考科目.

4.2 實驗及結(jié)果分析

實驗使用的是某中學服務器,其服務器配置如表2.

表2 服務器配置

3種分班策略分別為隨機分班、按照成績分班、按照選課組合分班.隨機分班指不考慮任何條件,隨機的把選擇某個科目的學生分到某個班.按照成績分班指考慮學生當前科目的成績,按照排名前后分入某個班級.按照選擇組合分班指把選擇相同3 個科目的學生分到同一個班.在前文數(shù)據(jù)模型中多約束條件下走班制排課對比效果如表3所示.

表3中值為每種策略各運行3 次,求平均值所得.通過分班時間可以得出,隨機分班所花時間最少,按成績分班由于需要考慮每個學生的成績及排名,花費時間最多.

表3 算法優(yōu)化后的排課效率對比

通過表3還可以看出,在不同分班策略下,優(yōu)化后的GA*算法排課時間都明顯下降,并且按照選課組合分班排課時間花費最少,為101 s,因為走班排課問題中最容易引發(fā)沖突的點是學生,按照選課組合分班,可以降低學生的排課沖突.因此證明使用該沖突染色體算子優(yōu)化可以提高排課效率.

4.3 系統(tǒng)實現(xiàn)

面向中學的教師或?qū)W生等用戶時,一個完整的走班制排課系統(tǒng)應滿足從選課、分班到排課等完整的流程.新系統(tǒng)對整體排課流程進行了梳理,并集成學生選課、學生成績、學生評測等模塊.

首先教務老師新建排課任務時,首先選定年級和學期,系統(tǒng)會自動獲取對應年級的學生數(shù)據(jù),及教師數(shù)據(jù).新建排課任務完成以后,開始對此次排課任務配置課程,配置完成后,學生登錄系統(tǒng)可看到配置的課程數(shù)據(jù),并進行選擇課程操作,選擇課程中后端會自動校驗選擇課程數(shù)據(jù)是否正確.如圖4所示.

圖4 新建排課任務

學生選課完成后,教務老師根據(jù)學生選課情況,調(diào)用學生成績模塊數(shù)據(jù)或?qū)W生評測模塊數(shù)據(jù)等進行班級分配,分配完成后學生即分入了確定班級,再為這些班級分配教師.此時課程、學生、教師數(shù)據(jù)完成融合.具體樣式如“物理選考1 班,xx 教師,5 課時,學生列表{1.學號；2.學號；…；40.學號}”.如圖5所示.

待以上操作全部完成后,開始設置軟約束條件,將編碼后的數(shù)據(jù)輸入到優(yōu)化的走班制排課算法中,系統(tǒng)在迭代過程時會調(diào)用配置的軟約束,及默認必須滿足的硬約束.排課結(jié)束后課表解碼并返回給用戶.

系統(tǒng)輸出多種類型課表,如教務課表、學生課表、教師課表、教室課表.如圖6、圖7給出部分課表,圖6為教務部分課表,圖7為教師課表.

圖5 數(shù)據(jù)融合及編碼

圖6 教務部分課表

圖7 教師課表

系統(tǒng)運行時間及結(jié)果進一步驗證了沖突染色體優(yōu)化的有效性.

5 結(jié)論與展望

本文通過實驗驗證了沖突染色體算子優(yōu)化遺傳算法的有效性,提高了走班制排課的效率.為使用遺傳算法解決組合優(yōu)化問題提供了一種優(yōu)化思路.實驗還驗證了不同的分班策略對走班制排課的影響,實驗表明按照選課組合對學生進行分班,同樣算法條件下可使走班制排課效率得到更多的提升.并依此構建了一個新走班制排課系統(tǒng),該系統(tǒng)目前正在某中學試運行,并為高二年級進行了走班制排課,反饋效果很好.

當前對采取走班制該教學方式的學校而言排課還是一個挑戰(zhàn),考慮到約束條件多、動態(tài)性強,且學校具有各自不同的走班需求,使得算法實現(xiàn)的復雜度變高.目前此算法實現(xiàn)了在當前約束條件下可排出課表的問題,但也可能出現(xiàn)約束擴增到一定程度時算法可能無解的問題,后續(xù)還需繼續(xù)優(yōu)化算法及對約束條件的分類梳理,對比分析不同約束對排課的影響.