新高考體制下運(yùn)用改進(jìn)粒子群算法的排課算法

趙瑩帝，孫光民，周青昱

（1. 北京工業(yè)大學(xué) 信息學(xué)部，北京 100124；2. 北京科技大學(xué) 自動(dòng)化學(xué)院，北京 100091）

0 引言

學(xué)校的教育管理部門在整個(gè)教學(xué)過程中起著重要的作用，其中排課工作是最基礎(chǔ)也是工作量最大的一項(xiàng)任務(wù)。隨著高校不斷擴(kuò)招，各高校都面臨教學(xué)資源緊張的問題。對(duì)于教務(wù)處來說，高效地做出一份合理的高質(zhì)量的課表是困難的。所以根據(jù)實(shí)際教務(wù)工作實(shí)現(xiàn)計(jì)算機(jī)的智能優(yōu)化排課勢在必行。

排課問題已經(jīng)被證明是 NP完全問題。最優(yōu)化排課方案的本質(zhì)即找到所有排課要素之間的對(duì)應(yīng)關(guān)系，并尋找所有存在的對(duì)應(yīng)關(guān)系的最優(yōu)組合。排課問題面臨的主要難點(diǎn)就是在教學(xué)資源緊張的情況下實(shí)現(xiàn)最優(yōu)化配置。國內(nèi)外很多學(xué)者[1-14]都對(duì)最優(yōu)化排課問題進(jìn)行了研究，并順利解決原始排課問題。

有部分學(xué)者[1-4]使用模擬退火算法解決原始排課問題。有學(xué)者[1]提出改進(jìn)的模擬退火排課算法，通過記憶當(dāng)前最優(yōu)解避免最優(yōu)解遺失，并給出可變步長的溫度更新函數(shù)。有學(xué)者[2]通過設(shè)定閾值判斷收斂后的結(jié)果是否符合要求，如果不在規(guī)定范圍內(nèi)則認(rèn)為進(jìn)入局部最優(yōu)，此時(shí)接受差解，并繼續(xù)進(jìn)行模擬退火過程尋找最優(yōu)課表。也有學(xué)者[3]側(cè)重對(duì)比大學(xué)和中學(xué)排課的不同，并分三個(gè)階段進(jìn)行模擬退火實(shí)現(xiàn)中學(xué)排課以減少算法運(yùn)行時(shí)間。還有學(xué)者[4]基于局部狀態(tài)計(jì)算，對(duì)臨近代變化量求目標(biāo)函數(shù)，減小計(jì)算量以解決排課問題。目前，還沒有學(xué)者運(yùn)用模擬退火算法解決新高考排課問題。

有部分學(xué)者[5-12]使用粒子群算法解決原始排課問題。有學(xué)者[5]級(jí)聯(lián)粒子群算法和前行檢測算法，比粒子群算法耗時(shí)長，但效果有改善。有學(xué)者[6-7]依靠權(quán)重進(jìn)行新狀態(tài)的選取，避免早熟收斂和局部最優(yōu)解徘徊現(xiàn)象。也有學(xué)者[8]結(jié)合容易陷入局部最優(yōu)但收斂速度快的粒子群算法和全局收斂性好但收斂速度慢的魚群算法，得到具有較快局部搜索能力和較強(qiáng)全局收斂能力的混合優(yōu)化算法，以解決原始排課問題。目前，還沒有學(xué)者用粒子群算法解決新高考排課問題。

普遍教學(xué)資源緊張的中學(xué)排課問題有以下特點(diǎn)：第一，時(shí)間片較多，課表飽和易沖突。第二，課間短校園小，執(zhí)行走班制課表較困難。第三，教室靈活性差，每個(gè)行政班一個(gè)教室，副科特殊教室數(shù)量少且專科專用。第四，某科中學(xué)教師每學(xué)期都只能教授該門課程，且不能同時(shí)教多個(gè)科目。在這種情況下實(shí)現(xiàn)最優(yōu)化排課是有難度的，新高考體制下的最優(yōu)化排課問題更具有挑戰(zhàn)性。

