面向大學課程時間表的并行多視圖搜索算法

宋 婷，王 棟，許玉龍，王 昂

1.河南中醫藥大學 信息技術學院，鄭州450046

2.華中師范大學 國家數字化學習工程技術研究中心，武漢430079

3.河南農業大學 信息與管理科學學院，鄭州450046

隨著我國高等教育的快速發展，不斷擴大的教學規模和教學改革要求對如何科學集約的調配各種教學資源、合理高效地安排大學課程時間表提出了新的挑戰。大學課程時間表問題（university course timetable problem，UCTP），即大學排課問題，本質上是一個具有NP難度的多約束組合優化問題[1]，這意味著不存在完整精確的快速求解算法。啟發式算法通常可以在較短時間內獲得一個令人滿意的解，實現求解效率和質量之間的平衡。因此，設計高效的啟發式算法，是求解組合優化問題的主要途徑。這類算法通常可分為：直接啟發式方法（包括貪婪算法[2]、圖著色算法[3]等）、局部搜索算法（包括禁忌搜索[4]、模擬退火[5]等）、群智能算法（包括蜂群算法[6]、蟻群算法[7]、遺傳算法[8]等）。由于該問題的復雜性，為吸引更多學者的關注和研究，學術界已舉辦過多次國際時間表競賽（international timetabling competition，ITC）[9]，提供了公開的大學排課模型以便于廣大研究者在同一基準下聚焦于算法與理論研究。在競賽當中和其后的研究中，研究者往往混合多種啟發式算法共同參與問題的求解，例如Müller[10]采用基于約束的混合局部搜索算法，合并爬山法、大洪水算法、模擬退火算法共同提升尋找最優解。Lyu等[4]將一種自適應禁忌搜索的混合啟發式算法應用于大學課程時間表。Geiger[11]采用了一種基于閾值接受準則的隨機鄰域混合算法來克服求解UCTP 時的局部最優問題。Clark 等[12]應用基于修復的混合啟發式搜索求解UCTP。Abdullah[13]采用基于電磁原理的混合元啟發式算法對該問題進行求解，Bellio等[14]利用令牌環搜索策略混合模擬退火和動態禁忌搜索算法提升全局搜索能力，隨后在另一項研究[15]中又提出對樣本特征進行統計分析，從而實現參數調整的方法，包括基于特征的調整（FBT）和標準F-RACE調整等。本文作者在之前的研究[16]中也嘗試了運用多類分類器指導鄰域選擇和參數設置，混合貪婪算法、模擬退火算法、迭代局部搜索算法共同參與求解UCTP問題。

上述算法雖然取得了一定的成果，但仍未能解決ITC 給出的所有問題實例，且之前的算法多為串行算法，在目前普遍存在的多/眾核環境中，無法有效利用算力資源、發揮多/眾核優勢，為此本文針對UCTP 問題提出了一種全新的并行多視圖搜索算法（parallel multi-view search algorithm，PMSA）。該算法運用并行計算混合多個基于模擬退火的局部搜索過程，通過視圖聚合實現多視圖最優解的共享與更新。在幾乎沒有降低迭代速度的前提下，線性擴大了搜索范圍，極大地提高了全局最優解的求解質量。在對ITC基準數據集的測試中，取得了優于當前文獻中的最好結果。

1 UCTP數學模型

UCTP 涉及將一組課程C={c1,c2,…,ct} 分配到不同的教室R={r1,r2,…,rm} 和時段P={p1,p2,…,pn} 中，并且要盡可能滿足學校或教育機構的各種約束要求。這些約束可以分為兩類：硬約束（在任何情況下都不能違反）和軟約束（允許違反但應使這種違反盡可能最小）。根據時間表的一般設定，以周為單位，每天h個時段，一周d個工作日，總時段數n=d×h。這樣候選解可用一個m×n的矩陣X表示，xij=ck表示課程ck分配在總課表中教室ri時段pj的位置。一般而言，滿足所有硬約束的時間表是一個可行解，而同時滿足所有硬約束和軟約束的可行解就是全局最優解。在實際中，由于軟約束之間的相互沖突，很難全部得到滿足。因此，求解UCTP的目標就是在保證可行解的前提下，最小化軟約束違反值。

