一種基于分布式約束滿(mǎn)足的資源優(yōu)化模型

（華中科技大學(xué) 電子與信息工程系， 武漢 430074）



摘 要：分布式約束滿(mǎn)足作為分布式人工智能領(lǐng)域的一個(gè)重要分支，在許多領(lǐng)域均得到了廣泛應(yīng)用。針對(duì)Web服務(wù)事務(wù)協(xié)調(diào)過(guò)程中的資源優(yōu)化問(wèn)題，在分布式逃逸算法的基礎(chǔ)上提出了一種基于分布式約束滿(mǎn)足的資源優(yōu)化模型，并通過(guò)仿真實(shí)驗(yàn)證實(shí)了模型及其算法的收斂性和優(yōu)化性。

關(guān)鍵詞：分布式約束滿(mǎn)足;分布式逃逸算法;資源優(yōu)化

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)03086403



Resource allocation optimization model based on DCSP



XIAO Yu， XU Wei， CHENG Wenqing



（Dept. of Electronics Information， Huazhong University of Science Technology， Wuhan 430074， China）



Abstract:As one of the most important branches of DAI， the distributed constraint satisfaction is in wide application. This paper proposed a DCSPbased resource allocation optimize model in order to satisfy the same requirement of the Web service transaction coordination. Finally， the astringency and optimization of the new model and its algorithm are proved through a simulation.

Key words：distributed constraint satisfaction; distributed breakout algorithm; resource allocation optimization



0 引言

自從1974年Montanari在圖像處理中首先提出了約束滿(mǎn)足問(wèn)題（constraint satisfaction problems，CSPs）[1]以來(lái)，約束滿(mǎn)足作為一種重要的求解方法在人工智能與計(jì)算機(jī)科學(xué)其他領(lǐng)域中得到了廣泛的應(yīng)用[2]，從n皇后、圖染色等經(jīng)典問(wèn)題到時(shí)序安排、計(jì)劃編制、資源分配等大型應(yīng)用問(wèn)題，均可以形式化為約束滿(mǎn)足問(wèn)題進(jìn)行求解。此后，Yokoo等人[3]又在原有工作的基礎(chǔ)上提出了分布式約束滿(mǎn)足問(wèn)題的解決框架，以agent作為計(jì)算實(shí)體，通過(guò)各個(gè)agent之間的協(xié)調(diào)來(lái)尋找滿(mǎn)足所有分布式約束的解。其核心算法包括異步回溯（asynchronous backtracking，ABT）、異步弱承諾搜索（asynchronous weakcommitment search，AWS）[4]和分布式逃逸[5]。這些算法構(gòu)成了分布式約束滿(mǎn)足問(wèn)題求解體系的基礎(chǔ)。

雖然約束滿(mǎn)足模型一般被用來(lái)尋找可行解的問(wèn)題，但是如果能夠?qū)s束評(píng)估函數(shù)以及迭代算法加以改進(jìn)，則可以利用約束滿(mǎn)足模型來(lái)求解優(yōu)化問(wèn)題，尤其是分布式優(yōu)化問(wèn)題。在之前的研究[6]中，筆者發(fā)現(xiàn)Web服務(wù)事務(wù)協(xié)調(diào)過(guò)程中包含了一個(gè)資源預(yù)分配環(huán)節(jié)，如果能夠在這一環(huán)節(jié)中實(shí)現(xiàn)分布式資源的最優(yōu)分配，將會(huì)對(duì)事務(wù)協(xié)調(diào)的總體效果起到非常積極的作用。因此，本文提出了一種基于分布式約束滿(mǎn)足的資源優(yōu)化模型來(lái)解決Web服務(wù)事務(wù)協(xié)調(diào)過(guò)程中的資源優(yōu)化預(yù)分配問(wèn)題；同時(shí)，這種通用模型也可以在分布式資源優(yōu)化領(lǐng)域得到廣泛應(yīng)用。

1 分布式約束滿(mǎn)足問(wèn)題

