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

1.河南中醫(yī)藥大學(xué) 信息技術(shù)學(xué)院，鄭州450046

2.華中師范大學(xué) 國家數(shù)字化學(xué)習(xí)工程技術(shù)研究中心，武漢430079

3.河南農(nóng)業(yè)大學(xué) 信息與管理科學(xué)學(xué)院，鄭州450046

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

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

1 UCTP數(shù)學(xué)模型

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

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

根據(jù)以上問題描述及變量定義，UCTP 問題的軟硬約束及目標(biāo)函數(shù)可數(shù)學(xué)表達如下。

1.1 硬約束及其數(shù)學(xué)表達

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

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

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

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

1.2 軟約束及其數(shù)學(xué)表達式

S1：任意課程的學(xué)生人數(shù)不大于所分配教室座位數(shù)。

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

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

S4：同一課程組的課程應(yīng)盡量緊湊分配。

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

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

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

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

2.1 算法主框架

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

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

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

2.2 初始解構(gòu)建

在初始解構(gòu)建階段，首先初始化一個R×P的時間表矩陣，其中R={r1,r2,…,rm} 為所有教室的集合，P={p1,p2,…,pn} 為所有時段的集合，矩陣元素為分配至該教室時段的課程。因為所有課程均已關(guān)聯(lián)教師、學(xué)生，該矩陣即表示全?？傉n程時間表，任一教師或?qū)W生的課程時間表均可從總課程時間表里導(dǎo)出。

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

2.3 多鄰域局部搜索

2.3.1 鄰域結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

2.3.2 候選鄰域選擇概率設(shè)定

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

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

2.3.3 改進模擬退火

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

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

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

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

輸出：局部最優(yōu)解X*。

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

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

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

（4）若ΔE≤0 或rand

（5）給當(dāng)前恒溫過程數(shù)Ct增加1次計數(shù)。

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

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

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

（9）更新局部最優(yōu)解X*=X，輸出X*。

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

表1 重要參數(shù)的設(shè)定與描述Table 1 Setting and description of important parameters

2.3.4 搜索過程的Δ計算

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

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

2.4 視圖聚合更新

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

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

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

3 實驗與分析

3.1 測試算例與實驗設(shè)定

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

3.2 ITC-2007競賽規(guī)則下的對比實驗

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

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

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

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

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

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

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

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

4 結(jié)束語

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