肖成龍，聶紫陽，王珊珊

遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島125105

1 引言

約束規(guī)劃（Constraint Programming，CP）[1]是用于聲明描述和有效解決約束滿足及約束優(yōu)化問題的軟件技術(shù)，其在實(shí)際問題的建模方面具有高度靈活性和求解方式多樣性，具有很高的學(xué)術(shù)價(jià)值和商業(yè)價(jià)值，在很多領(lǐng)域受到相關(guān)專家的高度關(guān)注。世界多所知名大學(xué)、科研機(jī)構(gòu)和公司紛紛成立了約束規(guī)劃研究中心，致力于約束規(guī)劃的理論研究、工具研發(fā)及成果轉(zhuǎn)化。目前，約束規(guī)劃已經(jīng)成功應(yīng)用于包括航空[2]、電氣[3]、運(yùn)輸[4]、密碼學(xué)[5]、生物信息學(xué)[6]、生產(chǎn)調(diào)度[7]、機(jī)器學(xué)習(xí)[8]、圖形圖像[9]等諸多領(lǐng)域。

約束規(guī)劃起源于20世紀(jì)60年代，并在20世紀(jì)80年代開始積極發(fā)展，其中約束邏輯規(guī)劃CLP[10]的出現(xiàn)成為了約束規(guī)劃領(lǐng)域研究的一座重要里程碑。20世紀(jì)90年代，約束規(guī)劃進(jìn)入實(shí)際使用時(shí)代，一些大學(xué)及商業(yè)公司相繼研發(fā)了多種基于邏輯規(guī)劃語言和面向過程語言的約束規(guī)劃工具。1996 年，在美國計(jì)算機(jī)協(xié)會ACM 成立五十周年大會上，約束規(guī)劃被列為21 世紀(jì)計(jì)算機(jī)領(lǐng)域戰(zhàn)略研究方向之一。同年，約束規(guī)劃期刊Constraints創(chuàng)刊。2005 年約束規(guī)劃協(xié)會ACP 在法國成立，旨在促進(jìn)約束規(guī)劃的理論及應(yīng)用發(fā)展，其每年舉辦的約束規(guī)劃理論及實(shí)踐國際會議CP 與整合約束規(guī)劃、人工智能及運(yùn)籌學(xué)國際會議CPAIOR（非約束規(guī)劃協(xié)會舉辦）已成為約束規(guī)劃研究交流的兩項(xiàng)重要國際學(xué)術(shù)會議。此外，近些年，在IJCAI、AAAI、ECAI 等一些國際頂級的人工智能會議上，都有對約束規(guī)劃相關(guān)研究的專題討論。當(dāng)前，約束規(guī)劃已成為人工智能領(lǐng)域的一個研究熱點(diǎn)。

約束規(guī)劃采用約束傳播[11]和回溯搜索[12]來解決問題，約束傳播用于修剪搜索空間，回溯搜索對搜索空間進(jìn)行遍歷，實(shí)現(xiàn)問題求解。在搜索過程中如何選擇變量構(gòu)建搜索樹是一個十分關(guān)鍵的步驟，選擇“正確”變量賦值可減少無效搜索分支，提高求解效率。

假設(shè)一個簡單的約束滿足問題包含n 個白變量和m 個黑變量。白變量值域?yàn)閧0，1}，黑變量值域?yàn)閧0，1，2，…，m-2}，對于黑變量要求其兩兩取值不同，而白變量沒有約束限制?？梢院苋菀追治龀鲈摷s束滿足問題沒有滿足約束條件的解。假設(shè)在回溯搜索過程中采用的變量排序啟發(fā)式優(yōu)先選擇白變量進(jìn)行賦值，待所有白變量賦值完成后再選擇黑變量賦值，則該啟發(fā)式對應(yīng)的搜索樹如圖1左所示，求解時(shí)會對整個搜索空間進(jìn)行遍歷。若在開始搜索之后采用動態(tài)的變量排序啟發(fā)式選擇可能導(dǎo)致搜索失敗的變量構(gòu)建搜索樹，則搜索樹如圖1右所示，可以看到合適的變量排序啟發(fā)式策略可對搜索樹進(jìn)行有效剪枝，提高問題求解效率。