對每一個樣本I，定義集合G={g1,g2,…,gs} 是綁定了學生、教師和課次信息的課程事件集合。Cri表示涉及相同學生的課程組，CR={Cr1,Cr2,…,Crs} 表示所有課程組的集合。此外定義變量stui為課程ci所含學生數，rni為課程ci所涉及的教室數，rmi為教室ri的座位數，dni為課程ci的實際工作天數，dmi為教學計劃中要求的課程ci每周最小安排的天數。最后定義二進制變量conij描述課程ci和cj是否存在學生或教師等沖突，存在沖突賦值為1，反之賦值為0。exclij描述是否允許將課程ci安排至pj時段，允許賦值為1，反之賦值為0。cpi,j描述是否允許將課程組Cri里的課程安排至pj時段，允許賦值為1，反之為0。

根據以上問題描述及變量定義，UCTP 問題的軟硬約束及目標函數可數學表達如下。

1.1 硬約束及其數學表達

H1：所有教學計劃中的課程事件均需分配到時間表中。

H2：時間表中任意位置僅允許分配不超過一個課程事件。

H3：任意課程事件不允許存在學生或教師等沖突。

H4：任意課程不允許分配至其授課教師明確拒絕的時段。

1.2 軟約束及其數學表達式

S1：任意課程的學生人數不大于所分配教室座位數。

S2：同一班級的同一課程盡可能分配在同一教室。

S3：所有課程事件應滿足最小工作日均勻分配。

S4：同一課程組的課程應盡量緊湊分配。

依據以上約束表達式，可以通過式（9）得到一個給定候選解X的軟約束違反值。

這樣UCTP 問題就表示為一個在滿足給定硬約束條件下，求解最小軟約束違反時間表的最優化問題，即尋找可行解X*使z(X*)≤z(X)；其中v1、v2、v3、v4為每個軟約束的懲罰系數。

2 并行多視圖搜索求解UCTP問題

經典的迭代局部搜索算法在局部搜索算法的基礎上，加入擾動算子，通過反復迭代使搜索能夠跳出局部最優，具有結構簡單、高效健壯的特點，在對UCTP的求解中取得了較佳的結果[17]，但也存在著迭代過程中鄰域單一、耗時的缺陷。在前期工作的基礎上[16-17]，本文提出一種基于改進迭代局部搜索的并行多視圖搜索算法PMSA，通過對多個視圖運用不同的鄰域結構，使得解空間發生改變，從而增大搜索范圍、跳出局部最優，并利用并行計算加快搜索速度。以下給出該算法的主要特征及實現過程。

2.1 算法主框架

PMSA 算法主要由三個階段組成：初始解構建、多鄰域局部搜索和視圖聚合更新。在初始解構建階段，僅考慮硬約束，運用貪婪啟發式算法快速獲取可行解作為初始解。在多鄰域局部搜索階段，先依據當前計算環境中的可用處理器數確定視圖數，分別基于獨立提升貢獻比例構造具有不同選擇概率的多鄰域集。然后從前面獲取的初始解出發，利用基于模擬退火的局部搜索算法并行的在多個鄰域集上移動，逐步減少目標函數的軟約束違反值，獲取局部最優解。在視圖聚合更新階段，通過多個視圖所得局部最優解的聚合，選擇當前最優解作為新的初始解，并通過重新升溫的擾動策略開啟新一輪的多鄰域局部搜索。后兩個階段反復迭代，直到達到終止條件（到達問題下界或規定時間）為止。圖1 給出了PMSA算法的流程示意圖。

圖1 PMSA算法流程示意圖Fig.1 Flow chart of PMSA algorithm

可以看出，并行多視圖搜索的關鍵在于迭代搜索的過程中，多個不同鄰域狀態下的局部搜索可以探索更多的方向，從而使每輪搜索都能挑選更適合問題當前狀態的移動，提高了搜索效率和收斂速度。同時多個視圖在相同狀態下的并行搜索具有很強的并發性，極大地減少了進程間的等待時間。需要特別指出的是，盡管本文中多個視圖搜索的主要差異來源于各自不同的鄰域結構，但實際上也可以采用多種完全不同的搜索技術，例如引導式局部搜索[18]、禁忌搜索[4]甚至群智能方法[6-8]，當前工作僅展示了該技術的一般原型。

2.2 初始解構建

在初始解構建階段，首先初始化一個R×P的時間表矩陣，其中R={r1,r2,…,rm} 為所有教室的集合，P={p1,p2,…,pn} 為所有時段的集合，矩陣元素為分配至該教室時段的課程。因為所有課程均已關聯教師、學生，該矩陣即表示全校總課程時間表，任一教師或學生的課程時間表均可從總課程時間表里導出。