分布式約束滿(mǎn)足問(wèn)題是變量和約束均分布在不同自治agent中的約束滿(mǎn)足問(wèn)題。與一般約束滿(mǎn)足問(wèn)題相比，它最顯著的特征是每個(gè)自治agent僅依據(jù)局部的約束關(guān)系來(lái)確定自身變量的取值，其形式化定義如下：

定義1 分布式約束滿(mǎn)足問(wèn)題。n個(gè)agent表示為A1， A2， …， An，m個(gè)變量為v1， v2， …， vm，m個(gè)變量的值域?yàn)镈1， D2， …， Dm，變量間的約束仍用C表示；每個(gè)agent有一個(gè)或多個(gè)變量，每個(gè)變量vj屬于一個(gè)Ai，表示為belongs(vj， Ai)；變量間的約束關(guān)系分布在agent內(nèi)或agent之間，當(dāng)Al知道約束關(guān)系Ck時(shí)，表示為known(Ck， Al)。

定義2 分布式約束滿(mǎn)足問(wèn)題的解。當(dāng)且僅當(dāng)滿(mǎn)足下述條件時(shí)，分布式約束滿(mǎn)足問(wèn)題找到了解：Ai，vj存在關(guān)系belongs(vj，Ai)，當(dāng)vj的賦值是dj∈Dj時(shí)，Ck、Ai、known(Ck，Ai)均有Ck被滿(mǎn)足，也即此時(shí)對(duì)問(wèn)題中所有變量的賦值滿(mǎn)足agent間及agent內(nèi)的所有約束。

可以用上述分布式約束滿(mǎn)足問(wèn)題的形式化描述方法具體定義一個(gè)簡(jiǎn)單的分布式圖形著色問(wèn)題（distributed graphcoloring problem）。如圖1所示，對(duì)于任意一個(gè)agent xi，與它有直接關(guān)聯(lián)的agent集合稱(chēng)為xi的鄰居（neighbors），xi的值域?yàn)閧black， white}，約束關(guān)系是任意一個(gè)agent xi都必須與它的鄰居取不同的值。以x1為例，known(Ck，x1)={x1≠x2， x1≠x6}，那么如果x1取值為white，x2和x6的取值就必須為black。由于所有的約束關(guān)系known(Ck，xi)被分散到每個(gè)獨(dú)立的agent xi中，因此問(wèn)題的求解與一般約束滿(mǎn)足問(wèn)題的求解有較大差異。

分布式約束滿(mǎn)足問(wèn)題的求解算法主要有三種，即異步回溯算法、異步弱承諾搜索算法和分布式逃逸算法。異步回溯算法的核心思想源于回溯算法，所不同的是它能夠適應(yīng)分布式、異步的執(zhí)行環(huán)境。算法中的agent具有明確的優(yōu)先次序，高優(yōu)先序的agent通過(guò)ok?消息將自己的取值告知低優(yōu)先次序的agent。如果低優(yōu)先次序agent的值域中沒(méi)有能與高優(yōu)先序agent的賦值相一致的值，就產(chǎn)生一個(gè)新的約束關(guān)系（也就是nogood消息）；同時(shí)將nogood消息傳遞給高優(yōu)先序agent，形成一次回溯。為了解決異步回溯算法固有的優(yōu)先次序問(wèn)題，異步弱承諾搜索算法引入了最小沖突啟發(fā)策略來(lái)減少不利賦值的風(fēng)險(xiǎn)；同時(shí)動(dòng)態(tài)調(diào)整agent的優(yōu)先級(jí)順序，讓不利賦值無(wú)須窮盡搜索就能夠得到更正。與前面兩種算法不同，分布式逃逸算法是一種局部搜索算法，它是集中條件下逃逸算法針對(duì)分布式環(huán)境的改進(jìn)。在分布式逃逸算法中，相鄰的agent之間通過(guò)兩種消息的通信：ok?和improve？來(lái)交換取值信息和改進(jìn)評(píng)估值的能力，只有能夠最大提高評(píng)估值的agent才有權(quán)改變自己的值，如果都不能提高評(píng)估值，則違反的約束權(quán)值需要累加以跳出局部最小。

