求解最小雙連通支配集問題的變鄰域禁忌搜索算法

［摘 要］ 針對經典NP難優化問題——最小雙連通支配集問題，提出了一種元啟發式求解算法——變鄰域禁忌搜索算法。算法將原優化問題的求解轉換為一系列判定問題——k雙連通支配集問題的求解，使用兩種鄰域結構更加有效地覆蓋解空間，同時使用擾動及禁忌機制幫助算法跳出局部最優陷阱。通過與現有文獻中的精確算法、啟發式算法在國際文獻公開的38個雙連通圖算例上的實驗對比，結果表明變鄰域禁忌搜索算法能夠有效求解最小雙連通支配集問題，可求得所有公開算例的最優解，并且在稠密圖中計算效率明顯優先于其他算法。

［關鍵詞］ 元啟發式算法； 最小雙連通支配集； 變鄰域搜索算法； 禁忌算法； 雙連通圖

［中圖分類號］ TP393 ［文獻標識碼］ A

無線傳感器網絡（WSN）是物聯網獲取信息的核心，在軍事、醫療、交通、家庭等應用領域都有廣泛應用[1]。在傳感器網絡中，傳感器節點存在能量、存儲和計算等資源約束，節點的失效、鏈路的斷裂會導致網絡失敗，因此構造一個容錯性好、可靠性高的虛擬骨干網是一個非常有意義的課題[2]。構造一個最小雙連通支配集（M2-CDS）來充當虛擬骨干網，可以提高網絡的容錯性和可靠性。近年來，研究人員提出多種不同方法求解M2-CDS問題近似解或最優解。Buchanan等[3]提出基于頂點切割的整數規劃模型，采用lazy-constraint方法解決M2-CDS問題。Lucena等[4]使用混合整數規劃模型的分支剪枝算法求解M2-CDS問題。Wu等[5]用貪心方法來優化無線網絡容錯骨干。Park等[6]提供一種整數編程的優化算法求解M2-CDS問題。Nutov [7]針對最小m-連通支配集問題，其中包括雙連通支配集問題，提出一種比較頂點近似比率的改進近似算法。Jovanovic R等[8]提出求解M2-CDS的貪心隨機自適應搜索算法（GRASP），是一種基于廣度優先搜索的啟發式算法，基本思想是將圖劃分具有約束為雙連通分量[9]，通過添加一個從支配集中去除冗余頂點的修正操作，最后改進已找到的解的質量。Jovanovic R等[10] 對GRASP算法進行擴展，使用基于混合整數線性規劃的局部搜索擴展了GRASP算法。該方法是目前已知求解最小雙連通支配集問題的最好算法。

本文以無權無向的連通圖G（V，E）作為無線傳感器網絡模型，提出了一種變鄰域禁忌搜索算法（VNTS）對問題進行求解。VNTS將求解M-2CDS的問題轉化為可以找到一個給定k大小的2-CDS問題，通過逐步降低k值，使k值趨近或等于2-CDS的最優解；算法包含兩種鄰域結構，同時加入擾動與禁忌機制改進了變鄰域結構，基于該鄰域結構，本文提出的算法具有較高的求解率；最后，將本文算法與其他精確算法和啟發式算法在公開數據集算例上進行對比，實驗結果表明本文提出的算法在大規模算例的求解中具有較強的優勢。

1 最小雙連通支配集問題

對于無權無向的連通圖G（V，E），其中V（G）為圖的頂點集合，E（G）為圖的邊集合，設集合SV且S≠，若x∈V-S， x都與集合S中至少一個頂點相鄰，則S為圖G的一個支配集。若集合S構成的圖G的子圖是連通圖，則稱集合S為圖G的一個連通支配集。若集合S中每一對頂點之間存在至少2條頂點不相交的路徑，則稱集合S為圖G的一個雙連通支配集。若集合S的任何真子集都不是雙連通支配集，則稱集合S為圖G的一個極小雙連通支配集。設集合S是圖G的一個雙連通支配集，若在圖G中不存在雙連通支配集S1，使|S1|lt;|S|，則稱集合S為圖G的最小雙連通支配集。本文研究的最小雙連通支配集問題（M2-CDS），尋找給定無向圖中的最小雙連通支配集。

