李飛龍　趙春艷　范如夢(mèng)

摘 要：為了求解具有增長(zhǎng)取值域的隨機(jī)約束滿足問題（CSP），提出了一種基于禁忌搜索并與模擬退火相結(jié)合的算法。首先，利用禁忌搜索得到一組啟發(fā)式的初始賦值，即由一個(gè)隨機(jī)初始化的可行解通過鄰域構(gòu)造一組候選解，再利用禁忌表使候選解向最小化目標(biāo)函數(shù)值的方向移動(dòng);如果得到的最優(yōu)賦值不是問題的解，就把它作為啟發(fā)式的初始賦值，再執(zhí)行模擬退火對(duì)這組賦值進(jìn)行修正直到得到全局最優(yōu)解。數(shù)值實(shí)驗(yàn)結(jié)果表明，所提算法在接近問題的理論相變閾值時(shí)仍然能有效地找到問題的解，與其他局部搜索算法相比，表現(xiàn)出了顯著的優(yōu)越性，可用于隨機(jī)CSP的算法設(shè)計(jì)。

關(guān)鍵詞：隨機(jī)約束滿足問題;RB模型;相變現(xiàn)象;禁忌搜索;模擬退火;算法效率

中圖分類號(hào)： TP301.6文獻(xiàn)標(biāo)志碼：A

Solving random constraint satisfaction problems based on

tabu search algorithm

LI Feilong， ZHAO Chunyan*， FAN Rumeng

（College of Science， University of Shanghai for Science and Technology， Shanghai 200093， China）

Abstract： A novel algorithm based on tabu search and combined with simulated annealing was proposed to solve random Constraint Satisfaction Problem （CSP） with growing domain. Firstly， tabu search was used to obtain a set of initial heuristic assignments， which? meant a set of candidate solutions were constructed based on a randomly initialized feasible solution through neighborhood， and then the tabu table was used to move the candidate solutions to the direction of minimizing the objective function value. If the obtained optimal assignment was not the solution of the problem， the assignment would be used as the initial heuristic assignment and then simulated annealing was performed to correct the set of assignments until the global optimal solution was obtained. The numerical experiments demonstrate that， the proposed algorithm can effectively find the solution of problem when approaching the theoretical phase transition threshold of problem， and it shows obvious superiority compared with other local search algorithms. The proposed algorithm can be applied to the algorithm design of random CSP.

Key words： random Constraint Satisfaction Problem （CSP）;Revised B （RB） model; phase transition phenomenon; tabu search; simulated annealing; algorithm efficiency

0 引言

約束滿足問題（Constraint Satisfaction Problem， CSP）是人工智能領(lǐng)域的一個(gè)重要分支[1-2]，它在物流規(guī)劃、生產(chǎn)調(diào)度、產(chǎn)品配置器、生物信息等領(lǐng)域都有非常廣泛的應(yīng)用。

CSP模型是探索非確定性多項(xiàng)式（Non-deterministic Polynomial， NP）-完全問題難解性的重要基礎(chǔ)。為了克服標(biāo)準(zhǔn)CSP模型中B模型的平凡漸進(jìn)不可滿足性[3-5]，Xu等[6]提出了RB（Revised B）模型并證明了該模型具有精確的可滿足性相變現(xiàn)象。隨后，Xu等[7-8]又從理論和實(shí)驗(yàn)上證明了RB（Revised B）模型在相變區(qū)域能產(chǎn)生大量的難解實(shí)例。近年來，RB模型受到了國(guó)內(nèi)外研究學(xué)者的廣泛研究[9-12]。理論上，沈靜等[13-16]提出了基于RB模型的推廣模型;Zhou等[17]改進(jìn)了發(fā)生相變的條件。實(shí)驗(yàn)上，Zhao等[18-20]設(shè)計(jì)了基于置信傳播的算法來求解RB模型;原志強(qiáng)等[21]提出了改進(jìn)的模擬退火（Simulated Annealing， SA）和遺傳算法;吳撥榮等[22]將置信傳播和模擬退火相結(jié)合來求解RB模型。此外，基于RB模型的難解算例被用于各種算法競(jìng)賽[23]。

