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

肖成龍，聶紫陽，王珊珊

遼寧工程技術(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 年，在美國(guó)計(jì)算機(jī)協(xié)會(huì)ACM 成立五十周年大會(huì)上，約束規(guī)劃被列為21 世紀(jì)計(jì)算機(jī)領(lǐng)域戰(zhàn)略研究方向之一。同年，約束規(guī)劃期刊Constraints創(chuàng)刊。2005 年約束規(guī)劃協(xié)會(huì)ACP 在法國(guó)成立，旨在促進(jìn)約束規(guī)劃的理論及應(yīng)用發(fā)展，其每年舉辦的約束規(guī)劃理論及實(shí)踐國(guó)際會(huì)議CP 與整合約束規(guī)劃、人工智能及運(yùn)籌學(xué)國(guó)際會(huì)議CPAIOR（非約束規(guī)劃協(xié)會(huì)舉辦）已成為約束規(guī)劃研究交流的兩項(xiàng)重要國(guó)際學(xué)術(shù)會(huì)議。此外，近些年，在IJCAI、AAAI、ECAI 等一些國(guó)際頂級(jí)的人工智能會(huì)議上，都有對(duì)約束規(guī)劃相關(guān)研究的專題討論。當(dāng)前，約束規(guī)劃已成為人工智能領(lǐng)域的一個(gè)研究熱點(diǎn)。

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

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

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

目前，針對(duì)變量選擇已有多種獨(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ā)式自身特性等原因，一個(gè)變量排序啟發(fā)式即使在多數(shù)問題求解上剪枝效果較好，也無法保證在所有問題求解上都要優(yōu)于其他啟發(fā)式。從搜索過程出發(fā)尋找利用問題求解通性，屏蔽問題之間的差異對(duì)求解過程的影響，提出和研究改進(jìn)更為有效、適用范圍更廣的獨(dú)立或組合的通用啟發(fā)式仍是約束規(guī)劃研究中一個(gè)重要的研究方向。

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

2 相關(guān)工作

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

變量排序啟發(fā)式可分靜態(tài)變量排序啟發(fā)式和動(dòng)態(tài)變量排序啟發(fā)式兩類。靜態(tài)變量排序啟發(fā)式在搜索之前計(jì)算變量得分并確定實(shí)例化變量序列，在搜索過程中不會(huì)對(duì)變量序列進(jìn)行調(diào)整，一些已經(jīng)提出的靜態(tài)排序啟發(fā)式包括選擇相關(guān)約束最多變量的啟發(fā)式deg[14]、選擇最小約束網(wǎng)絡(luò)寬度的啟發(fā)式width[12]等。動(dòng)態(tài)變量排序啟發(fā)式在搜索期間動(dòng)態(tài)更新變量得分并調(diào)整變量排序。在實(shí)際使用中，動(dòng)態(tài)排序啟發(fā)式的應(yīng)用多于靜態(tài)排序啟發(fā)式。早期的獨(dú)立或組合動(dòng)態(tài)排序啟發(fā)式都是根據(jù)變量基本屬性來選擇變量，如第一個(gè)動(dòng)態(tài)排序啟發(fā)式dom[13]基于值域大小選擇變量、動(dòng)態(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ā)式為每個(gè)約束賦予一個(gè)權(quán)重值，當(dāng)搜索產(chǎn)生沖突時(shí)，相應(yīng)約束的權(quán)重會(huì)增加，啟發(fā)式會(huì)優(yōu)先選擇約束權(quán)重之和最大的變量。ABS 啟發(fā)式基于每個(gè)變量值域變動(dòng)頻率選擇變量。近些年提出的一些較為新穎的啟發(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ì)，從而將問題本身與變量選擇分離，使其可用于對(duì)大部分問題求解，而不是只針對(duì)一個(gè)或一類問題，具有一定的通用性。因此，對(duì)于提高變量排序啟發(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ā)式提供了一個(gè)新的思路。

除上述獨(dú)立啟發(fā)式與組合啟發(fā)式研究外，還有一些關(guān)于自適應(yīng)變量排序啟發(fā)式的研究，這類啟發(fā)式稱為超啟發(fā)式（hyper-heuristic）[30]，其根據(jù)解決方案數(shù)量、目標(biāo)函數(shù)值、已運(yùn)行時(shí)間等問題狀態(tài)特征，從包含多個(gè)獨(dú)立啟發(fā)式的序列中為搜索過程動(dòng)態(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)的集合，每個(gè)變量值域大小記作|dom( xi)|。為約束集，約束是各變量取值的制約關(guān)系。變量xi涉及約束的個(gè)數(shù)稱為度（degree），每個(gè)約束ci可記成( scp( ci),rel( ci))，scp( ci)={ x1,x2,…,xr} 是一個(gè)有序的變量子集，為約束ci所涉及到的變量，rel(ci)是scp(ci)內(nèi)每個(gè)變量值域笛卡爾乘積D(x1)×D(x2)×…×D(xr)的一個(gè)子集，每個(gè)元組τ ∈rel(ci)是一個(gè)有序的變量取值的集合，可定義為＜(x1,a1),(x2,a2),…,(xr,ar)＞，其中aj∈dom(xj),j=1,2,…,r。

約束滿足問題的求解是依次為每個(gè)變量在其值域中選擇一個(gè)合適的值，使所有變量賦值后滿足全部約束，為變量賦值的過程稱為實(shí)例化（instantiate）。在約束規(guī)劃中常采用約束傳播與回溯搜索結(jié)合的方式對(duì)CSP進(jìn)行求解。約束傳播使用相容性技術(shù)（consistency technology）在搜索前和搜索過程中從變量值域里移除不屬于任何可行解的值，進(jìn)而減小搜索空間，加快搜索進(jìn)程，出于時(shí)間復(fù)雜度和空間復(fù)雜度的考慮，約束求解器中最常使用的為弧相容（Arc Consistency，AC）[11]和邊界相容（Bounds Consistency，BC）[11]算法?；厮菟阉饔糜趯?shí)現(xiàn)對(duì)問題求解，在搜索過程中會(huì)使用變量排序啟發(fā)式選擇待實(shí)例化變量構(gòu)建搜索樹，變量排序啟發(fā)式會(huì)對(duì)搜索效率產(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 對(duì)問題的求解效率和通用性，本文提出了基于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ì)方法對(duì)帕累托候選變量集合中的變量做進(jìn)一步篩選。已有研究發(fā)現(xiàn)變量實(shí)例化的失敗次數(shù)在一定程度上可說明該變量與已實(shí)例化變量集之間的沖突關(guān)系[22]，因此選擇實(shí)例化失敗次數(shù)最多的變量作為待實(shí)例化變量可增加搜索過程中發(fā)生沖突的可能，從而使搜索樹盡早剪枝，加快問題求解。

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