圖1 應(yīng)用變量排序啟發(fā)式效果示例

目前，針對變量選擇已有多種獨(dú)立和組合變量排序啟發(fā)式被提出，包括dom[13]、deg[14]、IBS[15]、ABS[16]、CBS[17]、CRBS[18]、dom/deg[19]、dom/ddeg[20]、dom/wdeg[13]等。這些啟發(fā)式基于變量屬性或問題求解狀態(tài)選擇合適變量，加快搜索進(jìn)程。但由于待解決問題種類、特征不同及啟發(fā)式自身特性等原因，一個變量排序啟發(fā)式即使在多數(shù)問題求解上剪枝效果較好，也無法保證在所有問題求解上都要優(yōu)于其他啟發(fā)式。從搜索過程出發(fā)尋找利用問題求解通性，屏蔽問題之間的差異對求解過程的影響，提出和研究改進(jìn)更為有效、適用范圍更廣的獨(dú)立或組合的通用啟發(fā)式仍是約束規(guī)劃研究中一個重要的研究方向。

本文采用一種新穎的變量排序啟發(fā)式組合策略ParetoHeu[21]將經(jīng)典的啟發(fā)式dom/wdeg與基于關(guān)聯(lián)的啟發(fā)式CRBS（Correlation-Based Search）結(jié)合，以提高和增強(qiáng)CRBS對問題的求解效率和通用性。同時(shí)，加入基于實(shí)例化失敗次數(shù)的權(quán)值統(tǒng)計(jì)方法[22]進(jìn)一步對待實(shí)例化變量進(jìn)行選擇，提出了crbs-sum及crbs-max的兩種改進(jìn)變量排序啟發(fā)式PICS 和PICM。實(shí)驗(yàn)在Choco[23]約束求解器上實(shí)現(xiàn)，并在多個約束滿足問題實(shí)例上進(jìn)行測試。實(shí)驗(yàn)結(jié)果表明PICS 和PICM 與crbs-sum、crbsmax 及其他經(jīng)典主流啟發(fā)式相比，在多個問題實(shí)例求解上，兩種新變量排序啟發(fā)式方法的求解效率高于其他啟發(fā)式。

2 相關(guān)工作

變量排序啟發(fā)式對回溯搜索效率有著重要影響，選擇合適變量實(shí)例化可以顯著減小搜索空間，從而更快地解決問題。在一些規(guī)模較大的問題求解上，一個“正確”或“錯誤”的決定可以使求解時(shí)間產(chǎn)生指數(shù)級的變化。目前，已有多種變量排序啟發(fā)式相繼提出。這些啟發(fā)式大多遵循“失敗優(yōu)先”原則，即優(yōu)先選擇可能導(dǎo)致搜索失敗的變量進(jìn)行實(shí)例化，并基于變量值域大小、約束圖、約束觸發(fā)失敗次數(shù)等特征定義得分函數(shù)，在每個搜索節(jié)點(diǎn)上選擇得分函數(shù)最高的變量實(shí)例化。