2 優(yōu)化問(wèn)題的約束模型

與經(jīng)典染色問(wèn)題不同，本文提出的資源優(yōu)化模型將每個(gè)事務(wù)看成一個(gè)獨(dú)立的agent，每個(gè)agent的值域?yàn)閧0， 1}。其中：0代表事務(wù)資源預(yù)定失敗；1代表預(yù)定成功。每個(gè)事務(wù)通常由多個(gè)資源請(qǐng)求組成。為了滿(mǎn)足事務(wù)原子性的要求，這些資源請(qǐng)求要么同時(shí)被滿(mǎn)足，要么同時(shí)被拒絕。

資源優(yōu)化模型的另外一項(xiàng)重要內(nèi)容是對(duì)約束關(guān)系進(jìn)行建模。DB算法求解染色問(wèn)題時(shí)，惟一的約束條件是相鄰實(shí)體的染色不能相同。然而在資源優(yōu)化問(wèn)題中，約束的設(shè)定需要考慮更多因素，即應(yīng)該同時(shí)包含資源請(qǐng)求超額和資源利用不足兩方面的約束內(nèi)容（具體參見(jiàn)定義3）。

定義3 分布式資源優(yōu)化問(wèn)題。n個(gè)事務(wù)Ti，i∈{1，…， n}分別用對(duì)應(yīng)的agent來(lái)表示：A1， A2，…，An。其中每個(gè)agent控制惟一的一個(gè)變量vi， i∈{1，…，n}。vi的值域分別為D1，D2，…，Dn。其中Di={0，1}，1表示事務(wù)成功；0表示事務(wù)失敗。每個(gè)agent包含對(duì)多個(gè)服務(wù)資源的請(qǐng)求r1，r2，…，rm。該請(qǐng)求資源的集合可以用R(Ai)來(lái)表示。如果R(Ai)∩R(Aj)≠，則說(shuō)明Ai與Aj之間存在著競(jìng)爭(zhēng)關(guān)聯(lián)compete (Ai，Aj)。事務(wù)僅與資源存在約束關(guān)系。事務(wù)Ai與資源rj的約束可以用Cij表示每個(gè)Ai僅知道自己的約束關(guān)系known(Cij，Ai)，Cij， rj∈R(Ai)的具體計(jì)算模型如下（其中當(dāng)前請(qǐng)求數(shù)量和資源可用數(shù)量分別用volume(rj)和rj.max表示)：

當(dāng)vi=1且volume(rj)＞rj.max時(shí)，Cij=1；

當(dāng)vi=1且volume(rj)≤rj.max時(shí)，Cij=-1；

當(dāng)vi=0且volume(rj)＜rj.max時(shí)，Cij=1；

當(dāng)vi=0且volume(rj)≥rj.max時(shí)，Cij=-1。

定義4 分布式資源優(yōu)化問(wèn)題的解。當(dāng)且僅當(dāng)滿(mǎn)足下述條件時(shí)，Web服務(wù)事務(wù)協(xié)調(diào)過(guò)程中的資源預(yù)優(yōu)化問(wèn)題找到了解：Ai，當(dāng)vi的賦值滿(mǎn)足di∈Di時(shí)，Ck∈Ai，均有Ck≤0（Ck是由known(Cij，Ai)中所有事務(wù)Ai與資源rj的約束Cij組成的評(píng)估函數(shù))。

