改進(jìn)遺傳算法求解新高考背景下的排課問(wèn)題

徐向陽(yáng) 劉文偉 傅蝶 徐剛 金澈清 王祥豐 王江濤

摘要： 我國(guó)提出新高考改革政策后， 越來(lái)越多地區(qū)和高中開(kāi)始采用走班制教學(xué)模式. 相對(duì)于傳統(tǒng)的行政班教學(xué)模式， 走班制教學(xué)模式使排課問(wèn)題的約束條件進(jìn)一步增多， 學(xué)校教育資源匱乏的現(xiàn)象進(jìn)一步凸顯. 傳統(tǒng)的排課算法不適于求解走班制教學(xué)模式下的排課問(wèn)題， 而純粹的手動(dòng)編排課表不僅費(fèi)時(shí)費(fèi)力， 排出的課表還可能存在大量沖突， 難以保證課表的可行性和合理性. 根據(jù)走班制教學(xué)模式的特點(diǎn)，設(shè)計(jì)了一種獲取優(yōu)質(zhì)可行解的方法： 首先針對(duì)走班課程提出了一種自動(dòng)生成教學(xué)班組合的方法; 然后運(yùn)用改進(jìn)的遺傳算法高效合理地求解排課問(wèn)題. 實(shí)驗(yàn)結(jié)果表明， 該算法可獲得優(yōu)質(zhì)的課表安排， 并且已經(jīng)加入到實(shí)際應(yīng)用中.

關(guān)鍵詞： 走班制; 遺傳算法; 排課問(wèn)題; 排課算法; 組合優(yōu)化

中圖分類(lèi)號(hào)： TP311 文獻(xiàn)標(biāo)志碼： A DOI： 10.3969/j.issn.1000-5641.201921008

0 引言

2014 年， 我國(guó)出臺(tái)了新高考教育改革政策， 在上海和浙江兩地試點(diǎn)， 隨后新高考政策逐漸開(kāi)始在全國(guó)范圍內(nèi)推廣. 該政策引入了走班制教學(xué)模式， 賦予了學(xué)生選學(xué)選考的權(quán)利[1]. 新高考模式下， 學(xué)生的高考成績(jī)將由統(tǒng)一高考的語(yǔ)文、數(shù)學(xué)、英語(yǔ)科目的成績(jī)和高中學(xué)業(yè)水平測(cè)試的任意三門(mén)課的成績(jī)組成， 學(xué)生可以根據(jù)自己的興趣和特長(zhǎng)選擇相應(yīng)的科目， 學(xué)生個(gè)性化教育的需求得到了滿足. 在走班制教學(xué)模式下， 同一個(gè)行政班中學(xué)生的選課可能各不相同; 而傳統(tǒng)的班級(jí)授課模式中， 學(xué)生在固定的行政班里上課， 每位同學(xué)上的課程完全一樣. 實(shí)施走班制教學(xué)會(huì)造成教學(xué)班與行政班交錯(cuò)的情況， 課表的安排更加復(fù)雜， 對(duì)教學(xué)資源的需求會(huì)增加， 課表編排的約束條件也更加苛刻， 而很多學(xué)校都存在著教學(xué)資源匱乏的問(wèn)題， 這種情況下實(shí)施走班制教學(xué)困難重重. 單純手動(dòng)排課不僅費(fèi)時(shí)費(fèi)力， 而且不能保證遵循所有的約束條件， 排出的課表難以滿足教師和學(xué)生的需求. 課表安排是否合理， 對(duì)學(xué)校教學(xué)質(zhì)量有著較大的影響， 因此需要一種高效智能的排課方法來(lái)求解走班制度下的排課問(wèn)題.