變量排序啟發(fā)式可分靜態(tài)變量排序啟發(fā)式和動態(tài)變量排序啟發(fā)式兩類。靜態(tài)變量排序啟發(fā)式在搜索之前計(jì)算變量得分并確定實(shí)例化變量序列，在搜索過程中不會對變量序列進(jìn)行調(diào)整，一些已經(jīng)提出的靜態(tài)排序啟發(fā)式包括選擇相關(guān)約束最多變量的啟發(fā)式deg[14]、選擇最小約束網(wǎng)絡(luò)寬度的啟發(fā)式width[12]等。動態(tài)變量排序啟發(fā)式在搜索期間動態(tài)更新變量得分并調(diào)整變量排序。在實(shí)際使用中，動態(tài)排序啟發(fā)式的應(yīng)用多于靜態(tài)排序啟發(fā)式。早期的獨(dú)立或組合動態(tài)排序啟發(fā)式都是根據(jù)變量基本屬性來選擇變量，如第一個動態(tài)排序啟發(fā)式dom[13]基于值域大小選擇變量、動態(tài)的deg 啟發(fā)式ddeg[14]、dom/deg[19]、dom/ddeg[20]等。之后，一些基于問題求解狀態(tài)和自定義變量特征的啟發(fā)式相繼提出，包括基于影響的啟發(fā)式IBS（Impact-Based Search）[15]、基于沖突的啟發(fā)式wdeg[24]、基于活躍度的啟發(fā)式ABS（Activity-Based Search）[16]、dom/wdeg[13]、基于約束緊度和解密度的啟發(fā)式RHO[25]等。目前，IBS、ABS 和dom/wdeg 是大多數(shù)約束規(guī)劃求解器中主要使用的三種啟發(fā)式。IBS啟發(fā)式通過衡量變量實(shí)例化導(dǎo)致潛在搜索空間的減少程度選擇變量。Wdeg啟發(fā)式為每個約束賦予一個權(quán)重值，當(dāng)搜索產(chǎn)生沖突時(shí)，相應(yīng)約束的權(quán)重會增加，啟發(fā)式會優(yōu)先選擇約束權(quán)重之和最大的變量。ABS 啟發(fā)式基于每個變量值域變動頻率選擇變量。近些年提出的一些較為新穎的啟發(fā)式及改進(jìn)啟發(fā)式主要有基于統(tǒng)計(jì)變量賦值在解中出現(xiàn)的頻率的CBS（Count-Based Search）[17]、基于失敗原因解釋的改進(jìn)wdeg[26]、優(yōu)先選擇最后沖突的變量的LC（Last Conflict heuristic）[27]、沖突排序的COS（Conflict Ordering Search）[28]、基于約束緊度的改進(jìn)dom/ddeg和dom/wdeg[29]、基于變量關(guān)聯(lián)的CRBS以及基于帕累托最優(yōu)的啟發(fā)式組合策略ParetoHeu等。這些變量排序啟發(fā)式都基于問題變量、約束的自身屬性或研究人員自定義屬性來選擇變量，不考慮問題本身的性質(zhì)，從而將問題本身與變量選擇分離，使其可用于對大部分問題求解，而不是只針對一個或一類問題，具有一定的通用性。因此，對于提高變量排序啟發(fā)式通用性研究的著手點(diǎn)也在于如何利用變量、約束的基本屬性或與其相關(guān)的自定義屬性來選擇變量。此外，在Li等人的研究[21]中，實(shí)驗(yàn)結(jié)果顯示組合啟發(fā)式在多數(shù)情況下要優(yōu)于原單啟發(fā)式，早期的dom/ddeg、dom/wdeg等組合啟發(fā)式也很好地印證了這一點(diǎn)，文章中應(yīng)用其提出的ParetoHeu 啟發(fā)式組合策略在問題求解上平均CPU時(shí)間要少于傳統(tǒng)的順序啟發(fā)式組合策略和得分乘積啟發(fā)式組合策略，ParetoHeu為組合啟發(fā)式提供了一個新的思路。

除上述獨(dú)立啟發(fā)式與組合啟發(fā)式研究外，還有一些關(guān)于自適應(yīng)變量排序啟發(fā)式的研究，這類啟發(fā)式稱為超啟發(fā)式（hyper-heuristic）[30]，其根據(jù)解決方案數(shù)量、目標(biāo)函數(shù)值、已運(yùn)行時(shí)間等問題狀態(tài)特征，從包含多個獨(dú)立啟發(fā)式的序列中為搜索過程動態(tài)選擇啟發(fā)式。一些研究[21]包括基于機(jī)器學(xué)習(xí)[31-32]和基于演化計(jì)算[33]的超啟發(fā)式。目前，這些方法尚未在主流約束規(guī)劃求解器中實(shí)現(xiàn)和應(yīng)用。

3 相關(guān)定義