4.2 PICRBS流程

PICRBS流程圖如圖2所示。在搜索期間，PICRBS維持存儲(chǔ)所有變量對(duì)關(guān)聯(lián)性的對(duì)稱關(guān)聯(lián)矩陣、統(tǒng)計(jì)約束權(quán)值和各變量實(shí)例化失敗次數(shù)。進(jìn)行變量選擇時(shí)，PICRBS遍歷未實(shí)例化變量集合FutVars，對(duì)集合中變量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中。對(duì)于ParetoFront中得分相同的變量，PICRBS 通過變量實(shí)例化失敗次數(shù)進(jìn)行進(jìn)一步篩選，選擇搜索期間實(shí)例化失敗次數(shù)最多的變量作為待實(shí)例化變量加入集合MaxInsta中，若MaxInsta中存在多個(gè)失敗次數(shù)相同的變量，則對(duì)這些變量進(jìn)行隨機(jī)選擇。在變量實(shí)例化后，如果搜索未發(fā)生沖突，對(duì)關(guān)聯(lián)矩陣進(jìn)行更新。反之，更新關(guān)聯(lián)矩陣同時(shí)對(duì)約束權(quán)值和變量實(shí)例化失敗次數(shù)進(jìn)行加權(quán)更新。

關(guān)聯(lián)矩陣更新方式及PICRBS中CRBS啟發(fā)式得分計(jì)算規(guī)則如下：當(dāng)選擇某個(gè)變量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 會(huì)將crbs-sum(xi)/dom(xi) 和crbs-max(xi)/dom(xi) 作 為 最終啟發(fā)式得分。

約束權(quán)值weight[c]是啟發(fā)式dom/wdeg為每個(gè)約束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í)先建立兩個(gè)空集合ParetoFront 和MaxInsta 分別用于存儲(chǔ)帕累托候選變量以及實(shí)例化失敗次數(shù)最多變量，tempMaxInsta 記錄當(dāng)前最大實(shí)例化失敗次數(shù)。在構(gòu)建搜索樹時(shí)，對(duì)于未實(shí)例化變量集合FutVars 中的變量進(jìn)行遍歷，選擇兩種啟發(fā)式得分都最高的變量加入集合，在遍歷過程中對(duì)ParetoFront 進(jìn)行動(dòng)態(tài)更新。待所有變量遍歷完畢后，通過基于變量實(shí)例化失敗次數(shù)對(duì)ParetoFront 中變量做進(jìn)一步篩選，選擇以往搜索中實(shí)例化失敗次數(shù)最多的一個(gè)變量或多個(gè)變量加入MaxInsta 集合，若MaxInsta 中多于一個(gè)變量，則對(duì)變量進(jìn)行隨機(jī)選取，最后返回一個(gè)變量構(gòu)建搜索樹。

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

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