初始解的構建采用一種基于序列的快速貪婪算法：在滿足所有硬約束(H1～H4)的條件下，動態地從待分配課程事件池中選擇當前最難分配的課程事件，優先安排至當前被請求最少的時間表位置。課程事件的分配難度用s=ap/uc評價，其中ap為當前該課程的可選時段數，uc為該課程的剩余節次數。通過這個貪婪啟發式策略，可以輕松地為本文中所有測試算例求得可行的初始解。

2.3 多鄰域局部搜索

2.3.1 鄰域結構

從給定的當前解X出發，通過一次鄰域移動mv，可得到一個新的可行解，用X→mv表示。令M(X)為所有從X出發，在解空間中一步可達的可行移動的集合。則X的鄰域可定義為：

本文針對UCTP 問題的特殊性設計了兩類鄰域移動：隨機移動和指向性移動。隨機移動包含四種不同的動作，分別用時段移動、教室移動、課程交換、時段交換來表示。相應地，指向性移動也包含四個動作，分別用教室容量移動、教室穩定性移動、最小工作日移動和課程緊湊性移動表示。在這兩類鄰域移動中，隨機移動有助于擴大搜索范圍，指向性移動有助于使搜索迅速收斂到有希望的方向。兩類鄰域移動混合使用，能夠有效提高搜索的速度和精度，具體描述如下：

M1時段移動：隨機交換或移動一個課程事件到另一個可行時段。

M2教室移動：隨機交換或移動一個課程事件到另一個可行教室。

M3課程交換：在確保無硬沖突的前提下，隨機交換時間表中兩個位置的課程。

M4時段交換：隨機交換兩個時段的所有課程。

M5教室容量移動：隨機選擇違反教室容量約束的一個課程事件，將其移動到合適的教室。

M6教室穩定性移動：隨機選擇違反教室穩定性約束的一個課程，將該課程所有事件交換或移動到同一教室。

M7最小工作日移動：隨機選擇違反最小工作日約束的一個課程，調整違反課程事件到可行工作日。

M8課程緊湊性移動：隨機選擇違反課程緊湊型約束的一個課程，調整違反課程事件到可行時段。

為了方便起見，將可行移動集合M1～M8表示的鄰域分別定義為N1～N8。

2.3.2 候選鄰域選擇概率設定

局部搜索過程中，每次移動前需首先從八種候選鄰域中隨機挑選一種鄰域作為此次搜索方向，不同的候選鄰域選擇概率設置決定了該鄰域集搜索偏重的方向，也就造成了搜索結果的不同。現有的鄰域選擇概率設定方法往往是通過預先實驗，設定固定的比例；或者根據問題樣本的特征，確定候選鄰域的選擇概率。這些設定方式能夠適應普通的問題樣本，但是由于UCTP問題的復雜性，固定的選擇比例無法匹配難度特征完全不同的算例，而依據問題樣本特征在一些情況下也不能完全反映隱含的難度。例如課程組數量這一特征值并未包含每一個課程組中所涉及課程的多少和彼此之間的約束。這種隱含的關系很難通過對特征值的預先分析獲得準確的度量。

受賽車比賽中的排位賽單圈成績決定正賽發車順序的啟發，算法在正式迭代搜索之前，對每個候選鄰域運行一個循環的排位賽，根據實際運行中候選鄰域對總優化分值的提升貢獻比設定鄰域選擇概率比例。具體來說，用si表示僅使用候選鄰域Ni運行一個循環對軟約束值得優化程度，則鄰域Ni的選擇概率可以用公式表示。由于基于提升貢獻的鄰域選擇概率是從實際運行結果中得到的，有利于契合樣本中隱含的特性。需要注意的是，源于算法的隨機性，各視圖獨立運行獲取的si并不完全相同，這種差異也就造成不同視圖鄰域搜索方向的區別，從而在客觀上擴大了局部搜索范圍，增大了發現全局最優解的概率。

2.3.3 改進模擬退火