約束滿足問題（Constraint Satisfaction Problem，CSP）[34]源于人工智能研究，多為NP-hard 問題，可定義為三元組P=＜X,D,C ＞，其中X={x1,x2,…,xn}為變量集，D={dom(x1),dom(x2),…,dom(xn)}為X 中各變量值域dom( xi)的集合，每個變量值域大小記作|dom( xi)|。為約束集，約束是各變量取值的制約關(guān)系。變量xi涉及約束的個數(shù)稱為度（degree），每個約束ci可記成( scp( ci),rel( ci))，scp( ci)={ x1,x2,…,xr} 是一個有序的變量子集，為約束ci所涉及到的變量，rel(ci)是scp(ci)內(nèi)每個變量值域笛卡爾乘積D(x1)×D(x2)×…×D(xr)的一個子集，每個元組τ ∈rel(ci)是一個有序的變量取值的集合，可定義為＜(x1,a1),(x2,a2),…,(xr,ar)＞，其中aj∈dom(xj),j=1,2,…,r。

約束滿足問題的求解是依次為每個變量在其值域中選擇一個合適的值，使所有變量賦值后滿足全部約束，為變量賦值的過程稱為實(shí)例化（instantiate）。在約束規(guī)劃中常采用約束傳播與回溯搜索結(jié)合的方式對CSP進(jìn)行求解。約束傳播使用相容性技術(shù)（consistency technology）在搜索前和搜索過程中從變量值域里移除不屬于任何可行解的值，進(jìn)而減小搜索空間，加快搜索進(jìn)程，出于時(shí)間復(fù)雜度和空間復(fù)雜度的考慮，約束求解器中最常使用的為弧相容（Arc Consistency，AC）[11]和邊界相容（Bounds Consistency，BC）[11]算法?；厮菟阉饔糜趯?shí)現(xiàn)對問題求解，在搜索過程中會使用變量排序啟發(fā)式選擇待實(shí)例化變量構(gòu)建搜索樹，變量排序啟發(fā)式會對搜索效率產(chǎn)生巨大影響。在回溯搜索期間，已實(shí)例化變量稱為PastVar。相反，未實(shí)例化變量稱為FutVar。

4 基于ParetoHeu和實(shí)例化失敗統(tǒng)計(jì)的關(guān)聯(lián)啟發(fā)式方法PICRBS

4.1 PICRBS思想

為進(jìn)一步提升和增強(qiáng)關(guān)聯(lián)啟發(fā)式CRBS 對問題的求解效率和通用性，本文提出了基于ParetoHeu 和實(shí)例化失敗統(tǒng)計(jì)的關(guān)聯(lián)啟發(fā)式PICRBS，并根據(jù)CRBS 中兩種變量選擇方式crbs-sum 和crbs-max 提出了具體方法PICS 和PICM，PICS 與PICM 的區(qū)別在于兩種方法計(jì)算CRBS啟發(fā)式得分方式不同。

PICRBS 采用基于帕累托最優(yōu)（Pareto optimality）的啟發(fā)式組合策略ParetoHeu 將啟發(fā)式CRBS 與dom/wdeg 結(jié)合，在未實(shí)例化變量中選擇最可能導(dǎo)致搜索發(fā)生沖突的變量，加入帕累托候選變量集合中。之后使用基于實(shí)例化失敗次數(shù)的權(quán)值統(tǒng)計(jì)方法對帕累托候選變量集合中的變量做進(jìn)一步篩選。已有研究發(fā)現(xiàn)變量實(shí)例化的失敗次數(shù)在一定程度上可說明該變量與已實(shí)例化變量集之間的沖突關(guān)系[22]，因此選擇實(shí)例化失敗次數(shù)最多的變量作為待實(shí)例化變量可增加搜索過程中發(fā)生沖突的可能，從而使搜索樹盡早剪枝，加快問題求解。