2 變鄰域禁忌搜索算法

本節介紹用于求解最小雙連通支配集問題的變鄰域禁忌搜索算法（VNTS）。首先對于給定無向圖G（V，E），將圖中頂點分別劃分為支配集頂點，被支配頂點，以及未被支配的頂點。將V頂點集劃分為如下三個部分：

S*集合：S*V，若由S*推導的G的子圖是一個連通圖，則S*集合為候選支配集頂點集合。

S+集合：S+集合是被S*集合所支配的點的集合。

S-集合：S-集合是未被S*集合所支配的點的集合。

2.1 VNTS算法主體框架

本文研究的M2-CDS問題，其對應的判斷問題為是否可以在無向圖中找到頂點數為定值k的雙連通支配集（k-2CDS問題）。具有最小k值的k-2CDS問題的可行解可被認為是原M2-CDS問題的最佳解。

變鄰域禁忌搜索算法（VNTS）主體框架描述見算法1。VNTS包含不同鄰域結構的搜索子算法VNTS-F與VNTS-T，其中VNTS-F以目標評估函數值為非支配集合，記為F的變鄰域禁忌搜索算法，如果當前格局為一個雙連通圖格局，用VNTS-F將當前雙連通格局轉變為k-2CDS格局，找到2-CDS的解；VNTS-T以目標評估函數值為S集合中割點集合大小記為T的變鄰域禁忌搜索算法，如果當前格局不是雙連通圖格局，用算法VNTS-T將當前格局轉變為雙連通圖格局，找到雙連通格局的解。算法1中的迭代終止條件（18行）可設定為算法運行到達運行時間限制或k小于問題已知下界。算法1以整個圖的頂點集合為一個雙連通支配集，每次集合中減少一個頂點，k減1，如果減少后的格局為雙連通圖格局，則執行搜索子算法VNTS-F，找到k-2CDS可行解；如果減少后的格局不是雙連通圖的連通圖格局，則執行搜索子算法VNTS-T，找到雙連通圖格局；如果減少后的格局不是連通格局，則返回原來格局，重新再刪一個點。按照這些步驟進行，若每次都可以得到當前k值的2-CDS可行解，則可以使k值趨近于或等于最小雙連通支配集。

算法1 算法主體框架

輸入：一個雙連通圖

輸出：最好的M2-CDS可行解

1）初始雙連通圖為一個雙連通支配集S；

2）k=|S|；

3）repeat：

4）if S集合為k-2CDS格局

5） 記錄當前k-2CDS可行解，k=k-1，產生新格局；

6）else if S集合是一個雙連通圖格局

7） 執行搜索子算法VNTS-F；

8） if 在λ次數沒有找到k-2CDS格局

9） " k=k-1，產生新格局；

10） end if

11）else if S集合為非雙連通圖的連通圖格局

12） 執行搜索子算法VNTS-T；

13） if 在R次數沒有找到雙連通格局

14） " k=k-1，產生新格局；

15） end if

16）else 返回原來格局，并重新k=k-1產生新格局；

17）end if

18）until 滿足終止條件；

2.2 子算法VNTS-F

VNTS-F的主要思路為：從起始格局開始在保證格局為雙連通格局的情況下不斷改變S*、S+、S－集合，最終使S－集合為空，此時的S*集合為當前k值的一個雙連通支配集。

2.2.1 VNTS-F的目標評估函數 設x 為當前k值下雙連通支配集的一個解，對于解x的目標評估函數可以做出如下定義：

f（x）=|S－|

其中目標函數值為沒有被S*所支配的節點的個數，當f（x）=0時，x為可行解，f（x）gt;0時，x為不可行解。

2.2.2 VNTS-F的一次鄰域動作 鄰域動作定義為從S*集合中移除a放入S+集合中，同時從S+集合中移除掉b點放入S*集合中。每一次交換后更新集合劃分，并比較目標評價函數值，當f（x）=0結束搜索鄰域交換。對于候選解x，它的搜索鄰域范圍為O（|S*|×|S+|），一次鄰域交換的時間復雜度為O（|V|+|E|）。

