面向大學(xué)課程時(shí)間表的并行多視圖搜索算法

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

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

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

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

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

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

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

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

對(duì)每一個(gè)樣本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í)際工作天數(shù)，dmi為教學(xué)計(jì)劃中要求的課程ci每周最小安排的天數(shù)。最后定義二進(jìn)制變量conij描述課程ci和cj是否存在學(xué)生或教師等沖突，存在沖突賦值為1，反之賦值為0。exclij描述是否允許將課程ci安排至pj時(shí)段，允許賦值為1，反之賦值為0。cpi,j描述是否允許將課程組Cri里的課程安排至pj時(shí)段，允許賦值為1，反之為0。

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

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

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

H2：時(shí)間表中任意位置僅允許分配不超過(guò)一個(gè)課程事件。

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

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

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

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

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

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

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

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

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

2 并行多視圖搜索求解UCTP問(wèn)題

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

2.1 算法主框架

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

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

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

2.2 初始解構(gòu)建

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

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

2.3 多鄰域局部搜索

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

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

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

M1時(shí)段移動(dòng)：隨機(jī)交換或移動(dòng)一個(gè)課程事件到另一個(gè)可行時(shí)段。

M2教室移動(dòng)：隨機(jī)交換或移動(dòng)一個(gè)課程事件到另一個(gè)可行教室。

M3課程交換：在確保無(wú)硬沖突的前提下，隨機(jī)交換時(shí)間表中兩個(gè)位置的課程。

M4時(shí)段交換：隨機(jī)交換兩個(gè)時(shí)段的所有課程。

M5教室容量移動(dòng)：隨機(jī)選擇違反教室容量約束的一個(gè)課程事件，將其移動(dòng)到合適的教室。

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

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

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

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

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

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

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

2.3.3 改進(jìn)模擬退火

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

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

算法1 基于改進(jìn)模擬退火的多鄰域局部搜索

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

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

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

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

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

（4）若ΔE≤0 或rand

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

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

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

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

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

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

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

2.3.4 搜索過(guò)程的Δ計(jì)算

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

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

2.4 視圖聚合更新

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

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

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

3 實(shí)驗(yàn)與分析

3.1 測(cè)試算例與實(shí)驗(yàn)設(shè)定

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

3.2 ITC-2007競(jìng)賽規(guī)則下的對(duì)比實(shí)驗(yàn)

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

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

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

3.3 并行多視圖搜索對(duì)比實(shí)驗(yàn)

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

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

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

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

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

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