本文提出了一種基于禁忌搜索（Tabu Search， TS）并與模擬退火（SA）相結(jié)合的高效算法來求解RB模型這類具有可變?nèi)≈涤虻碾S機(jī)CSP， 命名為TS-SA。首先，利用TS得到一個(gè)啟發(fā)式的初始賦值，即由一個(gè)初始可行解通過鄰域生成一組候選解，利用禁忌表使得候選解向目標(biāo)函數(shù)值減小的方向移動(dòng)。如果得到的賦值不是問題的解，再利用SA對(duì)該賦值進(jìn)行優(yōu)化直至得到最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，TS-SA算法的求解性能顯著優(yōu)于TS、SA以及其他局部搜索算法。在難解區(qū)域即使找不到解，得到的最優(yōu)解僅使得極少數(shù)的約束是不可滿足的。

1 RB模型

RB模型由一個(gè)變量集合X={x1，x2，…，xN}和一個(gè)約束集合C={C1，C2，…，CM}構(gòu)成[6]。每個(gè)變量xi都從定義域D={1，2，…，dN}中取值，這里dN=Nα，α>0為常數(shù)。不難看出，RB模型中變量的取值域規(guī)模隨著變量數(shù)的增加呈多項(xiàng)式級(jí)增長(zhǎng)，因此RB模型可以看作是一類具有可變?nèi)≈涤虻碾S機(jī)CSP。每個(gè)約束Ca都由一個(gè)變量的子集Xa和其相應(yīng)的不相容賦值集合Qa所構(gòu)成。從N個(gè)變量中隨機(jī)選取k（k≥2）個(gè)不同的變量構(gòu)成Xa，從Xa可能的dk個(gè)賦值中隨機(jī)不重復(fù)地選取pdk個(gè)k元賦值作為不相容賦值集合Qa，這里00是常數(shù)）個(gè)就構(gòu)成了RB模型的一個(gè)隨機(jī)實(shí)例RB（k，N，r，α，p） 。

若能找到這N個(gè)變量的一組完全賦值，使得所有約束同時(shí)被滿足，這組賦值就是RB（k，N，r，α，p）的一個(gè)解。文獻(xiàn)[6]中已經(jīng)嚴(yán)格證明了RB模型存在精確的可滿足性相變現(xiàn)象，即用Pr（SAT）表示隨機(jī)實(shí)例有解的概率，則有以下結(jié)論成立：

定理 設(shè)ps=1-e-α/r，若α>1/k，r>0是兩個(gè)常數(shù)，且滿足ke-α/r≥1 ，則：

limN→∞ Pr（SAT）=1， p

0，p>ps （1）

該定理表明，當(dāng)N→∞時(shí)，約束緊度存在一個(gè)閾值ps，若p>ps，RB模型隨機(jī)實(shí)例有解的概率趨近于0;若p

由于二元RB模型（即k=2）是NP-完全問題，故下面的算法均用于求解二元RB模型的隨機(jī)實(shí)例。而k>2的情形可以通過多項(xiàng)式時(shí)間歸約為二元的情形。

2 TS算法

TS算法是對(duì)局部鄰域搜索算法的推廣，是對(duì)人類智力過程的一種模擬，是人工智能的一種體現(xiàn)。它區(qū)別于其他現(xiàn)代啟發(fā)式算法的顯著特點(diǎn)是利用記憶來引導(dǎo)算法的搜索過程。TS算法涉及鄰域、候選解、禁忌表、禁忌長(zhǎng)度、藐視準(zhǔn)則等概念。在鄰域搜索的基礎(chǔ)上，通過禁忌表來避免重復(fù)搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證搜索空間的多樣化，最終實(shí)現(xiàn)對(duì)全局的優(yōu)化。

為將TS算法應(yīng)用于求解RB模型，先給出目標(biāo)函數(shù)的定義。對(duì)RB模型的一個(gè)隨機(jī)實(shí)例，設(shè)N個(gè)變量的一組完全賦值為X0=（σ1，σ2，…，σN） ，相應(yīng)的約束Ca中變量的賦值為X0a=（σ1a，σ2a，…，σNa）。定義目標(biāo)函數(shù)為不可滿足約束的數(shù)目，即：

E（X0）=∑Ma=1[1-S（X0a）]（2）

其中：

S（X0a）=1， σ1a，σ2a，…，σkaQa

0，σ1a，σ2a，…，σka∈Qa（3）