PICRBS通過對變量值域在搜索中改變頻率以及變量相關(guān)約束導(dǎo)致回溯次數(shù)的雙重衡量，從變量自身及約束兩個方面考慮選擇該變量導(dǎo)致搜索發(fā)生回溯的可能，使變量實(shí)例化后搜索樹可最大化剪枝。同時(shí)，雙重衡量也可防止因單啟發(fā)式對問題求解的不適用而導(dǎo)致問題求解時(shí)間過長甚至無法求解，增強(qiáng)了啟發(fā)式的通用性。在組合啟發(fā)式后使用基于實(shí)例化失敗的權(quán)值統(tǒng)計(jì)方法，選擇實(shí)例化后導(dǎo)致搜索沖突可能性相對更高的變量，可對啟發(fā)式求解問題的效率做進(jìn)一步提升。

4.2 PICRBS流程

PICRBS流程圖如圖2所示。在搜索期間，PICRBS維持存儲所有變量對關(guān)聯(lián)性的對稱關(guān)聯(lián)矩陣、統(tǒng)計(jì)約束權(quán)值和各變量實(shí)例化失敗次數(shù)。進(jìn)行變量選擇時(shí)，PICRBS遍歷未實(shí)例化變量集合FutVars，對集合中變量xi計(jì)算啟發(fā)式CRBS（crbs-sum/crbs-max）和dom/wdeg得分（兩種得分分別記作sc1 和sc2），并依次與帕累托候選變量集合ParetoFront 中的變量xj比較兩種啟發(fā)式得分，若sc1[xi]≥sc1[xj]且sc2[xi]＞sc2[xj]或sc2[xi]≥sc2[xj]且sc1[xi]＞sc1[xj]，稱變量xi支配（dominate）變量xj，PICRBS 將xi作為帕累托候選變量添加到候選變量集合ParetoFront中，同時(shí)由xi支配的變量xj都將從集合中移除。如果xi和xj的啟發(fā)式得分相同，xi被添加到ParetoFront中。對于ParetoFront中得分相同的變量，PICRBS 通過變量實(shí)例化失敗次數(shù)進(jìn)行進(jìn)一步篩選，選擇搜索期間實(shí)例化失敗次數(shù)最多的變量作為待實(shí)例化變量加入集合MaxInsta中，若MaxInsta中存在多個失敗次數(shù)相同的變量，則對這些變量進(jìn)行隨機(jī)選擇。在變量實(shí)例化后，如果搜索未發(fā)生沖突，對關(guān)聯(lián)矩陣進(jìn)行更新。反之，更新關(guān)聯(lián)矩陣同時(shí)對約束權(quán)值和變量實(shí)例化失敗次數(shù)進(jìn)行加權(quán)更新。

關(guān)聯(lián)矩陣更新方式及PICRBS中CRBS啟發(fā)式得分計(jì)算規(guī)則如下：當(dāng)選擇某個變量xi實(shí)例化并進(jìn)行約束傳播后，若發(fā)生沖突，即有變量值域被清空，關(guān)聯(lián)矩陣按式（1）規(guī)則進(jìn)行更新，其中X'=X{xi}為X 去除xi后的變量集合，為更新前的關(guān)聯(lián)值。

若無沖突發(fā)生，則按式（2）規(guī)則更新關(guān)聯(lián)矩陣，dom'(xj)為約束傳播后變量xj的值域，U 和N 分別為約束傳播后值域發(fā)生變化和沒有變化的變量集合。

圖2 PICRBS流程圖

啟發(fā)式CRBS 計(jì)算得分有兩種方式，crbs-sum 與crbs-max。PICS和PICM 分別采用這兩種計(jì)算方式，計(jì)算規(guī)則如式（3）和（4）所示。 Pc(xi)為已實(shí)例化變量與xi關(guān)聯(lián)值的和，F(xiàn)c(xi)為未實(shí)例化變量與xi關(guān)聯(lián)值的和，在計(jì)算時(shí)變量xi記為未實(shí)例化變量，參數(shù)0 ≤θ ≤1用于調(diào)整Pc(xi) 與Fc(xi) 的組合關(guān)系。在計(jì)算crbssum(xi) 或crbs-max(xi) 后，crbs-sum 和crbs-max 會將crbs-sum(xi)/dom(xi) 和crbs-max(xi)/dom(xi) 作 為 最終啟發(fā)式得分。