上述定義中，關(guān)鍵的內(nèi)容是約束關(guān)系Cij的計(jì)算模型。由于需要同時(shí)考慮資源請(qǐng)求超額和資源利用不足兩方面的約束條件，不能通過(guò)簡(jiǎn)單的違反約束或不違反約束來(lái)影響變量vi的取值。因此，本文提出了一種新型的雙向約束，它包含正面影響和負(fù)面影響兩種類(lèi)型。當(dāng)資源rj∈R(Ai)時(shí)，如果該資源預(yù)定請(qǐng)求超額，而事務(wù)取值為1，說(shuō)明該事務(wù)是當(dāng)前超額情況的貢獻(xiàn)者之一，因此具有負(fù)面影響；相反，當(dāng)資源預(yù)定請(qǐng)求不足，而事務(wù)取值為0時(shí)，則說(shuō)明事務(wù)也是當(dāng)前資源利用不足情況的貢獻(xiàn)者之一，也具有負(fù)面影響；其他兩種情況依此類(lèi)推。最后，每個(gè)事務(wù)根據(jù)所有的約束來(lái)計(jì)算評(píng)估函數(shù)Ck。如果Ck≤0，則說(shuō)明目前事務(wù)的取值在兼顧資源請(qǐng)求超額和資源利用最大化方面是較優(yōu)的。

3 資源優(yōu)化算法

針對(duì)上述優(yōu)化模型，本文對(duì)DB算法進(jìn)行了改進(jìn)。之所以選用DB算法，是因?yàn)樗且环N局部搜索算法，在執(zhí)行的任何階段均可以獲得逐步優(yōu)化的過(guò)程解，雖然這些解有時(shí)可能陷入局部最優(yōu)，但是求解效率是相當(dāng)顯著的[7]。下面為改進(jìn)后的DB算法（即本文提出的分布式資源優(yōu)化算法）的偽代碼描述。

1）分布式資源優(yōu)化算法（wait_ok模式）偽代碼

wait_ok？模式;

when received(ok， (xj， dj)) do

counter++;//搜集所有相鄰事務(wù)的取值信息后才進(jìn)行評(píng)估

add (xj， dj) to agent_view;

if counter = number_of_neighbors then

send_improve; counter=0; //計(jì)數(shù)器清零，等待下一輪ok消息

end if; end do;

procedure send_improve

eval = evaluate(current_value); 

//根據(jù)約束模型計(jì)算當(dāng)前的評(píng)估值

if eval <=0 then consistent = true;

else consistent = 1;

my_tc = 0; //出現(xiàn)不一致情況，終止計(jì)數(shù)器清零

end if

another = evaluate(1-current_value);//計(jì)算另一取的評(píng)估值

if eval > another then

my_improve = evalanother; //評(píng)估函數(shù)改進(jìn)值

can_move = true; 

//能不能變化還要看等收到improve消息才能定

quasi_local_minimum = 1; new_value = 1value;

else

my_improve = 0; can_move = 1;

quasi_local_minimum = true; //無(wú)法改進(jìn)所以是準(zhǔn)局部最小

end if

send(improve， xi， my_improve， eval， my_tc) to all the neighbors;

end procedure

2)分布式資源優(yōu)化算法（wait_inprove模式）偽代碼

wait_improve？模式;

when received(improve， xj， improve， eval， tc) do

counter++;//搜集所有相鄰事務(wù)的評(píng)估信息后才做決定

my_tc = min(tc， my_tc);

if improve ＞ my_improve then //相鄰事務(wù)改進(jìn)效果更好 

can_move = 1; quasi_local_minimum = 1;

else if improve = my_improve and ID ＜ my_ID then

can_move = 1; end if;//改進(jìn)能力相同，但對(duì)方次序靠前

if eval ＞ 0 then

consistent = 1; end if;

if counter = number_of_neighbors then

send_ok; counter=0; //計(jì)數(shù)器清零，等待下一輪improve消息

end if;

end do;

procedure send_ok

if consistent = true then my_tc ++; 

if my_tc = max_distance then 

//連續(xù)幾輪收到一致消息，全體一致

find a solution， terminate the algorithm; end if; end if;

if consistent = 1 and quasi_local_minimum = true then 

Increase the weights of constraint equals 1; end if;

if can_move = true then //如果自己改進(jìn)最大，則取新值

current_value = new_value; end if;

send(ok， (xi，current_value)) to all the neighbors;

end procedure