由此可見，若一組賦值使得目標(biāo)函數(shù)值為0，則這組賦值就是實(shí)例的解;否則就不是解。

給定RB模型變量的一組賦值，先隨機(jī)且不重復(fù)地從這N個(gè)變量中選取NCa個(gè)變量對(duì)Xij=（xi，xj）構(gòu)成鄰域變量集合。采用兩種不同的策略改變這組賦值中每對(duì)所對(duì)應(yīng)的賦值構(gòu)成NCa組候選解。這兩種策略分別是：將Xij中xi和xj的賦值相互交換;重新對(duì)xi和xj進(jìn)行隨機(jī)賦值。將這組候選解中使得目標(biāo)函數(shù)取得最小值的那組賦值作為最優(yōu)候選解，它所對(duì)應(yīng)的Xij作為禁忌對(duì)象置入禁忌表中。禁忌表可以看作是一個(gè)N×N的矩陣，矩陣中的元素是禁忌對(duì)象Xij。禁忌表的主要目的是禁止這些禁忌對(duì)象在近期內(nèi)參與最優(yōu)候選解的選擇，從而避免搜索過程中出現(xiàn)循環(huán)和陷入局部最優(yōu)的現(xiàn)象。在最優(yōu)候選解更新過程中，要設(shè)定禁忌對(duì)象不允許被選取的最大次數(shù)即禁忌長(zhǎng)度。禁忌長(zhǎng)度的選取與問題特征有關(guān)，它在很大程度上決定了算法的計(jì)算復(fù)雜性。在TS算法中，設(shè)禁忌長(zhǎng)度LTabu=N（N-1）/2，這樣能保證更新禁忌表時(shí)，至少有一個(gè)變量對(duì)Xij被選擇。當(dāng)禁忌長(zhǎng)度為0時(shí)，禁忌表會(huì)釋放相應(yīng)的禁忌對(duì)象，重新參與候選解的選擇。在賦值更新過程中，可以設(shè)置藐視準(zhǔn)則，也就是最優(yōu)候選解優(yōu)于當(dāng)前最優(yōu)解時(shí)，即使這組賦值中所對(duì)應(yīng)的Xij在禁忌表中，也可以忽視其禁忌屬性，用它代替當(dāng)前解和最優(yōu)解。若不存在上述最優(yōu)候選解，則在候選解中選擇非禁忌的次優(yōu)候選解為新的當(dāng)前解，將對(duì)應(yīng)的Xij加入禁忌表，同時(shí)修改禁忌表中各禁忌對(duì)象的禁忌長(zhǎng)度。重復(fù)上述迭代搜索過程，直到最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值為零，則停止迭代;否則，直至達(dá)到最大迭代次數(shù)。

TS算法的具體步驟如下：

輸入 二元RB模型的一個(gè)隨機(jī)實(shí)例以及TS算法中候選解的數(shù)目NCa，最大迭代次數(shù)tmax;

輸出 找到的最優(yōu)解以及對(duì)應(yīng)的目標(biāo)函數(shù)值。

步驟1 初始化禁忌表為N×N的零矩陣，由公式計(jì)算禁忌長(zhǎng)度，隨機(jī)初始化一組賦值X0。

步驟2 t=0。

步驟3 計(jì)算目標(biāo)函數(shù)值E（X0），如果E（X0）=0，則輸出最優(yōu)解及對(duì)應(yīng)的目標(biāo)函數(shù)值。

步驟4 隨機(jī)生成鄰域變量集合，對(duì)鄰域變量集合采用兩種策略構(gòu)造NCa組候選解。計(jì)算候選解目標(biāo)函數(shù)值，按照從小到大保留較優(yōu)的NCa/2組候選解并記錄對(duì)應(yīng)的變量對(duì)Xij。將使得目標(biāo)函數(shù)值最小的候選解設(shè)為最優(yōu)候選解，并記錄對(duì)應(yīng)的目標(biāo)函數(shù)值。

步驟5 如果最優(yōu)候選解優(yōu)于當(dāng)前迭代的最優(yōu)解或滿足藐視準(zhǔn)則，則將最優(yōu)候選解作為當(dāng)前解和最優(yōu)解，并將其他禁忌對(duì)象的禁忌長(zhǎng)度減1;否則將候選解中次優(yōu)且在禁忌表中對(duì)應(yīng)的禁忌長(zhǎng)度為0的候選解作為當(dāng)前解，并將其他禁忌對(duì)象的禁忌長(zhǎng)度減1。