排課問(wèn)題的重要性、復(fù)雜性， 使其長(zhǎng)期受到很多專(zhuān)家學(xué)者的關(guān)注與研究. 1962 年， Gotlieb[2] 提出了排課問(wèn)題對(duì)應(yīng)的數(shù)學(xué)模型， 為以后的研究奠定了一定的數(shù)學(xué)基礎(chǔ). Even 等[3] 在1975 年證明了排課問(wèn)題是一個(gè)NP 完全（Non-deterministic Polynomial Complete） 問(wèn)題， 讓人們對(duì)排課問(wèn)題的復(fù)雜性有了理論上的初步認(rèn)識(shí). 然而在20 世紀(jì)90 年代之前， 大多數(shù)的解決方案靠的是教務(wù)管理者的經(jīng)驗(yàn)， 通用性和實(shí)用性較低. 進(jìn)入90 年代后， 隨著計(jì)算機(jī)理論和技術(shù)的不斷發(fā)展， 越來(lái)越多的智能優(yōu)化算法陸續(xù)被用于求解排課問(wèn)題， 且取得了相應(yīng)的成果. 近些年的解決方案有遺傳算法（Genetic Algorithm，GA）[4-6]、模擬退火算法[7]、蟻群算法[8]、禁忌搜索算法[9] 以及混合算法[10] 等， 但是這些方案在約束條件的考慮上有所欠缺， 且基本上是針對(duì)高?；蛘咂胀ㄐ姓嘟虒W(xué)模式的排課問(wèn)題， 不適用于解決行政班和教學(xué)班交錯(cuò)情況的高中走班制排課問(wèn)題.

目前針對(duì)新高考走班排課問(wèn)題的研究較少， 文獻(xiàn)[11-12] 使用改進(jìn)的遺傳算法求解走班制排課問(wèn)題， 做出了一定的貢獻(xiàn)， 但是還存在了一些問(wèn)題， 如要求初始種群中的個(gè)體均無(wú)沖突， 但是在高中走班教學(xué)的實(shí)際情況中， 教學(xué)資源匱乏， 一個(gè)老師可能要教授多個(gè)年級(jí)下的多個(gè)班級(jí)， 一個(gè)教室也可能要安排多個(gè)班級(jí)的課程， 隨機(jī)生成的課表很大概率都會(huì)有沖突， 若要保證種群中的個(gè)體均無(wú)沖突， 則排課所耗費(fèi)的時(shí)間會(huì)大大增加; 此外， 適應(yīng)度函數(shù)的設(shè)計(jì)不夠靈活， 實(shí)際情況下教務(wù)老師會(huì)針對(duì)本校的情況設(shè)定一些約束條件， 而文中的適應(yīng)度函數(shù)只考慮了固定的幾種約束條件， 如果要加入新的約束條件， 則需要對(duì)適應(yīng)度函數(shù)進(jìn)行更改， 使得排課系統(tǒng)的可維護(hù)性降低. 現(xiàn)有的一些走班排課系統(tǒng)， 如科大訊飛的智能排課系統(tǒng)， 也是對(duì)一些學(xué)校復(fù)雜性的個(gè)性化需求缺少有效的解決方案， 比如長(zhǎng)短課程、導(dǎo)師班以及校本課程走班的安排等.

本文圍繞上述這些問(wèn)題設(shè)計(jì)了走班排課問(wèn)題的求解方法， 針對(duì)走班課程， 提出了走班組合的概念，給出了自動(dòng)劃分教學(xué)班的方法： 針對(duì)長(zhǎng)課時(shí)課程（長(zhǎng)課時(shí)課程占用1.5 個(gè)課時(shí)）， 為避免和正常課時(shí)課程的安排相沖突， 將兩節(jié)長(zhǎng)課時(shí)課程安排在相鄰的授課時(shí)段; 針對(duì)走班排課問(wèn)題， 建立排課模型， 使用改進(jìn)的遺傳算法解決排課問(wèn)題， 在生成初始種群時(shí)， 不考慮課表的沖突， 打破了初始種群中個(gè)體應(yīng)當(dāng)為可行解的約束; 另外在變異算子中創(chuàng)新性地加入了基因編輯的思想， 以一定概率自動(dòng)定位課表中的一次資源沖突并消除沖突， 并有針對(duì)性地在適應(yīng)度函數(shù)中引入懲罰度的設(shè)計(jì). 實(shí)例驗(yàn)證表明，本文算法在實(shí)際的走班排課問(wèn)題中取得了很好的效果.