本文實(shí)驗(yàn)數(shù)據(jù)為國(guó)際測(cè)試通用的約束滿足問題，其中一部分為2018年約束求解器競(jìng)賽基準(zhǔn)問題。實(shí)驗(yàn)中，對(duì)于每類問題分別選取了不同規(guī)模的實(shí)例，共177 個(gè)，這些實(shí)例均可在http：//xcsp.org/上下載。測(cè)試所用的基準(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 對(duì)比的啟發(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ù)增長(zhǎng)，公式為cutoff=cutoff'+init_cutoff×ρk。 cutoff′ 為上一次失敗次數(shù)，k 為重啟次數(shù)。搜索使用二元分支深度優(yōu)先搜索，求解時(shí)限為1 200 s。對(duì) 于 啟 發(fā) 式crbs-sum 和PICS，參 數(shù)θ 設(shè) 為0.1。在PICS 和PICM 中為了選取最高得分，dom/wdeg計(jì)算采用對(duì)于實(shí)驗(yàn)中的隨機(jī)數(shù)，隨機(jī)種子均設(shè)為0。

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

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

表1 給出了各啟發(fā)式對(duì)于測(cè)試問題實(shí)例的成功求解個(gè)數(shù)、平均時(shí)間和平均節(jié)點(diǎn)。問題名稱后括號(hào)內(nèi)為實(shí)驗(yàn)選取問題實(shí)例個(gè)數(shù)，時(shí)間和節(jié)點(diǎn)后括號(hào)內(nèi)為該類問題啟發(fā)式均可求解實(shí)例個(gè)數(shù)。PICS 和PICM 作為本文提出的c-s 和c-m 改進(jìn)啟發(fā)式分別在11/13、9/13 個(gè)問題求解上相對(duì)于后兩者搜索樹節(jié)點(diǎn)有所減少，在Graceful-Graph 問題上最為明顯，分別減少了99.75%和98.73%，求解時(shí)間有大幅度提升。除GracefulGraph 問題外，在其他搜索樹節(jié)點(diǎn)減少的問題中，兩種改進(jìn)啟發(fā)式在搜索樹節(jié)點(diǎn)上相對(duì)于改進(jìn)前平均減少46.1%和50.47%，求解時(shí)間平均降低了44.83%和29.65%。PICS和PICM分別在10、8、9和10、6、7個(gè)問題求解上優(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 個(gè)問題實(shí)例，PICS 求解數(shù)量最多，c-s 最少。同時(shí)，PICS在全部求解實(shí)例中平均表現(xiàn)最優(yōu)，在多個(gè)共同求解問題中無耗時(shí)較長(zhǎng)的求解結(jié)果，平均時(shí)間比次優(yōu)的PICM 少近9 s，平均搜索樹節(jié)點(diǎn)減少了三分之二。IBS 啟發(fā)式在多數(shù)問題求解中時(shí)長(zhǎng)和節(jié)點(diǎn)數(shù)均大于其他啟發(fā)式。兩種主流通用啟發(fā)式ABS、d/w在個(gè)別問題求解上表現(xiàn)并不理想。從最終結(jié)果來看，在測(cè)試問題實(shí)例上，c-s與c-m啟發(fā)式僅優(yōu)于IBS啟發(fā)式。他啟發(fā)式，PICM 啟發(fā)式在問題實(shí)例driverlogw-09 求解上與c-m相比搜索樹節(jié)點(diǎn)少于后者，但求解時(shí)間恰恰相

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

圖3 各啟發(fā)式測(cè)評(píng)指標(biāo)比較

一般來說，搜索樹節(jié)點(diǎn)數(shù)與運(yùn)行時(shí)間成正比，節(jié)點(diǎn)數(shù)越大求解時(shí)間越長(zhǎng)，但由于問題特性和啟發(fā)式時(shí)間復(fù)雜度較高等原因，一些啟發(fā)式在求解某些規(guī)模較小的問題實(shí)例時(shí)，會(huì)出現(xiàn)搜索樹節(jié)點(diǎn)數(shù)少于其他啟發(fā)式而求解時(shí)間較長(zhǎng)的情況。表2 給出了各啟發(fā)式對(duì)部分問題實(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í)間不會(huì)與Hanoi-06 實(shí)例一樣與其他啟發(fā)式相距懸殊。

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

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

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

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。在多個(gè)國(guó)際通用測(cè)試約束滿足問題求解上，PICS 和PICM 相對(duì)與改進(jìn)前平均搜索樹節(jié)點(diǎn)和求解時(shí)間有所減少，并與主流啟發(fā)式相比具有一定競(jìng)爭(zhēng)力。未來將對(duì)多種變量排序啟發(fā)式及約束規(guī)劃求解問題的特征做進(jìn)一步研究，以提出更為有效的獨(dú)立或組合通用啟發(fā)式。