步驟6 t=t+1。

步驟7 如果t>tmax，則輸出最優(yōu)解及對(duì)應(yīng)的目標(biāo)函數(shù)值;否則返回步驟3。

可以看出，TS算法先通過鄰域構(gòu)造了一組候選解，增強(qiáng)了全局搜索能力;再利用禁忌表使得目標(biāo)函數(shù)值向減少的方向移動(dòng)，使算法具備較好的局部搜索能力。雖然該算法受初始賦值和鄰域結(jié)構(gòu)的影響較大，很難得到全局最優(yōu)解，但是搜索過程分布性好，搜索得到的最優(yōu)解僅使得較少的約束是不可滿足的。

SA算法是啟發(fā)式算法的一種。該算法從高溫出發(fā)，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)時(shí)能概率性地跳出并最終趨于全局最優(yōu)?？梢姡琒A算法的局部搜索能力很強(qiáng)，可以很好地避免陷入局部最優(yōu);但是其對(duì)初始解的依賴性較大?？紤]到TS算法較強(qiáng)的全局搜索能力以及SA算法較強(qiáng)的局部搜索能力，本文將兩種算法結(jié)合提出了TS-SA算法來求解RB模型這類具有可變?nèi)≈涤虻碾S機(jī)CSP。

3 TS-SA算法

TS-SA算法可以概括為兩步：第一步，利用TS算法得到最優(yōu)解;第二步，若利用TS算法得到的最優(yōu)解不是RB模型隨機(jī)實(shí)例的解，就將此解作為SA算法的啟發(fā)式初始賦值，再執(zhí)行SA算法對(duì)該賦值進(jìn)行修正，直至得到最優(yōu)解。

TS-SA算法具體步驟如下：

輸入 二元RB模型的一個(gè)隨機(jī)實(shí)例，以及TS算法中候選解的個(gè)數(shù)NCa，最大迭代次數(shù)tmax;SA算法中初始溫度T0，終止溫度Tf，溫度控制參數(shù)a，同一溫度下最大迭代次數(shù)L。

輸出 找到的最優(yōu)解以及對(duì)應(yīng)的目標(biāo)函數(shù)值。

步驟1 運(yùn)行上述TS算法，將返回的最優(yōu)賦值作為當(dāng)前解X0。

步驟2 T=T0。

步驟3 i=0。

步驟4 計(jì)算目標(biāo)函數(shù)值E（X0），如果E（X0）=0，則輸出最優(yōu)解及對(duì)應(yīng)的目標(biāo)函數(shù)值。

步驟5 隨機(jī)生成一個(gè)0到1之間的實(shí)數(shù)rand1。程序前

if （rand1<3/T） {令X0=Xbest，隨機(jī)選取一個(gè)不可滿足的約束，從其所關(guān)聯(lián)變量的協(xié)調(diào)賦值集合中隨機(jī)選取一組賦值，從而得到一組新的賦值記作Xnew}

else {對(duì)于X0，隨機(jī)選取一個(gè)不可滿足的約束，從其所關(guān)聯(lián)變量的協(xié)調(diào)賦值集合中隨機(jī)選取一組賦值，從而得到一組新的賦值記作Xnew}。程序后

步驟6 計(jì)算ΔE=E（X0）-E（Xnew） ;程序前

if （ΔE<0）{隨機(jī)取一個(gè)0到1之間的實(shí)數(shù)rand2

if （rand2

else {go to 步驟7}}

else {令X0=Xnew}。

程序后步驟7 計(jì)算當(dāng)前解的目標(biāo)函數(shù)值E（X0），如果優(yōu)于最優(yōu)解，則將當(dāng)前解賦予最優(yōu)解。

步驟8 i=i+1。

步驟9 如果i>L，則T=a·T;否則返回步驟4。

步驟10 如果T

由此可以看出，TS-SA算法先通過TS算法得到啟發(fā)式的初始賦值，再執(zhí)行SA算法對(duì)該賦值進(jìn)行修正直至得到最優(yōu)解。其中，TS算法通過鄰域構(gòu)造候選解，是多個(gè)體進(jìn)行迭代搜索，有效地避免了陷入局部最優(yōu)解。SA算法是單個(gè)體迭代搜索，由以TS算法得到的啟發(fā)式初始賦值避免了SA算法對(duì)初始賦值的依賴問題。TS-SA算法有效地利用了TS和SA這兩個(gè)算法的優(yōu)點(diǎn)，因此可以表現(xiàn)出良好的求解性能。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 TS-SA算法結(jié)果

