面向中學走班制排課的優化遺傳算法①

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

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

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

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

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

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

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

1 引言

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

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

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

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

2 走班制排課問題

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

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

2.1 問題分析

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

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

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

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

3 優化遺傳算法

3.1 數學模型

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

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

老師集合定義如下,j為教師總數：

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

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

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

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

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

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

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

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

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

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

總課表表示為：

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

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

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

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

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

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

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

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

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

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

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

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

3.2 優化策略

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

(1)變異率實現自縮放

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

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

Opt1=bestFitness - individual.getFitness()

Opt2=bestFitness - population.getAvgFitness()

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

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

(2)沖突染色體算子

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

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

圖1 沖突染色體

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

優化后的GA*算法流程如圖2所示.

基本的步驟如下：

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

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

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

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

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

步驟6.退出循環,將結果解碼輸出課表.

圖2 GA* 算法流程圖

對算法迭代過程中優化的核心內容展開,如圖3.

圖3 沖突染色體作用圖

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

4 實驗構建與系統實現

4.1 數據來源

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

表1 走班課程選課結果

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

4.2 實驗及結果分析

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

表2 服務器配置

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

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

表3 算法優化后的排課效率對比

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

4.3 系統實現

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

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

圖4 新建排課任務

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

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

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

圖5 數據融合及編碼

圖6 教務部分課表

圖7 教師課表

系統運行時間及結果進一步驗證了沖突染色體優化的有效性.

5 結論與展望

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

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