新高考政策為“3+3”模式，即語數(shù)英加從“史地政物化生”六個(gè)科目中選取的三個(gè)科目。學(xué)校根據(jù)自身情況實(shí)施適合自己的特色走班制，目前走班制分為四種：不走班、小走班、大走班、全走班。考生可根據(jù)自身情況自由選取“史地政物化生”中的三個(gè)科目，不再受限于只能選文科或者理科。這樣提高了學(xué)生選擇的自由度，可以最大程度發(fā)揮學(xué)生的特點(diǎn)。學(xué)生選擇自己擅長的三個(gè)科目參加高考以后，剩余的三科只需要通過會(huì)考即可。但同時(shí)帶來的問題就是學(xué)校需要為他們開設(shè)不同選課模式的班級(jí)，并需要將“史地政物化生”的每科教師分成兩組進(jìn)行不同難易程度和不同教學(xué)計(jì)劃備課，大幅度增加了學(xué)校教務(wù)處的排課任務(wù)量。

采用行政班制度進(jìn)行排課有以下優(yōu)點(diǎn)：第一，學(xué)生有固定教室，除副科外學(xué)生無需換教室上課，節(jié)約課間時(shí)間，減少課間換教室的遲到和安全問題。第二，有利于班級(jí)文化建設(shè)，也便于班主任管理。第三，每個(gè)班對(duì)應(yīng)固定的教師，有利于教學(xué)計(jì)劃同步推進(jìn)。第四，預(yù)防換教室?guī)淼乃饺宋锲繁黄茐牡葐栴}。

與原始排課不同，新高考體制下排課有更多約束條件。新高考體制下排課難點(diǎn)在于教學(xué)資源最優(yōu)化分配。第一，“史地政物化生”的教師應(yīng)分為兩組，因?yàn)闀?huì)考與高考要求不同，某教師不能教不同難度的相同科目，否則需要準(zhǔn)備多份教案。第二，當(dāng)六選三涉及的某教師課表發(fā)生沖突時(shí)，如果沒有班級(jí)需要對(duì)應(yīng)的該科目教師，該教師便處于課表非飽和狀態(tài)，同時(shí)還需引入該科目的另外一名教師以解決沖突。故實(shí)現(xiàn)教師數(shù)最少的新高考體制下排課是有難度的。第三，約束條件的增加會(huì)給優(yōu)化算法的初始解產(chǎn)生和優(yōu)化效率帶來挑戰(zhàn)。

針對(duì)新高考政策下的排課問題，目前沒有較成熟的實(shí)現(xiàn)方法。為了解決中學(xué)教學(xué)資源緊張的新高考體制下的排課問題，運(yùn)用改進(jìn)的模擬退火算法和改進(jìn)的粒子群算法，將確定解作為優(yōu)化算法的輸入，用監(jiān)督矩陣控制優(yōu)化過程中課表始終滿足硬約束條件和軟約束條件，并使課表不斷向用戶自定義約束條件方向變化。分別使用改進(jìn)的模擬退火算法和改進(jìn)的粒子群算法實(shí)現(xiàn)新高考體制下的排課，并進(jìn)行對(duì)比。最終，改進(jìn)的粒子群排課算法可得到無沖突、教師數(shù)最少、教室數(shù)最少、教學(xué)計(jì)劃同步推進(jìn)的、符合新高考體制的最優(yōu)化課表。

1 運(yùn)用改進(jìn)粒子群算法解決新高考排課問題

目前，粒子群算法被廣泛應(yīng)用于最優(yōu)化問題。粒子群算法和模擬退火算法相似，從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)度評(píng)價(jià)解的質(zhì)量。同時(shí)，粒子群算法是一種并行算法，尋優(yōu)效率高。將確定解作為改進(jìn)粒子群算法的輸入，解決了新高考體制下排課問題和滿足硬約束條件和軟約束條件的隨機(jī)初始課表難產(chǎn)生問題，并得到優(yōu)化后的高質(zhì)量課表。

改進(jìn)的粒子群算法進(jìn)行新高考體制下排課的算法流程如圖1所示。

圖1 改進(jìn)粒子群算法進(jìn)行新高考體制下排課流程圖Fig.1 Flow chart of course arrangement under the new college entrance examination system by improved particle swarm optimization algorithm