在RB模型中，取k=2，α=0.8，r=3，N∈{20，40，60，80，100}，由第1章中的定理可以求出理論的可滿足性相變點(diǎn)為ps=0.234。在不同的問題規(guī)模N下，RB模型的定義域規(guī)模d、約束數(shù)目M等參數(shù)值如表1所示。

在TS算法中，取候選解個(gè)數(shù)NCa=120，最大迭代次數(shù)tmax=103，LTabu由禁忌長(zhǎng)度公式計(jì)算。在隨機(jī)生成的50個(gè)實(shí)例RB（2，N，3，0.8，p）上測(cè)試TS算法的求解性能，求解概率如圖1所示。從圖1可以看出，當(dāng)N=20時(shí)，TS算法在約束緊度p≤0.15的范圍內(nèi)以概率1找到解，而在p≥0.23時(shí)算法失效;在N=100時(shí)，TS算法在約束緊度p≤0.09的范圍內(nèi)以概率1找到解，而在p≥0.12時(shí)算法失效。若取最大迭代次數(shù)tmax=2000，求解概率如圖2所示，取N=60。從圖2可以看出，增加迭代次數(shù)并沒有從本質(zhì)上改變算法意義上RB模型發(fā)生相變的區(qū)域，僅在個(gè)別點(diǎn)處提高了求解概率。因此，本文中算法的最大迭代次數(shù)取tmax=1000。

取N=40，TS算法求解隨機(jī)實(shí)例的平均迭代次數(shù)和平均運(yùn)行時(shí)間如表2所示，其中：t表示平均迭代次數(shù)， time表示平均運(yùn)行時(shí)間。從表2中可以看出，隨著p的不斷增加，TS算法的運(yùn)行時(shí)間呈指數(shù)級(jí)增長(zhǎng)。當(dāng)p≤0.14時(shí)，TS算法可以在較短的時(shí)間內(nèi)通過較少的迭代次數(shù)以概率1收斂到實(shí)例的解;當(dāng)0.14

在 TS-SA算法中，取候選解個(gè)數(shù)NCa=120，最大迭代次數(shù)tmax=103，LTabu由禁忌長(zhǎng)度公式計(jì)算。取初始溫度T0=97，終止溫度Tf=3，溫度控制參數(shù)a=0.95，同一溫度下最大迭代次數(shù)L=103。對(duì)于不同的問題規(guī)模N，分別在隨機(jī)生成的50個(gè)實(shí)例RB（2，N，3，0.8，p）上測(cè)試TS-SA算法的求解性能，求解概率如圖3所示。從圖3中可以看出：當(dāng)N=20時(shí)，TS-SA算法在約束緊度p≤0.16的范圍內(nèi)以概率1找到解，而在p≥0.23時(shí)算法失效;當(dāng)N=100時(shí)，TS-SA算法在約束緊度p≤0.12的范圍內(nèi)以概率1找到解，而在p≥0.17時(shí)算法失效。

TS算法和TS-SA算法在求解二元RB模型隨機(jī)實(shí)例過程中，在p=0.10和p=0.13時(shí)算法的平均運(yùn)行時(shí)間分別如圖4和圖5所示。從圖4（a）和圖5（a）可以看出，兩種算法在N≤100時(shí)平均運(yùn)行時(shí)間基本一樣。這是由于在p≤0.10時(shí)TS算法起主要作用，它能比較有效地找到實(shí)例的解，此時(shí)并不需要運(yùn)行SA算法對(duì)TS算法得到的最優(yōu)賦值進(jìn)行優(yōu)化或者僅在少數(shù)情況下需要再執(zhí)行SA算法。從圖4（b）和圖5（b）可以看出，這兩種算法在N≤80時(shí)平均運(yùn)行時(shí)間基本一樣;而當(dāng)N=100時(shí)，TS-SA算法的運(yùn)行時(shí)間明顯比TS算法多。這說明在p=0.13時(shí)隨著變量數(shù)目N的增加，需要再運(yùn)行SA算法對(duì)TS算法得到的賦值進(jìn)行修正才能得到實(shí)例的解或者最優(yōu)解。