約束權(quán)值weight[c]是啟發(fā)式dom/wdeg為每個約束c ∈C 設(shè)置的屬性值，初始為1，當(dāng)變量實(shí)例化導(dǎo)致沖突時(shí)，權(quán)重值加1。作為變量得分。式（5）為變量權(quán)重和計(jì)算公式，其中FutScp(c)為scp(c)中的未實(shí)例化變量集合。

變量實(shí)例化失敗次數(shù)權(quán)值統(tǒng)計(jì)公式如式（6）所示，其中var_ fails 為變量實(shí)例化失敗次數(shù)，dom 為變量值域大小。

PICRBS關(guān)鍵部分偽代碼如下：

算法1 PICRBS(FutVars,sc1,sc2,insta)

輸入：FutVars,sc1,sc2,insta

輸出：MaxInsta

1.ParetoFront←?；

2.MaxInsta←?；

3.tempMaxInsta=?1；

4.for each variable xiin FutVars do

5. isPareto←true；

6. for each variable xjin ParetoFront do

7. if xidominates xjthen

8. ParetoFront ←ParetoFront{xj}；

9. else

10. if xjdominates xithen

11. is Pareto←false；

12. end if

13. break；

14. end if

15. end for

16. if isPareto then

17. ParetoFront←ParetoFront∪{xi}；

18. end if

19.end for

20.for each variable xiin ParetoFront do

21. if insta[xi]>tempMaxInsta then

22. tempMaxInsta=insta[xi]；

23. MaxInsta←?；

24. MaxInsta←MaxInsta∪{xi}；

25. else

26. if insta[xi]==tempMaxInsta then

27. MaxInsta←MaxInsta∪{xi}

28. end if

29. end if

30.end for

31.return MaxInsta

偽代碼中參數(shù)FutVars、sc1、sc2、insta 分別為未實(shí)例化變量集合、CRBS 啟發(fā)式得分、dom/wdeg 啟發(fā)式得分和待解決約束滿足問題中所有變量集合。方法開始時(shí)先建立兩個空集合ParetoFront 和MaxInsta 分別用于存儲帕累托候選變量以及實(shí)例化失敗次數(shù)最多變量，tempMaxInsta 記錄當(dāng)前最大實(shí)例化失敗次數(shù)。在構(gòu)建搜索樹時(shí)，對于未實(shí)例化變量集合FutVars 中的變量進(jìn)行遍歷，選擇兩種啟發(fā)式得分都最高的變量加入集合，在遍歷過程中對ParetoFront 進(jìn)行動態(tài)更新。待所有變量遍歷完畢后，通過基于變量實(shí)例化失敗次數(shù)對ParetoFront 中變量做進(jìn)一步篩選，選擇以往搜索中實(shí)例化失敗次數(shù)最多的一個變量或多個變量加入MaxInsta 集合，若MaxInsta 中多于一個變量，則對變量進(jìn)行隨機(jī)選取，最后返回一個變量構(gòu)建搜索樹。

5 實(shí)驗(yàn)及結(jié)果分析

5.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)為國際測試通用的約束滿足問題，其中一部分為2018年約束求解器競賽基準(zhǔn)問題。實(shí)驗(yàn)中，對于每類問題分別選取了不同規(guī)模的實(shí)例，共177 個，這些實(shí)例均可在http：//xcsp.org/上下載。測試所用的基準(zhǔn)約束滿足問題包括：SportsScheduling、StripPacking、SocialGolfers、MagicHexagon、GracefulGraph、Frb、Bibd、QueensKnights、Hanoi、Driverlogw、Eternity、ColouredQueens、Crossword。

5.2 實(shí)驗(yàn)配置及說明

實(shí)驗(yàn)在約束求解器Choco 4.0.8上完成。實(shí)驗(yàn)環(huán)境及配置為JDK8，Windows操作系統(tǒng)，英特爾i5-3337U雙核處理器1.8 GHz，4 GB DDR3內(nèi)存。