解決排課問題需滿足不同約束條件。設(shè)置硬約束條件為：第一，無兩名教師同一時(shí)間進(jìn)入同一班級(jí)授課。第二，無一名教師同一時(shí)間需要到兩個(gè)班級(jí)授課。滿足硬約束條件的課表才具有可行性。設(shè)置的軟約束條件有三點(diǎn)：第一，滿足教師總數(shù)最少。第二，滿足教室數(shù)最少。第三，滿足每天每科目最多一節(jié)課。滿足軟約束條件的課表具有實(shí)際應(yīng)用價(jià)值。設(shè)置評(píng)分函數(shù)來衡量用戶自定義約束條件的滿足程度。課表評(píng)分越高，則越滿足用戶自定義約束條件。

最優(yōu)化排課的本質(zhì)就是尋找一組最優(yōu)的排課要素分配方案，使課表一定滿足硬約束條件和軟約束條件的同時(shí)盡可能滿足用戶自定義約束條件。排課要素主要分為以下五點(diǎn)：時(shí)間、班級(jí)、教師、教室、課程。通過分析，簡化了排課要素。每名中學(xué)教師只能教授一個(gè)科目，故課程信息等于教師信息。采用行政班進(jìn)行新高考體制下的排課，除副科外每個(gè)班級(jí)學(xué)生都在本班教室上課，每個(gè)副科都有單獨(dú)教室供所有班級(jí)錯(cuò)開時(shí)間段使用。將新高考體制下的排課要素簡化為三個(gè)：班級(jí)、教師、時(shí)間。

針對(duì)簡化后的排課要素，對(duì)課表信息進(jìn)行編碼，即考慮班級(jí)、教師和時(shí)間。時(shí)間片是確定且固定的，即每個(gè)班每周所需總課時(shí)數(shù)相同且不變。班級(jí)總數(shù)為不同選課模式班級(jí)數(shù)量的總和，需要根據(jù)學(xué)校實(shí)際情況進(jìn)行計(jì)算。教師總數(shù)和不同科目教師數(shù)由不同選課模式班級(jí)數(shù)量決定。

時(shí)間和班級(jí)只包含單一信息可順序編號(hào)，教師信息為復(fù)合信息需要同時(shí)包含科目號(hào)和該科目的教師號(hào)。采取的教師編碼方式為：教師編號(hào)=科目號(hào)*group+教師組內(nèi)號(hào)，其中科目號(hào)為所有科目順序編號(hào)后確定的唯一編號(hào)，group為大于每個(gè)單科教師最大數(shù)量的確定值，教師組內(nèi)號(hào)為教師在其所教授科目組中的具體編號(hào)。由于 group為預(yù)設(shè)定的值，當(dāng)同時(shí)確定教師的科目號(hào)和教師組內(nèi)號(hào)時(shí)，即可確定唯一的教師。對(duì)教師編號(hào)進(jìn)行順序編號(hào)，科目號(hào)可通過教師編號(hào)除以 group得到，教師組內(nèi)號(hào)可通過教師編號(hào)對(duì)group取余得到。

大部分學(xué)者在處理原始排課問題時(shí)，采用二進(jìn)制或十進(jìn)制數(shù)串進(jìn)行排課要素?cái)?shù)據(jù)存儲(chǔ)，不同字段表示不同排課要素。也有學(xué)者[16]使用矩陣進(jìn)行排課要素的存儲(chǔ)，這樣更直觀，也更便于約束條件的控制。學(xué)者劉騰[16]使用二維矩陣存儲(chǔ)排課要素的對(duì)應(yīng)關(guān)系，行和列分別為“時(shí)間”和“課程-教師-班級(jí)”，矩陣中存儲(chǔ)“教室”信息。使用二維矩陣對(duì)課表信息進(jìn)行存儲(chǔ)。因?yàn)椴煌x課模式班級(jí)數(shù)量決定了班級(jí)總數(shù)和教師總數(shù)，同時(shí)時(shí)間片是預(yù)設(shè)定的。故將“時(shí)間”作為不同矩陣的列，將“班級(jí)”作為班級(jí)課表矩陣的行，將“教師”作為教師課表矩陣的行。班級(jí)課表矩陣中存放教師編號(hào)，教師課表矩陣中存放班級(jí)編號(hào)。因?yàn)榘嗉?jí)課表矩陣和教師課表矩陣均包含某組課表的全部信息，所以它們?cè)谡n表產(chǎn)生新解過程中可互為監(jiān)督矩陣。

