新高考體制下運用改進粒子群算法的排課算法

趙瑩帝，孫光民，周青昱

（1. 北京工業大學 信息學部，北京 100124；2. 北京科技大學 自動化學院，北京 100091）

0 引言

學校的教育管理部門在整個教學過程中起著重要的作用，其中排課工作是最基礎也是工作量最大的一項任務。隨著高校不斷擴招，各高校都面臨教學資源緊張的問題。對于教務處來說，高效地做出一份合理的高質量的課表是困難的。所以根據實際教務工作實現計算機的智能優化排課勢在必行。

排課問題已經被證明是 NP完全問題。最優化排課方案的本質即找到所有排課要素之間的對應關系，并尋找所有存在的對應關系的最優組合。排課問題面臨的主要難點就是在教學資源緊張的情況下實現最優化配置。國內外很多學者[1-14]都對最優化排課問題進行了研究，并順利解決原始排課問題。

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

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

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

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

采用行政班制度進行排課有以下優點：第一，學生有固定教室，除副科外學生無需換教室上課，節約課間時間，減少課間換教室的遲到和安全問題。第二，有利于班級文化建設，也便于班主任管理。第三，每個班對應固定的教師，有利于教學計劃同步推進。第四，預防換教室帶來的私人物品被破壞等問題。

與原始排課不同，新高考體制下排課有更多約束條件。新高考體制下排課難點在于教學資源最優化分配。第一，“史地政物化生”的教師應分為兩組，因為會考與高考要求不同，某教師不能教不同難度的相同科目，否則需要準備多份教案。第二，當六選三涉及的某教師課表發生沖突時，如果沒有班級需要對應的該科目教師，該教師便處于課表非飽和狀態，同時還需引入該科目的另外一名教師以解決沖突。故實現教師數最少的新高考體制下排課是有難度的。第三，約束條件的增加會給優化算法的初始解產生和優化效率帶來挑戰。

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

1 運用改進粒子群算法解決新高考排課問題

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

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

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

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

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

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

時間和班級只包含單一信息可順序編號，教師信息為復合信息需要同時包含科目號和該科目的教師號。采取的教師編碼方式為：教師編號=科目號*group+教師組內號，其中科目號為所有科目順序編號后確定的唯一編號，group為大于每個單科教師最大數量的確定值，教師組內號為教師在其所教授科目組中的具體編號。由于 group為預設定的值，當同時確定教師的科目號和教師組內號時，即可確定唯一的教師。對教師編號進行順序編號，科目號可通過教師編號除以 group得到，教師組內號可通過教師編號對group取余得到。

大部分學者在處理原始排課問題時，采用二進制或十進制數串進行排課要素數據存儲，不同字段表示不同排課要素。也有學者[16]使用矩陣進行排課要素的存儲，這樣更直觀，也更便于約束條件的控制。學者劉騰[16]使用二維矩陣存儲排課要素的對應關系，行和列分別為“時間”和“課程-教師-班級”，矩陣中存儲“教室”信息。使用二維矩陣對課表信息進行存儲。因為不同選課模式班級數量決定了班級總數和教師總數，同時時間片是預設定的。故將“時間”作為不同矩陣的列，將“班級”作為班級課表矩陣的行，將“教師”作為教師課表矩陣的行。班級課表矩陣中存放教師編號，教師課表矩陣中存放班級編號。因為班級課表矩陣和教師課表矩陣均包含某組課表的全部信息，所以它們在課表產生新解過程中可互為監督矩陣。

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

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

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

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

不同優化算法進行原始排課時迭代過程緩慢是因為在一次迭代中需要不斷反復產生新解直至無沖突為止，這導致新解產生的效率低下。采用的新解產生機制是預設定交換次數為10，先隨機到某個班級再交換該班級的某兩節課，如果破壞硬約束條件和軟約束條件則不交換。在交換過程中，要注意幾點：第一，使用班級課表矩陣和教師課表矩陣互相監督，使課表恒滿足硬約束條件和軟約束條件成立。第二，設置副科教室監督矩陣，保證每科目每一時間段只有一名教師帶班上課，從而保證教室數最少。第三，不改變“班級-教師”對應關系以保證教師數最少。第四，如果交換后某科目在同一天內出現兩次，則取消交換。第五，自習沒有教師，無需更新教師課表矩陣。第六，副科采用合班制，每次涉及副科交換應同時交換一組合班中另外一個班的對應位置兩節課，并保證兩個班的換課均不破壞硬約束條件和軟約束條件。

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

將30個相同的確定解作為初始種群，在種群更新過程中種群中每個個體各自歷經一次新解產生機制，每一代新種群產生后對種群中每個個體進行單獨評分，更新歷史最優解和當前代最優解，淘汰每一代種群中評分最低的10個個體，其中5個用當前代最優解代替，另外5個用歷史最優解代替。當歷史最優解連續 1000代不發生變化則判定改進的粒子群算法終止。

2 實驗結果和分析

針對北京市某高校的實際情況，對25個班級進行新高考體制下排課。其中“物化生”模式班級數量為6，“物生史”模式班級數量為5，“物化地”和“物生政”模式班級數量為 3，“物史政”和“史地政”模式班級數量為2，“物地政”、“化生地”、“生史政”、“化史政”模式班級數量均為1。“3+3”教師均帶三個班級。幾乎所有班級選課模式中都與物理有關，原因是考生所選三科中有物理才可申報較多數大學。

進行實驗時，使用兩種不同優化算法分別實現新高考體制下的排課并對比兩種算法的優劣。在控制變量方面，兩種優化算法使用相同的確定解作為優化算法輸入、相同的新解產生機制、相同的評分函數以及相同的算法收斂條件。同時，設置最大算法運行代數為10000次。

進行實驗后，兩種改進優化算法的排課效果和排課速度各有特點，歷史最優課表評分隨算法運行代數變化對比如圖2所示，收斂速度隨算法運行代數變化對比如圖3所示。

實驗結果表明，所用改進的粒子群算法在新高考體制下排課可得到高質量的課表。相比于作為優化算法輸入的確定解，兩種優化算法均可提升課表的評分。改進粒子群算法具有較強的課表尋優能力，改進模擬退火算法運行時間較短。在實驗過程中，改進模擬退火算法的參數很難調整，經常出現收斂速度過快或課表當前代評分始終震蕩問題。

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

圖2 當代最優課表評分隨遺傳代數變化折線圖Fig.2 Broken line chart of contemporary optimal schedule score with the change of genetic algebra

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

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

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

3 結論

（1）文中所采用的改進粒子群算法拆分了變化更新的動態過程，將其拆分成淘汰機制和用歷史最優解、當前代最優解替代種群中劣質個體，實現種群向理想方向運動，提高算法運行效率，減少算法運行時間。

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

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