實(shí)驗(yàn)中與PICS 和PICM 對比的啟發(fā)式方法包括：IBS[15]、ABS[16]、dom/wdeg（d/w）[13]、crbs-sum（c-s）[18]和crbsmax（c-m）[18]。在實(shí)驗(yàn)中，采用geometric重啟策略，初始cutoff=10，ρ=0.1。cutoff 為最大失敗數(shù)，ρ 控制重啟之后最大失敗數(shù)增長，公式為cutoff=cutoff'+init_cutoff×ρk。 cutoff′ 為上一次失敗次數(shù)，k 為重啟次數(shù)。搜索使用二元分支深度優(yōu)先搜索，求解時(shí)限為1 200 s。對 于 啟 發(fā) 式crbs-sum 和PICS，參 數(shù)θ 設(shè) 為0.1。在PICS 和PICM 中為了選取最高得分，dom/wdeg計(jì)算采用對于實(shí)驗(yàn)中的隨機(jī)數(shù)，隨機(jī)種子均設(shè)為0。

實(shí)驗(yàn)測評指標(biāo)包括啟發(fā)式成功求解問題實(shí)例數(shù)量，所有啟發(fā)式均可求解問題的平均時(shí)間、平均搜索樹節(jié)點(diǎn)。在對時(shí)間指標(biāo)統(tǒng)計(jì)時(shí)，為避免極端求解時(shí)間對實(shí)驗(yàn)評估產(chǎn)生影響以及更準(zhǔn)確地反映問題求解時(shí)間，實(shí)驗(yàn)對每個問題實(shí)例進(jìn)行5次求解，最終統(tǒng)計(jì)時(shí)除去最長與最短求解時(shí)間，取剩余3次求解時(shí)間的平均值。

5.3 實(shí)驗(yàn)結(jié)果及分析

表1 給出了各啟發(fā)式對于測試問題實(shí)例的成功求解個數(shù)、平均時(shí)間和平均節(jié)點(diǎn)。問題名稱后括號內(nèi)為實(shí)驗(yàn)選取問題實(shí)例個數(shù)，時(shí)間和節(jié)點(diǎn)后括號內(nèi)為該類問題啟發(fā)式均可求解實(shí)例個數(shù)。PICS 和PICM 作為本文提出的c-s 和c-m 改進(jìn)啟發(fā)式分別在11/13、9/13 個問題求解上相對于后兩者搜索樹節(jié)點(diǎn)有所減少，在Graceful-Graph 問題上最為明顯，分別減少了99.75%和98.73%，求解時(shí)間有大幅度提升。除GracefulGraph 問題外，在其他搜索樹節(jié)點(diǎn)減少的問題中，兩種改進(jìn)啟發(fā)式在搜索樹節(jié)點(diǎn)上相對于改進(jìn)前平均減少46.1%和50.47%，求解時(shí)間平均降低了44.83%和29.65%。PICS和PICM分別在10、8、9和10、6、7個問題求解上優(yōu)于三種主流啟發(fā)式IBS、d/w、ABS。

各啟發(fā)式總求解實(shí)例數(shù)量及總平均時(shí)間和節(jié)點(diǎn)數(shù)如圖3所示。從圖中可以看到，IBS、d/w、ABS、c-s、c-m、PICS和PICM在限制時(shí)間內(nèi)依次成功求解了85、90、85、82、87、96、90 個問題實(shí)例，PICS 求解數(shù)量最多，c-s 最少。同時(shí)，PICS在全部求解實(shí)例中平均表現(xiàn)最優(yōu)，在多個共同求解問題中無耗時(shí)較長的求解結(jié)果，平均時(shí)間比次優(yōu)的PICM 少近9 s，平均搜索樹節(jié)點(diǎn)減少了三分之二。IBS 啟發(fā)式在多數(shù)問題求解中時(shí)長和節(jié)點(diǎn)數(shù)均大于其他啟發(fā)式。兩種主流通用啟發(fā)式ABS、d/w在個別問題求解上表現(xiàn)并不理想。從最終結(jié)果來看，在測試問題實(shí)例上，c-s與c-m啟發(fā)式僅優(yōu)于IBS啟發(fā)式。他啟發(fā)式，PICM 啟發(fā)式在問題實(shí)例driverlogw-09 求解上與c-m相比搜索樹節(jié)點(diǎn)少于后者，但求解時(shí)間恰恰相