模擬退火[5]是一種經典的局部搜索算法，模擬了真實世界中固體退火的物理原理，其基本搜索過程是：先給定初始溫度T，進而從初始解出發，根據特定的搜索策略在鄰域中尋找新的候選解，通過判斷當前解與候選解之間的差值ΔE，確定隨后的動作。若候選解優于當前解，則立即更新候選解為新的當前解；反之，則按照概率exp(-ΔE/T)更新當前解。在鄰域搜索的過程中，根據公式T=a×T(0

盡管模擬退火是一種易于實現的通用框架，但已被證明是處理UCTP 問題的有效方法。例如第一屆國際時間表大賽的冠軍、第二屆國際時間表大賽中三個賽道的第一名均采用了基于模擬退火的算法。本文多視圖搜索中為了提供更精確的搜索控制提高并行效率，對經典模擬退火進行改進。通過設置預定義參數Cdmax代替終止溫度控制迭代次數，保證各視圖局部搜索過程的同步，減少視圖聚合等待時間。算法1給出了改進模擬退火過程的偽代碼。

算法1 基于改進模擬退火的多鄰域局部搜索

輸入：初始解X0′，鄰域集NS，初始溫度T0。

輸出：局部最優解X*。

（1）初始化當前解X、初始溫度T、當前降溫過程數Cd、當前恒溫過程數Ct、最大降溫過程迭代數Cdmax、最大恒溫過程迭代數Ctmax、冷卻率a、下界Zmin等基本參數。

（2）從鄰域集NS中根據選擇概率隨機挑選一個鄰域Nb，從當前解出發在鄰域中尋找一個可行的候選解X′。

（3）計算候選解與當前解的差值ΔE=z(X′)-z(X)。

（4）若ΔE≤0 或rand

（5）給當前恒溫過程數Ct增加1次計數。

（6）判讀恒溫過程數是否達到最大限制，若Ct

（7）重新初始化Ct，給Cd增加1次計數，同時降低溫度T=a×T。

（8）判斷是否滿足迭代終止條件，若到達最大降溫迭代數Cd>Cdmax或當前解分值到達下界z(X)≤Zmin，則轉步驟（9）；否則，轉步驟（2）。

（9）更新局部最優解X*=X，輸出X*。

改進模擬退火過程涉及許多參數，其設置的有效性對算法的性能具有重要影響。在本文中，首先根據預先實驗和經驗設置初始溫度T0及冷卻率a，然后在其基礎上計算設置降溫過程最大迭代次數Cdmax，以保證終止溫度小于0.005 且對應接受差解概率小于1×e-60。同時依據問題樣本中的時段數n、房間數m以及8個基本鄰域，設置最大恒溫過程迭代數Ctmax≥n×m×8，以保證對時間表中所有位置移動嘗試的充分覆蓋。表1列出了PMSA 算法中使用的重要參數及對應的描述和配置。

表1 重要參數的設定與描述Table 1 Setting and description of important parameters

2.3.4 搜索過程的Δ計算

對當前解在不同鄰域下進行移動操作，都會引起解狀態的改變，相應的就要重新評估當前解與候選解狀態的差距。如果每次移動都評估整體目標函數值，會消耗大量時間成本，影響算法運行效率。實際操作中，僅對移動前后的解狀態進行Δ計算，且僅根據當前移動所造成的具體變化進行評估，使評估過程變得更加高效。

事實上，任何一種鄰域的移動僅會引起相關教室或時段沖突值的變化。這時，只需根據當前移動所引起的相關變化進行評估即可。例如N1、N4的移動僅會引起時段的變化，N2、N5、N6的移動僅會引起教室的變化，N3、N7、N8的移動則會引起時段和教室兩者的變化。

2.4 視圖聚合更新

不同于一般局部搜索算法，模擬退火是一種理論上具有全局優化能力的高級過程。但由于退火時間所限，通常無法保證模擬退火一定會產生全局最優解。為進一步優化在基于模擬退火的局部搜索中獲得的局部最優解，需要對當前最優解進行一定的更新和擾動后，運用迭代搜索進一步全局尋優。

與迭代局部搜索不同，PMSA算法在多鄰域局部搜索階段具有N個獨立的視圖（局部搜索過程），分別在具有不同選擇概率的多鄰域集中尋找局部最優解。在每輪局部搜索的終點，需要對N個視圖的局部搜索結果進行聚合，以選擇下一個迭代的初始解。顯而易見由函數確定的當前具有最小約束違反值的時間表方案代表著更有希望的搜索方向，被保存為當前全局最優解，并自動更新為新一輪搜索的初始解。

在重啟新一輪多鄰域局部搜索之前，為跳出局部最優，需對新的初始解進行擾動。在本文采用的模擬退火過程中，通過重新設置初始溫度T0以達到擾動目的。具體重啟次數iter依據終止時間限制和單次搜索時間的比例設置。

3 實驗與分析

3.1 測試算例與實驗設定

為了驗證PMSA算法的有效性，本文對第二屆國際時間表大賽的UCTP 問題（ITC-2007 track3）進行實驗驗證。大賽規定及相關細節可參考[19]。該數據集包含21個源自真實世界的基準測試算例。相對于競賽中要求比較算法在不同隨機種子下獨立求解10次的平均結果，后續研究考慮到計算的隨機性，為增強比較的公正程度，采用了更多次數（30～100）的平均結果進行算法評價，本文在相關實驗中也采取相同的設定。PMSA 算法采用C++編寫，并在配備Intel E5 2.6 GHz CPU 和32G RAM 的服務器上進行了測試。執行時間基于ITC-2007 規則，這是用基準工具確定的時間限制，運行環境中為208 s。

3.2 ITC-2007競賽規則下的對比實驗

實驗首先在ITC-2007 競賽規則下，比較了PMSA（僅使用單核狀態下）與文獻中七種最先進的UCTP 問題求解算法的性能差異。這七種算法包括在競賽中獲得前兩名的Müller提出的CSH[10]和Lyu等提出的ATS[4]，賽后最新研究中Abdullah 等提出的EM-GD[13]，Bellio 等提出的SA-DTS[14]和后續提出的FBT 和F-Race[15]，以及作者之前提出的MC-ILS[16]。考慮到比較的公平性，實驗采用與最新研究FBT 和F-Race 相似的運行次數，對每個實例獨立運行30次取平均值。獲得的結果分值越低，該算法的能力越強。表2給出了PMSA算法和其他七種參考算法在UCTP問題的21個算例上的運行結果。

如表2所示，PMSA算法在全部21個算例中獲得了11個最佳平均結果（每個算例的最佳平均結果以粗體顯示），相對于其他最新算法，PMSA顯示出明顯優勢。最后一行給出Friedman 非參數統計檢驗的Average ranks分值也得出了相同的結論。在僅使用單核處理器的情況下，PMSA 退化成為與MC-ILS 類似的迭代局部搜索算法，但依賴于八候選鄰域設計及新的候選鄰域選擇概率設定規則，仍然在整體精度上取得一定的提高，顯示了所提策略的有效性。

表2 ITC-2007競賽規則下的平均得分對比Table 2 Comparison of average scores under ITC-2007 rules

3.3 并行多視圖搜索對比實驗

在隨后的并行多視圖搜索測試中，分別比較了在PMSA算法分別在1核、2核、4核、8核、16核、32核CPU參與的情況下，對算法性能的提升。實驗終止條件仍然采用ITC-2007 競賽所定的基準時間。圖2 給出了針對UCTP問題21個算例，在不同的并行條件下取得平均分值的對比結果。

圖2 不同并行條件下的平均分值Fig.2 Average scores under different parallel conditions

從圖2 可以看出，在相同的基準時間下，隨著更多處理器參與計算，在除comp01和comp11兩個已到達下界的簡單算例之外的所有算例中都取得了線性的提升，多視圖聚合相對于單視圖的迭代局部搜索在收斂速度和搜索能力上顯示出明顯優勢。

在并行多視圖搜索當中，多個由不同選擇概率設定構造的多鄰域結構，使得算法在提升對重點區域搜索深度的同時，也擴大了鄰域搜索范圍，本質上是以更多的計算為代價換取精度上的提升。在給定時間限制條件下，借助并行計算有效利用已有計算資源是一種簡單易行的方案。多個獨立局部搜索過程具有顯著的并行性，最大程度保證各局部搜索過程的同步，減少視圖聚合等待時間，是提高并行效率的關鍵。通過對模擬退火算法改進，用預定義參數代替終止溫度控制循環次數，使每個視圖中搜索次數均為Cdmax×Cdmax，保證了局部搜索結束時間基本一致。在16 核以下的實驗中，視圖聚合更新的迭代次數與僅單核參與的迭代次數完全相同，僅在32核的實驗中，個別算例視圖更新次數有少量下降，表現出良好的并行能力。

4 結束語

本文對大學課程時間表問題（UCTP）進行了研究，提出一種全新的并行多視圖搜索算法。該方法通過包含八種基礎鄰域的多鄰域設計，根據實際運行中候選鄰域對總優化分值的提升貢獻比設定鄰域選擇概率比例，有效提升了局部搜索效率；并利用多視圖學習策略融合多個并行局部搜索過程結果，及時修正搜索方向，顯著提高了算法的收斂速度和搜索能力。在著名的包含21個問題實例的UCTP 基準數據集上進行的對比實驗表明，與當前文獻中表現最佳的七種啟發式算法相比，在ITC-2007競賽終止條件下PMSA獲得了最多的11個實例的最好結果；在并行多視圖搜索對比實驗中更體現出在多/眾核環境下更強的求解精度和搜索潛力。在未來的工作中，將對多視圖搜索階段運用不同的局部搜索算法或群智能算法做進一步研究，同時可嘗試將PMSA應用于時間表領域的其他復雜組合優化問題。