1 走班排課的基本問(wèn)題

1.1 問(wèn)題描述

排課問(wèn)題屬于調(diào)度問(wèn)題的研究范疇， 其核心任務(wù)是將課程、班級(jí)、教師、教室資源不沖突地安排在各個(gè)授課時(shí)間段， 并保證其能夠滿足教務(wù)老師事先設(shè)定好的各種約束條件， 且使結(jié)果達(dá)到最優(yōu)或者近似最優(yōu). 而走班制教學(xué)模式的引入， 使排課問(wèn)題變得更加復(fù)雜， 排課的約束條件進(jìn)一步增多， 學(xué)校教學(xué)資源匱乏的現(xiàn)象進(jìn)一步凸顯.

目前大多數(shù)實(shí)行走班制的高中學(xué)校采用的走班模式是， 主課和藝體課固定在行政班上課， 選考科目進(jìn)行走班[13]. 因此本文使用的排課模式是， 英語(yǔ)、數(shù)學(xué)、語(yǔ)文等主課以及藝體課固定在行政班上課，選考課程以及校本課程進(jìn)行走班安排.

5 結(jié)束語(yǔ)

隨著新高考政策在全國(guó)范圍內(nèi)的推廣， 走班制教學(xué)模式逐漸代替了傳統(tǒng)的行政班教學(xué)模式， 而走班制教學(xué)模式的引入， 使得排課的約束條件大大增加， 傳統(tǒng)的排課方案已經(jīng)不適用于解決走班模式下的排課問(wèn)題， 而單純的手動(dòng)排課不僅費(fèi)時(shí)費(fèi)力， 且難以滿足學(xué)生個(gè)性化教育的需求， 因此需要一個(gè)切實(shí)可行的智能排課方案來(lái)解決走班排課問(wèn)題. 本文立足于上海市實(shí)驗(yàn)性示范性高中背景下的學(xué)校的實(shí)際需求來(lái)解決走班排課問(wèn)題， 創(chuàng)新點(diǎn)主要有以下3 個(gè)方面： ①課表中加入了長(zhǎng)課時(shí)課程和走班課程組合的安排， 針對(duì)走班課程提出了自動(dòng)劃分教學(xué)班組合的方法， 每一個(gè)走班組合內(nèi)部的教學(xué)班相互不沖突; ②遺傳算法中的遺傳算子創(chuàng)新性地引入了基因編輯思想， 以一定概率去自動(dòng)定位課表中的一次沖突并消除該沖突， 大大提升了遺傳算法的進(jìn)化效果; ③針對(duì)本文提出的遺傳算法的初始種群生成策略， 在適應(yīng)度函數(shù)中引入了懲罰度設(shè)計(jì)， 也在一定程度上提升了遺傳算法的進(jìn)化效果.

測(cè)試結(jié)果表明， 本文算法能夠高效合理地求解走班排課問(wèn)題， 在不考慮課時(shí)設(shè)置錯(cuò)誤的情況下，算法能夠消除所有的資源沖突并在最大程度上符合教務(wù)老師設(shè)定的各種排課約束條件， 極大降低了教務(wù)老師在課表編排上所花費(fèi)的時(shí)間精力， 滿足了學(xué)生個(gè)性化教育的需求， 該排課方法實(shí)踐起來(lái)也更為簡(jiǎn)單且通用性良好， 具有很好的實(shí)際應(yīng)用意義.

[ 參 考 文 獻(xiàn)]

[ 1 ] 夏永庚， 朱琴. 走班制背景下高中班主任德育工作的挑戰(zhàn)與應(yīng)對(duì) [J]. 現(xiàn)代基礎(chǔ)教育研究， 2019， 33（1）： 215-220.

[ 2 ] GOTLIEB C C. The construction of class-teacher timetables [J]. Communications of the ACM， 1962， 5（6）： 73-77.