圖1展示了一次鄰域交換。如圖1a所示，填充的黑點構成連通集合為支配集，即S*集合。空白點屬于被支配集，即S+集合，被黑點連接。填充×的點屬于非支配集，即S－集合。當出現S－集合不為空，當前f（x）=2，則需要進行鄰域交換。如圖1b所示，一次鄰域交換后，當前f（x）=1，鄰域交換后的值更優，替換目標評估函數值，準備再進行下一次鄰域交換。

2.2.3 VNTS-F的主體框架 算法2為子算法VNTS-F求解k-2CDS問題的偽代碼描述。算法以一個雙連通圖格局作為輸入條件，以f（x）為初始最優的目標函數值，進行迭代局部搜索，當出現f（x）=0，記錄輸出最優解S*。當f（x）≠0時，需進行鄰域搜索。在鄰域搜索的過程中，若發現當前多個最好的鄰域動作，算法隨機選取一個鄰域動作更新當前解，再對相應的動作進行禁忌，通常被禁忌的變量在禁忌步長t之后被解禁。當擾動條件被滿足時，算法對歷史最優解進行擾動操作，擾動后繼續搜索，最后直到迭代結束。

算法2 子算法 VNTS-F

輸入：當前k值的雙連通圖格局

輸出：最優解S*集合

1）雙連通圖格局為S*；

2） Sbest←S*；

3）fbest←|S－|；

4）iter←0；

5） while iterlt;λ do

6）" if" fbest=0" then

7） return S*；

8）" else" move_f=find_move_f（S*）；

9） b∈move_f

10） 設置b的禁忌步長；

11） make_move（move_f）；

12） if the perturbation condition is met then

13） perturbation（S*）；

14） end if

15） end if

16） end while

17） return Sbest；

算法3為VNTS-F中尋找最佳鄰域動作find_move_f（）函數的偽代碼描述，根據步驟4的方法，在S*隨機取一點a與同樣在S+隨機取的點b進行交換，再通過增量評估方法update_move（a，b）快速確定每個交換操作的Δf值，Δfbest與Δftabu_best記錄當前鄰域空間中最好的非禁忌操作與禁忌操作増量值。fbest為歷史最優解，整個鄰域空間搜索完畢，算法得到當前最優禁忌動作best_tabu_move和最優非禁忌動作best_move，算法步驟18行通過禁忌過程的解禁策略，算法返回最優的禁忌動作或非禁忌動作。

算法3 VNTS-F的鄰域動作find_move_f

輸入：當前S*集合

輸出：最優的禁忌動作或非禁忌動作

1） 初始化Δfbest，Δf，Δftabu_best；

2） Δfbest←SymboleB@；

3） Δftabu_best←SymboleB@；

4）for a∈S*andb∈S+ do

5） Δf←update_move（a，b）；

6） if b" is tabu" then

7） if Δflt;Δftabu_bestthen

8） Δftabu_best←Δf；

9） best_tabu_move←（a，b）；

10）"" end if

11）else

12）" if Δflt;Δfbestthen

13） Δfbest←Δf；

14） best_move←（a，b）；

15）" end if

16）end if

17）end for

18） if Δftabu_bestlt;Δfbest and Δf+Δftabu_bestlt;fbest then

19） return best_tabu_move；

20） else

21） return best_move；

22） end if[CX]

算法4為算法2中擾動函數perturbation的偽代碼，初始解為當前的局部最優解S*，擾動強度為N，擾動總次數為R，當得到的局部最優解大于全局最優解時，根據步驟4，在S*隨機取N個頂點，與在S*以外的集合取的頂點進行交換，交換完更新當前各集合，找到當前的最優解。當擾動次數大于設定的R值時，算法結束擾動。

算法4 perturbation擾動

輸入：局部最優解S*集合

輸出：擾動后的局部解X

1）X←S*；

2）r←0；

3） while Xgt;=Sbest" do

4） for random（N）∈S*與 random（N）∈（S－S*）交換

5） X←update（S*）；

6） r←r+1；

7）" if rgt;R then

8） 結束擾動，返回X；

9）" end if

10）end for

11）end while

12）return X；

2.3 禁忌搜索策略