當(dāng)p≥0.16時(shí)，TS算法和TS-SA開始失效，即不能有效地找到二元RB模型隨機(jī)的解，也就是得到的最優(yōu)解不能使得所有約束都是可滿足的。對(duì)于不同的問題規(guī)模N，由TS算法和TS-SA算法得到的最優(yōu)解使得約束不可滿足的平均數(shù)目如表3～4所示。從表3和表4可以看出，在鄰近相變點(diǎn)時(shí)TS-SA算法雖然找不到實(shí)例解，但是得到的最優(yōu)解僅使得極少數(shù)的約束是不可滿足的;并且TS-SA算法求解RB模型時(shí)得到的平均不可滿足約束數(shù)目明顯少于TS算法所得到的。

TS-SA算法總能收斂到一組賦值，該賦值是此算法得到的最優(yōu)解。事實(shí)上，當(dāng)p較小時(shí)，只執(zhí)行TS算法就能找到實(shí)例的解。隨著p的不斷增大，TS得到的賦值逐漸不能使得目標(biāo)函數(shù)為0，需要執(zhí)行SA算法對(duì)由TS算法得到的啟發(fā)式初始賦值進(jìn)行修正，直到得到全局最優(yōu)解。如圖6所示，可以看到，取N=40，p從0.15增大到0.19時(shí)，在TS-SA算法找到解的實(shí)例中，僅執(zhí)行TS算法就能找到解的實(shí)例數(shù)目比例在逐漸降低，需要執(zhí)行SA算法才能找到解的實(shí)例數(shù)目占比逐漸增大。這表明在TS算法失效的情況下，SA算法的局部搜索能力開始占主導(dǎo)地位。直到非常接近理論相變點(diǎn)時(shí)，TS-SA算法失效，不能收斂到實(shí)例的解。

4.2 算法對(duì)比

將本文提出的TS-SA算法與TS算法，文獻(xiàn)[21]中提出的GSA（Genetic Simulated Annealing）算法、RSA（Revised Simulated Annealing）算法，文獻(xiàn)[22]中提出的BP-RSA-1（Belief Propagation-Revised Simulated Annealing-1）、BP-RSA-2（Belief Propagation-Revised Simulated Annealing-2）算法進(jìn)行對(duì)比。特別地，取N=100，對(duì)于不同的約束緊度p，分別在隨機(jī)生成的50個(gè)實(shí)例RB（2，N，3，0.8，p）上運(yùn)行算法，得到的求解概率如圖7所示。由圖7可以看出，本文提出的TS-SA算法求解效率明顯優(yōu)于TS算法、RSA算法;與BP-RSA-1算法、BP-RSA-2算法、GSA算法相比，TS-SA算法也在一定程度上提高了求解概率。

取N=60，p=0.13時(shí)，TS-SA算法、BP-RSA-1算法、GSA算法和RSA算法的平均運(yùn)行時(shí)間如圖8所示。由圖8可以看出，當(dāng)N較大時(shí)，與其他算法相比，本文提出的TS-SA算法花費(fèi)了較多的運(yùn)行時(shí)間。而由圖4可知，當(dāng)N較小時(shí)，只運(yùn)行TS算法就可以花費(fèi)較少的時(shí)間有效地找到實(shí)例的解。這是因?yàn)榇蠖鄶?shù)的實(shí)例都需要花費(fèi)時(shí)間來執(zhí)行SA算法對(duì)由TS得到的啟發(fā)式初始賦值進(jìn)行修正。

取N=60，p≥0.17，五種算法求解RB模型隨機(jī)實(shí)例找不到解時(shí)，得到的平均不可滿足約束數(shù)目如表5所示。由表5可以看出，由TS算法得到的不可滿足約束的數(shù)目要小于RSA算法所得到的，可見TS算法的全局搜索能力是優(yōu)于RSA算法的。從求解概率來看，RSA算法的局部搜索能力優(yōu)于TS算法。而將TS和SA結(jié)合得到的TS-SA算法所得到的平均不可滿足約束數(shù)目是最少的。當(dāng)p=0.17時(shí)，TS-SA算法的平均最少不可滿足約束的數(shù)目占約束總數(shù)的比例約為0.3%;當(dāng)p=0.20時(shí)，TS-SA算法的平均最少不可滿足約束的數(shù)目占約束總數(shù)的比例約為1.1%。這充分表明了本文提出的TS-SA算法雖然在非常接近理論相變點(diǎn)時(shí)找不到實(shí)例的解，但得到的最優(yōu)解僅使得近1%的約束是不可滿足的。