[ 3 ]EVEN S， ITAI A， SHAMIR A. On the complexity of time table and multi-commodity flow problems [C]//16th Annual Symposium onFoundations of Computer Science （SFCS 1975）. IEEE， 1975： 184-193. DOI： 10.1109/SFCS.1975.21.

[ 4 ]張艷紅， 王玲玲， 騰東興. 基于空間模型和遺傳算法的高校排課系統(tǒng) [J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2015， 24（9）： 49-55. DOI： 10.3969/j.issn.1003-3254.2015.09.008.

[ 5 ] 袁俊毅. 基于遺傳算法的高校教務(wù)排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn) [D]. 長(zhǎng)沙： 湖南大學(xué)， 2017.

[ 6 ] 姜婧， 白似雪. 遺傳算法的改進(jìn)及其在排課問(wèn)題中的應(yīng)用 [J]. 南昌大學(xué)學(xué)報(bào)（理科版）， 2018， 42（4）： 388-392.

[ 7 ] 唐環(huán)， 高健. 在中學(xué)排課問(wèn)題中實(shí)用的模擬退火算法應(yīng)用 [J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2017， 26（10）： 225-230.

[ 8 ]THEPPHAKORN T， PONGCHAROEN P， HICKS C. An ant colony based timetabling tool [J]. International Journal of ProductionEconomics， 2014， 149： 131-144. DOI： 10.1016/j.ijpe.2013.04.026.

[ 9 ] 張媛， 祁蘭. 基于禁忌搜索的排課系統(tǒng)的設(shè)計(jì) [J]. 電子設(shè)計(jì)工程， 2016， 24（22）： 71-73.

[10]FONG C W， ASMUNI H， LAM W S， et al. A novel hybrid swarm based approach for curriculum based course timetabling problem[C]//2014 IEEE Congress on Evolutionary Computation （CEC）. IEEE， 2014： 544-550.

[11]王衛(wèi)紅， 李文瓊. 基于改進(jìn)遺傳算法的高中走班制排課算法 [J]. 浙江工業(yè)大學(xué)學(xué)報(bào)， 2016， 44（6）： 601-607， 670. DOI： 10.3969/j.issn.1006-4303.2016.06.002.

[12] 陳璐， 王秀. 改進(jìn)遺傳算法求解走班制下的排課問(wèn)題 [J]. 計(jì)算機(jī)工程與應(yīng)用， 2019， 55（6）： 218-224.

[13] 馬輝輝. 走班制的實(shí)施與注意問(wèn)題 [J]. 教育與教學(xué)研究， 2016， 30（2）： 99-103. DOI： 10.3969/j.issn.1674-6120.2016.02.019.

[14] 張貴軍， 陳安， 胡俊. 基于蒙特卡洛遺傳算法的排課問(wèn)題研究 [J]. 實(shí)驗(yàn)技術(shù)與管理， 2019， 36（3）： 170-174.

[15] 馮智莉， 易國(guó)洪， 李普山， 等. 并行化遺傳算法研究綜述 [J]. 計(jì)算機(jī)應(yīng)用與軟件， 2018， 35（11）： 1-7， 80.

[16] 葛繼科， 邱玉輝， 吳春明， 等. 遺傳算法研究綜述 [J]. 計(jì)算機(jī)應(yīng)用研究， 2008， 10： 2911-2916. DOI： 10.3969/j.issn.1001-3695.2008.10.008.

[17] 王贊， 樊向宇， 鄒雨果， 等. 一種基于遺傳算法的多缺陷定位方法 [J]. 軟件學(xué)報(bào)， 2016， 27（4）： 879-900.

[18] 雷英杰， 張善文. MATLAB遺傳算法工具箱及應(yīng)用 [M]. 西安： 西安電子科技大學(xué)出版社， 2014.

[19]董玉鎖， 賀波， 尹迎， 等. 利用改進(jìn)遺傳算法破解排課難題 [J]. 中國(guó)教育技術(shù)裝備， 2018（1）： 16-19. DOI： 10.3969/j.issn.1671-489X.2018.01.016.

（責(zé)任編輯： 李 藝）