在局部搜索算法中，所有交換鄰域的方案需進行禁忌操作。禁忌算法[11]最早由Glover F.教授提出，禁忌搜索的設置，采用數組作為禁忌表，當先前被訪問過的解進入禁忌表，將禁止解再被一次訪問，以VNTS-F為例，采用對移入S*集合的頂點b進行禁忌操作，即在接下來t次迭代中，禁止頂點b被移除S*集合。tt為禁忌步長。以算法開始交換前的目標評估函數值為歷史最優解f。每次交換后進行増量評估，得到的目標函數值為增量Δf。用Δfbest與Δftabu_best記錄當前鄰域空間中最好的非禁忌操作與禁忌操作増量值。當在非禁忌操作中Δflt;Δfbest，更新Δfbest；當在禁忌操作中Δflt;Δftabu_best，更新Δftabu_best。當整個鄰域空間搜索完畢，算法得到當前最優禁忌動作和最優非禁忌動作。通過禁忌過程的解禁策略，即當前的最優禁忌解優于非禁忌解且最優禁忌解優于歷史最優解時，算法返回當前最優禁忌動作，其他情況返回當前最優非禁忌動作。

2.4 子算法VNTS-T

VNTS-T在非雙連通圖的連通圖格局中找到一個雙連通格局解。與VNTS-F不同，VNTS-T目標評估函數為割點集合的大小，鄰域動作為非割點集合中的頂點與支配集合中頂點的交換操作。

2.4.1 VNTS-T的目標評估函數 VNTS-T中，S*集合等于當前k值，并通過Tarjan的線性時間算法[12]，可以得到當前S*集合的割點集合T，以及S*中的非割點集合T*，通過不斷改變T*、S+集合，最終使割點集合T集合為空，此時S*集合為當前k值的雙連通格局的一個解，對于解x的目標評估函數做出如下定義：

g（x）=|T|

其中目標函數值為S*中割點集合T的大小，當g（x）=0時，x為可行解，可以用g（x）的大小作為當前解的優劣判斷標準。

2.4.2 VNTS-T的一次鄰域動作 鄰域動作定義為從T*集合取點a與S+集合中取頂點b進行交換，一次交換作為一次鄰域動作。圖2所示為一次鄰域動作，圖2a填充的黑點構成的集合為連通支配集即S*，空白的點構成的集合為被支配集合即S+，S*中帶有數字的點構成的集合為割點T集合，當前g（x）=3，則需要鄰域交換。如圖2b所示，一次鄰域交換后，當前g（x）=1，鄰域交換后的值更優，則替換交換前的目標函數值，再準備下一次鄰域動作。

2.4.3 VNTS-T的主體框架 算法5為VNTS-T改變集合為雙連通圖格局問題的偽代碼描述。算法以一個非雙連通的連通圖格局作為輸入條件，以連通圖格局中的割點數g（x）為初始最優的目標函數值Δg，進行迭代局部搜索，當出現g（x）=0，輸出雙連通圖格局S*集合。當g（x）≠0時，需進行鄰域搜索。在鄰域搜索的過程中，當發現當前多個最好的鄰域動作時，算法隨機選取一個鄰域動作更新當前解，再對操作的變量進行禁忌操作。

算法5 子算法VNTS-T

輸入：當前k值的連通圖格局

輸出：雙連通格局S*集合

1）連通圖格局為S*；

2）iter←0；

3） while iterlt;[CX1]R" do[CX]

4） if [CX]g（x）=0 [CX1] then[CX]

5）"" return S*；

6）else" move=find_move_τ（S*）；

7）b∈move

8）設置b的禁忌步長；

9） make_move（move）；

10）end if

11）end while

12）return S*；

VNTS-T中尋找最佳鄰域動作find_move_τ（），定義在T*隨機取一點a與同樣在S+隨機取的點b進行交換， 其他的鄰域操作與算法3大致相同，以gbest為歷史最優解，Δgbest與Δgtabu_best記錄當前鄰域空間中最好的非禁忌操作與禁忌操作，最后同樣返回最優的禁忌動作或非禁忌動作。

3 實驗與分析

3.1 實驗配置

實驗所涉及本文所提算法均為Java實現，為了評估算法性能，處理器（Intel核心i7 2.6GHZ）和16GB內存的基于Window10的計算機上運行的所有實驗，并以秒為單位跟蹤了平均運行時間。