下面將利用一個(gè)簡(jiǎn)化的示例來(lái)具體描述上述分布式資源優(yōu)化算法的執(zhí)行過(guò)程。假設(shè)五個(gè)事務(wù)的組成是A1{r1， r2}， A2{ r1， r3，r4}， A3{ r2， r3， r4}， A4{ r1， r4，r5}， A5{ r3}，而對(duì)應(yīng)的五種資源的容量為S1(2)， S2(2)， S3(2)， S4(2)， S5(1)，且每個(gè)事務(wù)agent隨機(jī)選定的初始值為v1(1)， v2(1)， v3(0)， v4(0)， v5(1)。通過(guò)第一輪ok?消息的交互，每個(gè)事務(wù)了解了相鄰事務(wù)的取值，然后對(duì)約束情況進(jìn)行評(píng)估。其中只有A3和A4約束函數(shù)大于0并且能夠改進(jìn)（增加資源利用）。由于A3次序靠前，第一輪improve?交互后，A3的取值發(fā)生改變v3(0)→v3(1)。第二輪ok?消息的交互后，只有A5約束函數(shù)大于0并且能夠改進(jìn)（資源超額），因此第二輪improve?交互后，A5的取值發(fā)生改變v5(1)→v5(0)。第三輪雖然有資源r5仍然沒(méi)有被預(yù)定，但是所有的約束函數(shù)并沒(méi)有大于0的情況出現(xiàn)，因此情況延續(xù)到第四輪。此時(shí)筆者注意到，由于連續(xù)兩次處于準(zhǔn)局部最小狀態(tài)，A4與r5的約束C45權(quán)值已經(jīng)增大為3，A4的約束函數(shù)變成1，而且能夠改進(jìn)，于是本輪循環(huán)后，A4的取值發(fā)生改變v4(0)→v4(1)。之后，A2與之前A5的情況一樣，由于引起資源超額而必須更改取值v2(1)→v2(0)，而A5卻因?yàn)锳2的取值變化，又重新具有改進(jìn)能力，從而完成系統(tǒng)最后一個(gè)取值變更v5(0)→v5(1)。此后，系統(tǒng)連續(xù)數(shù)個(gè)周期維持全部一致的狀態(tài)不變，表明解v1(1)， v2(0)， v3(1)， v4(1)， v5(1)是全局一致的解，同時(shí)也會(huì)注意到系統(tǒng)所有的資源被最大化地分配，從而證實(shí)了改進(jìn)后的DB算法是一種非常有效的分布式優(yōu)化算法。

4 仿真與結(jié)果

本文設(shè)計(jì)了一個(gè)Web服務(wù)事務(wù)協(xié)調(diào)仿真實(shí)驗(yàn)平臺(tái)來(lái)對(duì)分布式資源優(yōu)化模型進(jìn)行系統(tǒng)的仿真分析。平臺(tái)設(shè)計(jì)了一個(gè)100項(xiàng)事務(wù)的問(wèn)題規(guī)模，每個(gè)事務(wù)的長(zhǎng)度服從均值為3的正態(tài)分布，并將事務(wù)長(zhǎng)度限制在[1，5]整數(shù)區(qū)間內(nèi)。事務(wù)的資源請(qǐng)求是隨機(jī)構(gòu)成的，事務(wù)對(duì)資源的總體請(qǐng)求服從均勻分布（表1），資源的需求總數(shù)為308。

表1 事務(wù)對(duì)不同資源的請(qǐng)求數(shù)量列表

資源名稱(chēng)R1R2R3R4R5R6R7R8R9R10

資源請(qǐng)求數(shù)20151118131514151612

資源名稱(chēng)R11R12R13R14R15R16R17R18R19R20

資源請(qǐng)求數(shù)17171319121214151723

