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

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

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

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

4(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽 110168)

5(山東大學(xué) 大數(shù)據(jù)技術(shù)與認(rèn)知智能實(shí)驗(yàn)室,濟(jì)南 250000)

6(北京市中關(guān)村中學(xué),北京 100086)

1 引言

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

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

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

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

2 走班制排課問題

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

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

2.1 問題分析

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

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

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

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

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

3.1 數(shù)學(xué)模型

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

某個(gè)班的學(xué)生定義如下,n為此班級(jí)的人數(shù)：

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

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

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

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

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

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

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

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

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

假設(shè)一個(gè)課程v一周有N個(gè)課時(shí).每門課多少課時(shí),由學(xué)校教務(wù)老師定義,則所有課時(shí)和有限的教室

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

總課表表示為：

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

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

(2)同時(shí)間學(xué)生不能排兩門課程

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

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

(4)課時(shí)均勻：當(dāng)某個(gè)課程有多個(gè)課時(shí),一周內(nèi)其課時(shí)應(yīng)該均勻分布到每一天.

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

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

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

在某個(gè)時(shí)間點(diǎn)是否允許排課表示如下,i是星期,j是課節(jié)：

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

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

3.2 優(yōu)化策略

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

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

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

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

Opt1=bestFitness - individual.getFitness()

Opt2=bestFitness - population.getAvgFitness()

Opt1 表示當(dāng)前代課表中最好適應(yīng)度與當(dāng)前代中某個(gè)課表適應(yīng)度之間的差值,Opt2 表示當(dāng)前代中某個(gè)課表與當(dāng)前代課表中最好適應(yīng)度之間的差值.adaptive-MutationRate 作為新的變異率參與迭代計(jì)算.

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

(2)沖突染色體算子

沖突染色體算子是指構(gòu)建長度與原有染色體一致的沖突染色體,并對(duì)原有染色體進(jìn)行沖突基因記錄的過程.

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

圖1 沖突染色體

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

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

基本的步驟如下：

步驟1.隨機(jī)初始一個(gè)大小為N的課表種群M.

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

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

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

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

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

圖2 GA* 算法流程圖

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

圖3 沖突染色體作用圖

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

4 實(shí)驗(yàn)構(gòu)建與系統(tǒng)實(shí)現(xiàn)

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

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

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

由表1可以看出,物理選擇人數(shù)是最多的,接近一半學(xué)生選擇此科目作為選考科目,因?yàn)橛行└咝Ｒ呀?jīng)發(fā)布專業(yè)錄取條件,如要求選擇報(bào)考計(jì)算機(jī)專業(yè)時(shí)高中必須把物理作為選考科目.

4.2 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)使用的是某中學(xué)服務(wù)器,其服務(wù)器配置如表2.

表2 服務(wù)器配置

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

表3中值為每種策略各運(yùn)行3 次,求平均值所得.通過分班時(shí)間可以得出,隨機(jī)分班所花時(shí)間最少,按成績分班由于需要考慮每個(gè)學(xué)生的成績及排名,花費(fèi)時(shí)間最多.

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

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

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

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

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

圖4 新建排課任務(wù)

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

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

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

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

圖6 教務(wù)部分課表

圖7 教師課表

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

5 結(jié)論與展望

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

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