基于CSP 方法的經(jīng)濟(jì)學(xué)實驗分組問題的設(shè)計與實現(xiàn)

陳丹琳

（牛津大學(xué)納菲爾德學(xué)院社會科學(xué)實驗中心中國分部，天津 300071）

經(jīng)濟(jì)學(xué)的許多實驗中都會涉及排列組合的分組問題，比如獨裁者博弈[1]、公共物品實驗[2]以及眾多經(jīng)典的博弈類實驗.在這些實驗中，設(shè)計者需要將參與者按照一定數(shù)量進(jìn)行分組，在每輪中會多組同時實驗，并進(jìn)行多輪[3]，一些實驗還要求幾個參與者被分入同一組的情況只出現(xiàn)一次.

oTree 框架是進(jìn)行實驗編寫的常用工具，它是使用Python 編寫的行為研究開源平臺框架[4].使用oTree框架編寫實驗時，大部分會使用group_randomly 函數(shù)將參與者進(jìn)行隨機(jī)分組，對于N 個參與者P1，P2，…，PN，此函數(shù)調(diào)用Constants 類中的play_per_group 變量，即每組人數(shù)G，然后將參與者隨機(jī)排序后進(jìn)行分組，最終返回一個（N/G）× G 的矩陣作為分組結(jié)果. 此函數(shù)每次只能完成一輪分組，如果需要進(jìn)行多輪實驗，則需要重新調(diào)用此函數(shù).根據(jù)group_randomly 的運行機(jī)制，幾個參與者被分入同一組的情況可能會出現(xiàn)多次，而在某些實驗中，這是不允許的. 如，將參與者P1、P2、P3、P4兩兩組合，進(jìn)行 2 輪，設(shè)在第 1 輪使用group_randomly 函數(shù)后，分組情況為[[P1，P2]，[P3，P4]]，根據(jù)實驗要求，相同2 個參與者再次分入一組的概率應(yīng)為零，但是在第2 輪調(diào)用group_randomly 函數(shù)進(jìn)行分組時，P1、P2分入一組的概率為1/16. 因此利用group_randomly 函數(shù)分組不能滿足幾個參與者分在一組只出現(xiàn)一次的要求.為解決這一問題，本研究基于約束滿足類型問題（Constraint satisfaction problem，CSP）的分析方法[5]對此類分組實驗進(jìn)行分析規(guī)制，將分組形式拆解，對任意輪次的任意組中的每個空位構(gòu)造相對應(yīng)的值域（可填入此位置的參與者范圍）以及限制條件，然后使用回溯算法[6]解決問題.

1 CSP 和回溯算法模型

1.1 CSP

CSP 廣泛應(yīng)用于運籌學(xué)和人工智能等領(lǐng)域[7]，它通常需要將狀態(tài)進(jìn)行要素化描述，即對每個變量設(shè)定相應(yīng)的值域，當(dāng)所有變量都被賦值，且其值同時滿足所有約束條件時，問題便得以解決.CSP 通常表現(xiàn)出較高的時間復(fù)雜度，因此需要結(jié)合啟發(fā)式搜索和聯(lián)合搜索等方法進(jìn)行優(yōu)化.經(jīng)典的CSP 問題有八皇后問題[8]、地圖著色問題、 數(shù)獨問題等，這些問題可以分為二元問題和多元問題，本研究解決的為多元問題.

CSP 主要由 3 個集合組成：V={V1，V2，…，Vm}為變量集，包含所有需要被賦值的變量；D={D1，D2，…，Dn}為值域集，包含每個變量所對應(yīng)的值域； C = {C1，C2，…，Cp}為限制條件集，包含每個變量的賦值需要同時滿足的所有限制條件.基于這3 個集合，可以定義CSP 問題的狀態(tài)空間和問題的解.

1.2 回溯算法

回溯算法是一種十分常用的基本優(yōu)化搜索方法，通常用于解決CSP 問題[9]. 回溯算法是暴力枚舉的一種改進(jìn)，通過使用CSP 中的約束條件減少無用的枚舉步驟.

回溯算法的基本思想為：首先對第1 個變量賦值x1，使其滿足所有限制條件，然后對第2 個變量從剩下的可能解中選擇一個滿足所有限制條件的值x2，直到所有變量都已賦值，最終形成完整的解；在賦值過程中，設(shè)前 k 個變量依次賦值為 x1，x2，…，xk，如果第k +1 個變量找不到滿足所有限制條件的值，則進(jìn)行回溯，將第 k 個變量的值 xk刪除，回溯到 x1，x2，…，xk-1的狀態(tài)，并對第k 個變量重新賦值，再判斷第k+1個變量是否存在滿足條件的值.回溯算法流程類似于遞歸樹，通常使用深度優(yōu)先搜索（Deep first search，DFS）的方法實現(xiàn).

2 算法分析