粒子群算法的輸入一般為隨機(jī)解，但滿足教師數(shù)最少的新高考體制下的隨機(jī)課表難產(chǎn)生。同時(shí)，在粒子群算法運(yùn)行過程中去控制課表滿足不同約束條件來獲取最優(yōu)課表是有風(fēng)險(xiǎn)的。將確定的初始課表作為改進(jìn)粒子群算法的輸入，干擾優(yōu)化方向，嘗試獲取肯定滿足硬約束條件和軟約束條件的、較大程度滿足用戶自定義約束條件的、具有實(shí)際應(yīng)用價(jià)值的最優(yōu)課表。

規(guī)定每班每周的授課計(jì)劃為：語數(shù)英各5節(jié)課，六選三選中的科目各4節(jié)課，六選三未選中的科目各2節(jié)課，自習(xí)課2節(jié)課，音樂、體育、美術(shù)、計(jì)算機(jī)、閱讀這五個(gè)副科每科1節(jié)課?！?+3”涉及的教師可帶2或3個(gè)班，六選三未選中的教師需帶4個(gè)班。副科采取合班制，每名副科教師每周需上 5節(jié)課，即帶10個(gè)班。自習(xí)課無教師，每班學(xué)生在自己班教室上課。

先為不同類型科目組設(shè)定固定的時(shí)間段，即設(shè)置滿足每科目每天最多一節(jié)課的排課模板。在排課時(shí)，如果不同班級(jí)需要同一教師授課，在相同課時(shí)數(shù)的科目間順序輪轉(zhuǎn)以錯(cuò)開教師授課時(shí)間段。按課時(shí)數(shù)劃分不同輪轉(zhuǎn)組分別為：語數(shù)英、六選三選中的科目、六選三未選中的科目和自習(xí)、五個(gè)副科。在不同輪轉(zhuǎn)組中，組內(nèi)不同科目數(shù)大于等于組內(nèi)單科教師所需最大帶班數(shù)，不涉及模板增設(shè)問題。但副科采用合班制，五個(gè)副科輪轉(zhuǎn)只有5種情況且由于教學(xué)資源緊張只設(shè)置一組副科特殊教室，故班級(jí)數(shù)量大于10時(shí)需要增加模板。為保證副科盡量被安排在下午，班級(jí)總數(shù)不宜大于40。六選三科目和自習(xí)的時(shí)間段固定，按科目時(shí)間片調(diào)整語數(shù)英和副科對(duì)應(yīng)的時(shí)間段，可以分別設(shè)置不同模板。每十個(gè)班使用同一個(gè)模板，需要考慮模板交界處的沖突問題。當(dāng)語數(shù)英教師帶三個(gè)班時(shí)，可能會(huì)出現(xiàn)同一組教師跨模板排課情況。如果用W表示副科，X表示語文，Y表示數(shù)學(xué)，Z表示英語，每個(gè)科目對(duì)應(yīng)課表中的五節(jié)課，則四組模板按順序分別設(shè)置為：XYZW，WYZX，YWZX，ZXWY。在使用模板的基礎(chǔ)上進(jìn)行排課，順序交換課時(shí)數(shù)相同的科目，即可滿足教師數(shù)最少和教室數(shù)最少。