表1 各啟發(fā)式對測試問題求解個數(shù)、平均時(shí)間和平均節(jié)點(diǎn)

圖3 各啟發(fā)式測評指標(biāo)比較

一般來說，搜索樹節(jié)點(diǎn)數(shù)與運(yùn)行時(shí)間成正比，節(jié)點(diǎn)數(shù)越大求解時(shí)間越長，但由于問題特性和啟發(fā)式時(shí)間復(fù)雜度較高等原因，一些啟發(fā)式在求解某些規(guī)模較小的問題實(shí)例時(shí)，會出現(xiàn)搜索樹節(jié)點(diǎn)數(shù)少于其他啟發(fā)式而求解時(shí)間較長的情況。表2 給出了各啟發(fā)式對部分問題實(shí)例的求解時(shí)間和節(jié)點(diǎn)的實(shí)驗(yàn)結(jié)果（TO 表示求解超時(shí)）。如表2 所示，IBS 啟發(fā)式在求解問題實(shí)例Hanoi-06 中搜索樹節(jié)點(diǎn)為其他啟發(fā)式的一半，但其求解時(shí)間遠(yuǎn)大于其反。實(shí)驗(yàn)中，這種情況在IBS 啟發(fā)式上體現(xiàn)較為明顯，但求解時(shí)間不會與Hanoi-06 實(shí)例一樣與其他啟發(fā)式相距懸殊。

表3 加入權(quán)值統(tǒng)計(jì)方法前后啟發(fā)式節(jié)點(diǎn)對比

表3給出了CRBS與d/w采用ParetoHeu結(jié)合的啟發(fā)式在加入基于權(quán)值統(tǒng)計(jì)方法前后部分問題實(shí)例求解的搜索樹節(jié)點(diǎn)數(shù)量。在多個問題實(shí)例中，加入基于權(quán)值的統(tǒng)計(jì)方法可以進(jìn)一步減少搜索樹節(jié)點(diǎn)，加快問題求解。需要注意的是，在一些問題實(shí)例上加入該方法也會導(dǎo)致節(jié)點(diǎn)數(shù)增多，如表3中后兩行所示。從所有問題求解的最終結(jié)果來看，加入權(quán)值統(tǒng)計(jì)方法的組合啟發(fā)式效果較好。

總體而言，在多種問題實(shí)例進(jìn)行測試結(jié)果顯示，采用ParetoHeu結(jié)合d/w并加入基于實(shí)例化次數(shù)權(quán)值方法的關(guān)聯(lián)啟發(fā)式方法，相對于原始啟發(fā)式有了很大性能提升，并在一些問題上與主流啟發(fā)式相比具有競爭力。

6 結(jié)束語

本文采用基于帕累托最優(yōu)的啟發(fā)式組合策略ParetoHeu將啟發(fā)式CRBS與經(jīng)典啟發(fā)式d/w相結(jié)合，以提高CRBS的求解速度和增強(qiáng)通用性，同時(shí)加入基于實(shí)例化失敗次數(shù)的權(quán)值統(tǒng)計(jì)方法，以進(jìn)一步減小搜索樹大小，提高求解效率，提出了兩種CRBS 改進(jìn)啟發(fā)式PICS與PICM。在多個國際通用測試約束滿足問題求解上，PICS 和PICM 相對與改進(jìn)前平均搜索樹節(jié)點(diǎn)和求解時(shí)間有所減少，并與主流啟發(fā)式相比具有一定競爭力。未來將對多種變量排序啟發(fā)式及約束規(guī)劃求解問題的特征做進(jìn)一步研究，以提出更為有效的獨(dú)立或組合通用啟發(fā)式。