為了簡(jiǎn)化仿真的復(fù)雜度，本文假設(shè)每種資源擁有相同的資源容量，分別隨機(jī)選取資源容量為12和15兩種情況來(lái)進(jìn)行算法的收斂性分析。顯然，當(dāng)資源容量volume=12時(shí)，事務(wù)競(jìng)爭(zhēng)比較激烈；而當(dāng)資源容量volume=15時(shí)，事務(wù)的競(jìng)爭(zhēng)趨于緩和。仿真分析關(guān)注的內(nèi)容主要包括三個(gè)方面：a)本章提出的約束評(píng)估模型是否能夠讓DB算法收斂；b)不同的初值設(shè)定是否影響DB算法的收斂過(guò)程，如果不影響，其收斂過(guò)程如何？c)算法的收斂結(jié)果的優(yōu)化程度如何？通過(guò)仿真結(jié)果（圖2），本文證實(shí)了上述三個(gè)方面的內(nèi)容：第一，本章提出的約束評(píng)估模型能夠讓DB算法收斂，兩種資源容量下，分別從不同的初值開(kāi)始迭代，算法最終均能達(dá)到持續(xù)穩(wěn)定的解。第二，不同的初值設(shè)定對(duì)DB算法取得的最終解影響很小，收斂的過(guò)程也是穩(wěn)定的，收斂的速度與最優(yōu)解中成功事務(wù)的數(shù)量有關(guān)，如果成功率較高，則以全1為事務(wù)初值可以在非常短的時(shí)間內(nèi)達(dá)到收斂結(jié)果；反之，則達(dá)到收斂結(jié)果的時(shí)間較長(zhǎng)。第三，模型收斂的結(jié)果與用MATLAB環(huán)境中“01”規(guī)劃方法計(jì)算的結(jié)果非常接近，從而全面證實(shí)了本文提出的分布式資源優(yōu)化模型的有效性。

5 結(jié)束語(yǔ)

本文在分布式逃逸算法的基礎(chǔ)上，提出了一種基于約束滿(mǎn)足的資源優(yōu)化模型。通過(guò)設(shè)計(jì)新型的約束評(píng)估函數(shù)及其迭代算法，本文將只能求解可行解的約束滿(mǎn)足問(wèn)題轉(zhuǎn)換為求解最優(yōu)解的資源優(yōu)化問(wèn)題。并通過(guò)仿真實(shí)驗(yàn)，證實(shí)了模型求解的收斂性和優(yōu)化性。下一步筆者將在此研究的基礎(chǔ)上研究分布式資源優(yōu)化的連續(xù)求解問(wèn)題，從而使求解模型能夠適應(yīng)外界環(huán)境的不斷變化。

參考文獻(xiàn)：

［1］MONTANARI U. Networks of constraints: fundamental properties and applications to picture processing[J]. Information Sciences， 1974，7(2):95132.

[2]KUMAR V. Algorithms for constraint satisfaction problems: a survey[J]. AI Magazine， 1992，13(1):3244.

[3]YOKOO M， DURFEE E H， ISHIDA T， et al. Distributed constraint satisfaction for formalizing distributed problem solving[C]//Proc of the 12th Int’l Conf on Distributed Computing Systems. Los Alamitos: IEEE Computer Society Press， 1992:614621.

[4]YOKOO M. Asynchronous weakcommitment search for solving distributed constraint satisfaction problems[C]//MONTANARI U， ROSSI F. Proc of the 1st Int’l Conf on Principles and Practice of Constraint Programming. Berlin: SpringerVerlag， 1995:88102.

[5]YOKOO M， HIRAYAMA K. Distributed breakout algorithm for solving distributed constraint satisfaction problems[C]//WEIβ G. Proc of the 2nd Int’l Conf on Multiagent Systems. Cambridge: MIT Press， 1996：401408.

[6]XU Wei， YANG Zongkai， LIU Wei，et al. taTHP: a transactionaware protocol for Web services transaction coordination[C]//Proc of TENCON 2006.[S.l.]:IEEE Press， 2006.

[7]王秦輝，陳恩紅，王煦法.分布式約束滿(mǎn)足問(wèn)題研究及其進(jìn)展[J].軟件學(xué)報(bào)， 2006，17(10):20292039.