3.2 實驗算例

使用LMS算例集對本文所提算法與文獻算法進行對比實驗。LMS算例集包括38個已知雙連通圖的公共算例，由Buchanan等人于文獻[3，4]中給出。此算例集可劃分為7個小算例組，組中頂點數目分別為30、50、70、100、120、150與200。在每一個小算例組中，每一對頂點之間的連接概率分別為5%、10%、20%、30%、50%與70%。

3.3 算法參數調節

本文所提出的VNTS算法中，存在三個待確定參數，分別是解的擾動周期P，在算法2中第13步描述用來控制擾動策略的執行；擾動強度N，控制擾動函數perturbation的擾動強度；以及禁忌長度tt。通過參數校準實驗確定這三個參數的取值。對于擾動周期P，用來判定局部搜索是否已陷入局部最優陷阱，對比了三組數值，分別是100，250，500。擾動強度N作為對當前解擾動程度定義，測試了兩個數值，分別為1，5。對于禁忌長度tt， 對比了三組常數數值，分別是5，10，30。

參數校準實驗使用了LMS算例集中頂點個數為120，連接概率分別為10%、20%、30%、50%、70%的5個算例，作為校準測試算例。對于每種參數與算例的組合情況，進行10次的獨立求解，每次求解限30 s內得到最優的結果。表1為各參數組合的對比實驗結果。其中前三列為算法參數，后兩列分別代表10次求得的解與最優解的平均誤差范圍gap以及平均運行的時間Time。在LMS測試算例中，其給出了每個算例可得到的最佳解opt，在對應算例中10次獨立求得的最優目標函數值best，gap的計算公式為（best－opt）/opt×100%。

由表1可知，對于不同的預設參數組合，實驗結果差距不大，說明算法本身的穩定性。從表中可以看出，當禁忌長度為10，擾動強度設為1，參數得到的結果更接近最優，算法平均運算時間較短。接下來的實驗使用組合參數（10，100，1）作為實驗參數。

3.4 對比實驗結果

在本小節中，將VNTS算法與基于整數規劃的BCN方法[3]、LUN方法[4] 、基于貪心自適應算法GRASP[8]以及在GRASP中加入數學方法擴展的MH方法[10]進行了比較。

表2比較了38個算例，頂點范圍為30-200個，頂點連接概率從5%～70%，越來越稠密的隨機雙連通圖。記錄得到求解當前各個算例的最優解所需的平均計算時間。其中 “*”表示該算法沒有找到最優解，“opt”是算例給出的文獻已知最佳解決方案的大小。

從表2結果來看，在中小規模算例中，本文提出的VNTS算法具有很好穩定性。VNTS的計算效率遠遠優于BCN方法、LUN方法，且差距隨著算例規模的增大而逐漸增大。VNTS與同樣作為啟發式算法的GRASP對比，GRASP在較稀疏的圖中，比如表中在200個頂點連接概率為5%～10%的算例中會找不到最優解，VNTS可以找到表中所有算例的最佳解決方案， VNTS在連接概率較高的稠密圖中計算效率高于GRASP。VNTS與目前最好求解最小雙連通支配集問題的MH方法對比，在30-70個節點、連接概率為30%～70%的算例中，VNTS的計算效率較MH方法高一點，隨著算例節點規模數增大，在連接概率20%～30%的算例中，，VNTS計算效率明顯更好，節點規模增長到公共算例中最大規模200個頂點時，VNTS在連接概率為10%的稀疏圖上的計算效率反超MH方法，在稠密圖中的計算效率也優于MH方法。因此，說明了本文提出的VNTS算法在求解最小雙連通支配集問題上具有較強的競爭力。

4 結論

本文提出了求解最小雙連通支配集問題的VNTS算法。在算法中， 基于集合劃分規則，通過不同的鄰域結構來更好地適應最小雙連通支配集問題，提高了搜索效率，減少了時間。與其他文獻中介紹的算法進行對比，能得到所有公共算例的最優解，且得到算例的最優解的效率比較高，具有較強的競爭力，是求解最小雙連通支配集的有效算法。由于本文方法在頂點連接概率為5%稀疏圖中效率較低，以及缺少大規模公開的雙連通算例進行對比，未來工作重點會針對較稀疏的雙連通圖，對算法進行改進，提高算法在稀疏圖中的高效性，同樣在后續工作中，隨機生成更多大規模的雙連通圖算例進行對比，進一步提高算法的通用性與穩定性。