5 結(jié)語(yǔ)

本文提出了一種基于TS并與SA相結(jié)合的高效算法TS-SA來求解RB模型這類具有可變?nèi)≈涤虻碾S機(jī)約束滿足問題（CSP）。TS-SA算法是利用TS算法得到最優(yōu)初始賦值，在不是問題解的情況下再執(zhí)行SA算法對(duì)這個(gè)啟發(fā)式的初始賦值進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，在接近理論相變點(diǎn)時(shí)，TS-SA算法能有效地找到隨機(jī)實(shí)例的解;在理論相變點(diǎn)附近，即使算法失效，得到的最優(yōu)解僅使得極少數(shù)的約束是不可滿足的。這表明TS-SA算法充分利用了TS和SA算法的優(yōu)勢(shì)，既在全局搜索，又對(duì)局部?jī)?yōu)化，表現(xiàn)出了良好的求解性能，可用于對(duì)隨機(jī)CSP的算法設(shè)計(jì)。接下來的工作中我們會(huì)嘗試研究將禁忌搜索算法與其他局部搜索算法相結(jié)合來進(jìn)一步優(yōu)化算法的求解性能，從而探索CSP解空間的演化規(guī)律，以及問題難解性的根源。

參考文獻(xiàn) （References）

[1]TSANG E. A glimpse of constraint satisfaction [J]. Artificial Intelligence Review， 1999， 13（3）： 215-227.

[2]MOLLOY M. Models for random constraint satisfaction problems [J]. SIAM Journal of Computing， 2003， 32（4）： 935-949.

[3]SMITH B M， DYER M E. Locating the phase transition in binary constraint satisfaction problems [J]. Artificial Intelligence， 1996， 81（1/2）： 155-181

[4]ACHLIOPTAS D， MOLLOY M S O， KIROUSIS L M， et al. Random constraint satisfaction： a more accurate picture [J]. Constraints， 2001， 6（4）： 329-344.

[5]GENT I P， MACINTYRE E， PROSSER P， et al. Random constraint satisfaction： flaws and structure [J]. Constraints， 2001， 6（4）： 345-372.

[6]XU K， LI W. Exact phase transitions in random constraint satisfaction problems [J]. Journal of Artificial Intelligence Research， 2000， 12（1）： 93-103.

[7]XU K， LI W. Many hard examples in exact phase transitions [J]. Theoretical Computer Science， 2006， 355（3）： 291-302.

[8]XU K， BOUSSEMART F， HEMERY F， et al. Random constraint satisfaction： Easy generation of hard （satisfiable） instances [J]. Artificial Intelligence， 2007， 171（8/9）： 514-534.

[9]LIU T， LIN X， WANG C， et al. Large hinge width on sparse random hypergraphas [C]// Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Reston： AAAI， 2011： 611-616.

[10]ZHAO C， ZHENG Z. Threshold behaviors of a random constraint satisfaction problem with exact phase transitions [J]. Information Processing Letters， 2011， 111（20）： 985-988.

[11]徐偉，鞏馥洲.值域增長(zhǎng)約束滿足問題的無回溯與隨機(jī)行走策略的算法復(fù)雜性分析[J].計(jì)算機(jī)科學(xué)，2014，41（4）：205-210.（XU W， GONG F Z. Computational complexity analysis of backtrack-free and random-walk strategies on constraint satisfaction problems with growing domains [J]. Computer Science， 2014， 41（4）： 205-210.）

[12]王曉峰，許道云.RB模型實(shí)例集上置信傳播算法的收斂性[J].軟件學(xué)報(bào)，2016，27（11）：2712-2724.（WANG X F， XU D Y. Convergence of the belief propagation algorithm for RB model instances [J]. Journal of Software， 2016， 27（11）： 2712-2724.）