設(shè)置的評(píng)分函數(shù)僅用于測試改進(jìn)的粒子群算法的課表尋優(yōu)能力，也可以設(shè)置其他的評(píng)分函數(shù)。使用評(píng)分函數(shù)測試課表的用戶自定義約束條件的滿足程度，觀察最終課表是否可以向預(yù)期方向變化。設(shè)定語數(shù)英每天從早到晚8個(gè)時(shí)間段的得分為8到1，副科和自習(xí)從早到晚不同時(shí)間段得分為1到8，“史地政物化生”科目不設(shè)置得分。當(dāng)系統(tǒng)評(píng)分高時(shí)，語數(shù)英分布于早上，副科和自習(xí)分布于晚上，“史地政物化生”分布于一天的中間時(shí)段。遍歷班級(jí)課表二維矩陣所有時(shí)間段，將得分求和后，將分?jǐn)?shù)先除以班級(jí)數(shù)，除以159，再乘以100，即可得到歸一化后的百分制評(píng)分。關(guān)于159的闡述：得分最高的情況為語數(shù)英分布于每天的前三節(jié)課，副科和自習(xí)分布于下午第4節(jié)課5個(gè)時(shí)間段以及下午第3節(jié)課2個(gè)時(shí)間段。故得分最高情況為159，并非22*8。

不同優(yōu)化算法進(jìn)行原始排課時(shí)迭代過程緩慢是因?yàn)樵谝淮蔚行枰粩喾磸?fù)產(chǎn)生新解直至無沖突為止，這導(dǎo)致新解產(chǎn)生的效率低下。采用的新解產(chǎn)生機(jī)制是預(yù)設(shè)定交換次數(shù)為10，先隨機(jī)到某個(gè)班級(jí)再交換該班級(jí)的某兩節(jié)課，如果破壞硬約束條件和軟約束條件則不交換。在交換過程中，要注意幾點(diǎn)：第一，使用班級(jí)課表矩陣和教師課表矩陣互相監(jiān)督，使課表恒滿足硬約束條件和軟約束條件成立。第二，設(shè)置副科教室監(jiān)督矩陣，保證每科目每一時(shí)間段只有一名教師帶班上課，從而保證教室數(shù)最少。第三，不改變“班級(jí)-教師”對(duì)應(yīng)關(guān)系以保證教師數(shù)最少。第四，如果交換后某科目在同一天內(nèi)出現(xiàn)兩次，則取消交換。第五，自習(xí)沒有教師，無需更新教師課表矩陣。第六，副科采用合班制，每次涉及副科交換應(yīng)同時(shí)交換一組合班中另外一個(gè)班的對(duì)應(yīng)位置兩節(jié)課，并保證兩個(gè)班的換課均不破壞硬約束條件和軟約束條件。

每次新解產(chǎn)生后，需及時(shí)更新班級(jí)課表矩陣和教師課表矩陣。所采用的新解產(chǎn)生機(jī)制效率高，并且交換固定次數(shù)即保證新解一定可以快速產(chǎn)生。將交換次數(shù)設(shè)為適宜的值，可保證改進(jìn)粒子群算法運(yùn)行初期每一代均有新解產(chǎn)生，同時(shí)運(yùn)行后期收斂速度適宜。

將30個(gè)相同的確定解作為初始種群，在種群更新過程中種群中每個(gè)個(gè)體各自歷經(jīng)一次新解產(chǎn)生機(jī)制，每一代新種群產(chǎn)生后對(duì)種群中每個(gè)個(gè)體進(jìn)行單獨(dú)評(píng)分，更新歷史最優(yōu)解和當(dāng)前代最優(yōu)解，淘汰每一代種群中評(píng)分最低的10個(gè)個(gè)體，其中5個(gè)用當(dāng)前代最優(yōu)解代替，另外5個(gè)用歷史最優(yōu)解代替。當(dāng)歷史最優(yōu)解連續(xù) 1000代不發(fā)生變化則判定改進(jìn)的粒子群算法終止。

2 實(shí)驗(yàn)結(jié)果和分析

針對(duì)北京市某高校的實(shí)際情況，對(duì)25個(gè)班級(jí)進(jìn)行新高考體制下排課。其中“物化生”模式班級(jí)數(shù)量為6，“物生史”模式班級(jí)數(shù)量為5，“物化地”和“物生政”模式班級(jí)數(shù)量為 3，“物史政”和“史地政”模式班級(jí)數(shù)量為2，“物地政”、“化生地”、“生史政”、“化史政”模式班級(jí)數(shù)量均為1?！?+3”教師均帶三個(gè)班級(jí)。幾乎所有班級(jí)選課模式中都與物理有關(guān)，原因是考生所選三科中有物理才可申報(bào)較多數(shù)大學(xué)。