［ 參 考 文 獻 ］

［1］潘玉蘭，劉廣聰.無線傳感器網絡的特點和應用[J].電子技術與軟件工程， 2019（04）：14-15.

[2] HASAN M Z， AL-TURJMAN F. Optimizing multipath routing with guaranteed fault tolerance in Internet of Things [J]. IEEE Sensors Journal， 2017， 17（19）： 6463-6473.

[3] BUCHANAN A， SUNG J S， BUTENKO S， et al. An integer programming approach for fault-tolerant connected dominating sets [J]. Informs Journal on Computing， 2015， 27（01）： 178-188.

[4] FORTE V D， LUCENA A， MACULAN N. Formulations for the minimum 2-connected dominating set problem [J].Electronic Notes in Discrete Mathematics， 2013， 41： 415-422.

[5] WU， WEILI， ZHANG， et al. A greedy algorithm for the minimum-connected -fold dominating set problem [J]. Journal of Combinatorial Optimization， 2016， 31（01）： 136-151.

[6] AHN N， PARK S. An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks [J]. Wireless Networks， 2015， 21（03）： 783-792.

[7] Nutov Z. Improved approximation algorithms for k-connected m-dominating set problems[J]. Information Processing Letters， 2018， 140： 30-33.

[8] JOVANOVIC R， BAYRAM I.S， VOS. A GRASP approach for solving the 2-connected m-dominating set problem [J]. CoRR， 2016. Abs/1609.05662.

[9] JOVANOVIC R， TUBA M， VOS. A multi-heuristic approach for solving the pre-marshalling problem[J]. Central European Journal of Operations Research， 2017， 25（01）： 1-28.

[10] JOVANOVIC R， VOS. A Matheuristic Approach for Solving the 2-Connected Dominating Set Problem[J]. Applicable Analysis and Discrete Mathematics， 2020， 14（03）： 775-799.

[11] GLOVER F， GREENBERG H J. New approaches for heuristic search： A bilateral linkage with artificial intelligence[J]. European Journal of Operational Research， 1989， 39（02）： 119-130.

[12] HOPCROFT J， Tarjan R， Efficient algorithms for graph manipulation [J]. Communication of the ACM， 1973， 16（06）： 372-378.

Variable Neighborhood Tabu Search for Solving Minimum Biconnected Dominating Set Problem

GUI Wenjie，WU Xinyun，XIONG Caiquan

（School of Computer，Hubei Univ. of Tech.，Wuhan 430068，China）

Abstract： The minimum biconnected dominating set structure is used to construct a fault tolerant virtual back bone network of wireless sensor networks. A variable neighborhood tabu search algorithm （VNTS）， is proposed to solve the minimum biconnected dominating set problem， which is a classical NP hard optimization problem. The algorithm transforms the original optimization problem into a series of decision problems， the" k -biconnected dominating set problem， and uses two neighborhood structures to cover the solution space more efficiently. Meanwhile， a perturbation and a tabu mechanism are implemented to help the algorithm escape from the local optimal trap. The experiment on 38 public instances of biconnected graphs compares the proposed algorithms with the exact and heuristic algorithms in the literature. The results show that the VNTS algorithm is competitive in solving the minimum biconnected dominating set problem. It obtains the optimal solutions of all the instances and outperforms other algorithms on dense graphs in terms of computational efficiency.

Keywords： A meta heuristic algorithm; minimum biconnected dominating set; variable neighborhood search algorithm; tabu search algorithm; biconnected graph

［責任編校： 張巖芳］

［收稿日期］ 2022-08-23

［基金項目］ 國家自然科學基金（61902116）

［第一作者］ 桂文杰（1996-），男，湖北荊門人，湖北工業大學碩士研究生，研究方向為圖的支配集問題的啟發式算法。

［通信作者］ 吳歆韻（1987-），男，江蘇丹陽人，工學博士，湖北工業大學副教授，研究方向為組合優化問題的啟發式算法。