[13]沈靜.約束滿足問題的模型構(gòu)造和相變現(xiàn)象[D].武漢：華中師范大學(xué)，2011：13-30.（SHEN J. A model of random constraint satisfaction problems and phase transitions [D]. Wuhan： Central China Normal University， 2011： 13-30.）

[14]沈靜，梅丹.可滿足實(shí)例的歸結(jié)復(fù)雜度[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（22）：69-72.（SHEN J， MEI D. Resolution complexity of satisfiability instances [J]. Computer Engineering and Applications， 2014， 50（22）： 69-72.）

[15]SHEN J， REN Y. Bounding the scaling window of random constraint satisfaction problems [J]. Journal of Combinatorial Optimization， 2016， 31（2）： 786-801.

[16]沈靜，任耀峰，梅丹，等.一種產(chǎn)生可滿足性難解實(shí)例的模型[J].海軍工程大學(xué)學(xué)報(bào)，2016，28（3）：5-8.（SHEN J， REN Y F， MEI D， et al. A model to generate hard satisfiable instances [J]. Journal of Naval University of Engineering， 2016， 28（3）： 5-8.）

[17]ZHOU G， GAO Z， LIU J. On the constraint length of random-CSP [J]. Journal of Combinatorial Optimization， 2015， 30（1）： 188-200.

[18]ZHAO C， ZHOU H， ZHENG Z， et al. A message-passing approach to random constraint satisfaction problems with growing domains [J]. Journal of Statistical Mechanics： Theory and Experiment， 2011（2）： Article No. P02019.

[19]趙春艷，鄭志明.一種基于變量熵求解約束滿足問題的置信傳播算法[J].中國(guó)科學(xué)：信息科學(xué)，2012，42（9）：1170-1180.（ZHAO C Y， ZHENG Z M. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems [J]. SCIENTIA SINICA Informationis， 2012， 42（9）： 1170-1180.）

[20]ZHAO C， ZHANG P， ZHENG Z， et al. Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2012， 85（1 Pt 2）： 016106.

[21]原志強(qiáng)，趙春艷.兩種改進(jìn)的模擬退火算法求解大值域約束足問題[J].計(jì)算機(jī)應(yīng)用研究，2017，34（12）：3611-3616.（YUAN Z Q， ZHAO C Y. Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains [J]. Application Research of Computers， 2017， 34（12）： 3611-3616.）

[22]吳撥榮，趙春艷，原志強(qiáng).置信傳播和模擬退火相結(jié)合求解約束滿足問題[J].計(jì)算機(jī)應(yīng)用研究，2019，36（5）：1297-1301.（WU B R， ZHAO C Y， YUAN Z Q. Combining belief propagation and simulated annealing to solve random satisfaction problems [J]. Application Research of Computers， 2019， 36（5）： 1297-1301.）

[23]CAI S， SU K L， SATTAR A， et al. Local search with edge weighting and configuration checking heuristics for minimum vertex cover [J]. Artificial Intelligence， 2011， 175（9/10）： 1672-1696.

This work is partially supported by the National Natural Science Foundation of China （11301339）， the National Natural Science Foundation of China — International （Regional） Cooperation and Exchange Program （11491240108）.

LI Feilong， born in 1994， M. S. candidate， His research interests include computational theory and computational complexity.

ZHAO Chunyan， born in 1982， Ph. D.， lecturer. Her research interests include non-deterministic polynomial-complete problem， computational theory and computational complexity.

FAN Rumeng， born in 1995， M. S. candidate. Her research interests include computational theory and computational complexity.

收稿日期：2019-05-16;修回日期：2019-07-08;錄用日期：2019-07-17。

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（11301339）;國(guó)家自然科學(xué)基金國(guó)際 （地區(qū)）合作與交流項(xiàng)目（11491240108）。

作者簡(jiǎn)介：李飛龍（1994—），男，安徽阜陽(yáng)人，碩士研究生，主要研究方向：計(jì)算理論與計(jì)算復(fù)雜性; 趙春艷（1982—），女，河南焦作人，講師，博士，主要研究方向：NP-完全問題、計(jì)算理論與計(jì)算復(fù)雜性; 范如夢(mèng)（1995—），女，河南駐馬店人，碩士研究生，主要研究方向：計(jì)算理論與計(jì)算復(fù)雜性。

文章編號(hào)：1001-9081（2019）12-3584-06 DOI：10.11772/j.issn.1001-9081.2019050834