進(jìn)行實(shí)驗(yàn)時(shí)，使用兩種不同優(yōu)化算法分別實(shí)現(xiàn)新高考體制下的排課并對(duì)比兩種算法的優(yōu)劣。在控制變量方面，兩種優(yōu)化算法使用相同的確定解作為優(yōu)化算法輸入、相同的新解產(chǎn)生機(jī)制、相同的評(píng)分函數(shù)以及相同的算法收斂條件。同時(shí)，設(shè)置最大算法運(yùn)行代數(shù)為10000次。

進(jìn)行實(shí)驗(yàn)后，兩種改進(jìn)優(yōu)化算法的排課效果和排課速度各有特點(diǎn)，歷史最優(yōu)課表評(píng)分隨算法運(yùn)行代數(shù)變化對(duì)比如圖2所示，收斂速度隨算法運(yùn)行代數(shù)變化對(duì)比如圖3所示。

實(shí)驗(yàn)結(jié)果表明，所用改進(jìn)的粒子群算法在新高考體制下排課可得到高質(zhì)量的課表。相比于作為優(yōu)化算法輸入的確定解，兩種優(yōu)化算法均可提升課表的評(píng)分。改進(jìn)粒子群算法具有較強(qiáng)的課表尋優(yōu)能力，改進(jìn)模擬退火算法運(yùn)行時(shí)間較短。在實(shí)驗(yàn)過程中，改進(jìn)模擬退火算法的參數(shù)很難調(diào)整，經(jīng)常出現(xiàn)收斂速度過快或課表當(dāng)前代評(píng)分始終震蕩問題。

所用改進(jìn)的粒子群算法的輸出課表評(píng)分高于80，與確定解相比有明顯提升。這說明最終輸出課表在一定滿足硬約束條件和軟約束條件基礎(chǔ)上，基本可完全滿足用戶自定義約束條件。改進(jìn)粒子群算法輸出的班級(jí)課表和教師課表部分結(jié)果分別如圖 4和圖5所示，其中六選三選中和未選中的相同科目分別用A、B來區(qū)分。

圖2 當(dāng)代最優(yōu)課表評(píng)分隨遺傳代數(shù)變化折線圖Fig.2 Broken line chart of contemporary optimal schedule score with the change of genetic algebra

圖3 收斂速度隨遺傳代數(shù)變化折線圖Fig.3 The change of convergence rate with genetic algebra

圖4 改進(jìn)粒子群算法排課的班級(jí)課表部分結(jié)果Fig.4 Some results of class schedule based on improved particle swarm optimization

圖5 改進(jìn)粒子群算法排課的教師課表部分結(jié)果Fig.5 Some results of teachers' timetable based on improved particle swarm optimization

3 結(jié)論

（1）文中所采用的改進(jìn)粒子群算法拆分了變化更新的動(dòng)態(tài)過程，將其拆分成淘汰機(jī)制和用歷史最優(yōu)解、當(dāng)前代最優(yōu)解替代種群中劣質(zhì)個(gè)體，實(shí)現(xiàn)種群向理想方向運(yùn)動(dòng)，提高算法運(yùn)行效率，減少算法運(yùn)行時(shí)間。

（2）文中使用兩種改進(jìn)的優(yōu)化算法解決新高考體制下的排課問題，并對(duì)比兩種優(yōu)化算法的特點(diǎn)。將確定解作為兩種優(yōu)化算法的輸入，解決新高考體制下隨機(jī)課表難生成的問題，同時(shí)深刻挖掘排課問題的不同要素大幅度減少排課時(shí)間。

（3）希望本文可以給其他解決新高考排課問題的學(xué)者帶來參考意義，也可以給使用粒子群算法實(shí)現(xiàn)優(yōu)化問題的學(xué)者帶來新的改進(jìn)思路。同時(shí)希望本文可以給解決受眾廣的新高考排課問題帶來貢獻(xiàn)，為解決其他NP完全問題和多約束時(shí)間調(diào)度問題提供幫助。