設(shè)有 N 個參與者 P1，P2，…，PN，每 G 個分為一組.分組完成后，得到k=N/G 個組，將這樣的分組重復(fù)A 輪，總計得到A·k 個組，在這A·k 個組中，要求相同G 個參與者分入同一組（不論以何種順序排列）的情況只能出現(xiàn)一次.為方便，在下面的算法分析和代碼實現(xiàn)中設(shè) N=20，G=2，A=10.

2.1 CSP 分析

（1）變量集V.變量集V 為一個10×10×2 的矩陣，

其中：Vi，j，k表示第 i 輪中第 j 個組的第 k 個參與者，1≤i≤10，1≤j≤10，k=1、2.

（2）值域集D.值域集D 中的量應(yīng)與變量集V 中的變量一一對應(yīng)，因此D 為一個10×10×2×20 的矩陣，

其中：若參與者Pl在第i 輪中被分入第j 個組的第k個位置，則 Di，j，k，l=1，否則 Di，j，k，l=0，1≤i≤10，1≤j≤10，k=1、2，1≤l≤20.

（3）限制條件集C.限制條件集C 為一個20×20的矩陣，

其中 Ci，j的值為分組過程中[Pi，Pj]出現(xiàn)的次數(shù). 參與者Pi、Pj組合的順序會影響 Ci，j和 Cj，i的賦值.

2.2 回溯算法代碼實現(xiàn)

定義{V，D，C}后，使用回溯算法解決 CSP 問題.在問題求解過程中，每一步只討論一個變量的賦值，即每一步只在值域集D 中根據(jù)限制條件集C 尋找某個 Vi，j，k的賦值.當(dāng) V 中所有變量都已被賦值，則問題解決.變量集 V 中所有 Vi，j，k的初始賦值為-1，當(dāng)?shù)?i行的所有 Vi，j，k都已被賦除-1 以外的值時，則代表第 i輪分組完成.值域集 D 中所有 Di，j，k，l的初始賦值為 0.限制條件集 C 中所有 Ci，j的初始賦值為 0，且 Ci，j=0或1.

算法程序使用 Python 語言進(jìn)行編譯，使用Numpy 庫存儲多維數(shù)據(jù)集{V，D，C}.回溯算法中主要使用了 5 個函數(shù)：recursive_wrap，recursive，select_unsigned_var，order_domain_value 和 value_consistent.回溯算法流程圖如圖1 所示.

（1）recursive_wrap 函數(shù). 此函數(shù)主要用于對recursive 函數(shù)進(jìn)行包裝，并返回一個長度為2 的表.表中第 1 個元素為 boolean 變量，其值為 True 或False，若為True，則表明分組問題存在完整的合法解，若為False，則表明不存在合法解.當(dāng)?shù)? 個元素值為True 時，則第2 個元素為完全賦值的數(shù)據(jù)集V，當(dāng)?shù)? 個元素值為False 時，則第2 個元素為未完全賦值的數(shù)據(jù)集V.其偽代碼如下：

圖1 回溯算法流程Fig.1 Process of backtracking algorithm

（2）recursive 函數(shù). 此函數(shù)的返回內(nèi)容與函數(shù)recursive_wrap 相同.recursive 函數(shù)的詳細(xì)步驟為：

①檢查V 中是否存在未賦值的組.若V 中所有的變量都已經(jīng)被賦值，則recursive 函數(shù)返回[True，V]；若V 中還有未被賦值的組，則使用select_unsigned_var 函數(shù)得到集合[i，j，k]，選定 Vi，j，k進(jìn)行賦值.

②運行 order_domain_values 函數(shù)，帶入 Vi，j，k，得到可被放入 Vi，j，k的值域集合[a，…，b]，這個集合表示參與者[Pa，…，Pb]在第 i 輪中未被分組，關(guān)于[a，…，b]的排列順序，請見后文.

③在循環(huán)過程中，根據(jù)[a，…，b]將 Pa，…，Pb依次賦值到 Vi，j，k，使用 value_consistent 函數(shù)，根據(jù)限制集C 判斷 Px是否為 Vi，j，k的合理賦值.如果 Px不能滿足限制集 C 對 Vi，j，k的限制條件，則 value_consistent 會返回-1，即 if_consistent 等于-1，此時在 Pa，…，Pb中重新尋找 Vi，j，k的賦值； 如果 Pa，…，Pb中不存在 Vi，j，k的合法賦值，則recursive 函數(shù)返回False.

④如果value_consistent 返回的結(jié)果不是-1，則更新{V，D，C}，然后定義變量 result，將更新后的{V，D，C}代入resursive 函數(shù)進(jìn)行賦值，其結(jié)果賦給result.如果 result 的第 1 個元素為 False，則將{V，D，C}的更新撤銷，并返回步驟③.

recursive 函數(shù)的偽代碼如下：

Def recursive（{V，D，C}）：

If ?Vi，j，k∈V，Vi，j，k≠-1 do：

return[True，V]

end if

Vi，j，k=select_unsigned_var（V）

[a，…，b]=order_domain_values（Vi，j，k，{D，C}）

For ?x，x ∈[a，…，b]do：

if_consistent=value_consistent（Vi，j，k，Px，{V，D，C}）

if if_consistent≠-1，即 Px是 Vi，j，k的合理解：Vi，j，k=Px

更新值域集D

if if_consistent==2 do：

更新限制集C

end if

result=recursive（{V，D，C}）

if result 的第1 個元素不是False，

return result

end if

else：

Vi，j，k=-1

取消值域集的更新

if if_consistent==2：

撤銷限制集C 的更新

end if

end for

return[False，V]

（3）select_unsigned_var 函數(shù).此函數(shù)用于尋找數(shù)據(jù)集 V 中還未被賦值的變量 Vi，j，k，函數(shù)返回一個長度為 3 的數(shù)據(jù)集[i，j，k]，表示 Vi，j，k還未被賦值. select_unsigned_var 函數(shù)的偽代碼如下：

Def select_unsigned_var（V）：

for i= 第 1 輪到第 10 輪 do：

for j= 第 1 組到第 10 組 do：

for k=Vi，j，1，Vi，j，2：

if Vi，j，k==-1：

return[i，j，k]

end if

end for

end for

end for

return-1

（4）order_domain_values 函數(shù).此函數(shù)根據(jù)select_unsigned_var 函數(shù)中得到的[i，j，k]，在 D 中尋找第 i輪中還未出現(xiàn)過的所有參與者，即返回D 的第i 行j 列第 k 個集合里所有等于 0 的 Di，j，k，l.若此輪所有參與者已經(jīng)都完成分組，函數(shù)則返回一個空的表. order_domain_values 函數(shù)的偽代碼如下：

def order_domain_values（[i，j，k]，D，C）：

player_list=[]

for j=Di，j，k，1，…，Di，j，k，20do：

if Di，j，k，l=0：

player_list.append（l）

end if

end for

根據(jù)限制集C，將player_list 中的l 按限制條件由多到少排列.

return player_list

這里使用了最小剩余值（Minimum-remaining-values，MRV）技巧，以改變player_list 中元素的排列順序，從而對合法值的選擇進(jìn)行優(yōu)化. 集合[a，…，b]表示參與者[Pa，…，Pb]在第 i 輪中未被分組，通過檢查限制集C，可得[Pa，…，Pb]中的 Px還能與多少參與者進(jìn)行組合，可與Px組合的參與者越多則受到的限制越少.因此將[a，…，b]按照限制由多至少的順序進(jìn)行排列可提高賦值的成功率，從而降低程序的時間復(fù)雜度.

（5）value_consistent 函數(shù). 此函數(shù)用于判斷 Px是否為 Vi，j，k的合法賦值，如果是，則返回 1 或 2，如果不是，則返回-1.value_consistent 函數(shù)的偽代碼如下：

def value_consistent（{V，D，C}，[i，j，k]，Px）：

if 與 Vi，j，k同組的成員還未確定：

return 1

else：

match= 與 Vi，j，k同組的參與者為 Px

if y≠x 且 Cx，y+Cy，x==0：

return 2

end if

end if

return-1

3 仿真實驗

使用Python 分別編寫了關(guān)于分組問題回溯算法的程序和包含MRV 技巧的程序，在CPU 為1.6 GHz Intel Core i5、 操作系統(tǒng)為macOS Sierra10.12.6 的 Mac air 計算機(jī)上運行. 設(shè)定參與者 N = 16、18、20、22，每組人數(shù)G = 2，共進(jìn)行10 輪分組，利用程序進(jìn)行測試，程序運行時間見表1，以N=20 為例，10 輪的分組結(jié)果見表2.由表1 和表2 可知，本文基于CSP 的分組問題的回溯算法是有效的，且利用MRV 優(yōu)化的回溯算法可有效降低算法的時間復(fù)雜度.

表1 仿真實驗運行時間Tab.1 Run time of simulation experiments

表2 N=20 的分組結(jié)果Tab.2 Grouped results when N=20

4 結(jié)語

將經(jīng)濟(jì)學(xué)經(jīng)典實驗中分組問題歸類為CSP，并將問題拆解成變量集、 值域集以及約束條件集的形式，并使用回溯算法實現(xiàn)分組. 本文算法有效彌補了oTree 中g(shù)roup_randomly 函數(shù)無法確保相同參與者分在一組的情況只出現(xiàn)一次的缺點.回溯算法的時間復(fù)雜度以及空間復(fù)雜度并不適用于參與者人數(shù)過大的實驗，在下一步的工作中將嘗試設(shè)計能夠大幅降低復(fù)雜度的算法.