基于多種群的隨機擾動蟻群算法求解分布式約束優化問題

收稿日期：2022-03-04；修回日期：2022-04-25" 基金項目：重慶市教育委員會科學技術研究計劃青年資助項目（KJQN202001139）；重慶市基礎研究與前沿探索資助項目（cstc2018jcyjAX0287）；重慶理工大學研究生創新項目（clgycx20203116）；重慶理工大學科研啟動基金資助項目（2019ZD03）

作者簡介：石美鳳（1989-），女，湖南人，講師，碩導，博士，主要研究方向為計算智能、分布式人工智能（shimf@cqut.edu.cn）；肖詩川（1996-），女，四川人，碩士研究生，主要研究方向為計算智能、分布式人工智能；馮欣（1982-），女，重慶人，副教授，碩導，博士，主要研究方向為計算機視覺.

摘 要：

針對現有的基于蟻群優化思想求解分布式約束優化問題的算法收斂較慢、容易陷入局部最優等問題，提出了一種基于多種群的隨機擾動蟻群算法（random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems，RDMAD）來求解分布式約束優化問題。首先，RDMAD提出了一種分工合作機制，將種群按比例劃分為采用貪婪搜索的子種群和采用啟發式搜索的子種群，同時構建分級更新策略，提高算法收斂速度和求解質量；然后對采用貪婪搜索的子種群設計自適應變異算子和獎懲機制，防止算法陷入局部最優；最后在算法陷入停滯時觸發隨機擾動策略，增加種群多樣性。將RDMAD與七種最先進的非完備算法在三類基準問題上的尋優結果進行了實驗對比，結果表明RDMAD在求解質量和收斂速度上優勢明顯，且穩定性較高。

關鍵詞：分布式約束優化問題；蟻群算法；自適應變異算子；非完備算法

中圖分類號：TP301.6"" 文獻標志碼：A"" 文章編號：1001-3695（2022）09-019-2683-06

doi： 10.19734/j.issn.1001-3695.2022.03.0084

Random disturbance based multi-population ant colony algorithm to

solve distributed constraint optimization problems

Shi Meifeng， Xiao Shichuan， Feng Xin

（College of Computer Science amp; Engineering， Chongqing University of Technology， Chongqing 400054， China）

Abstract：Ant colony algorithms to solve distributed constraint optimization problems （ACO_DCOP） have some shortcomings including very slow convergence speed and easily falling into local optima. To cope with these issues，this paper proposed a RDMAD. The method introduced a division of labor and cooperation mechanism to divide the population into two subpopulations for greedy search and heuristic search respectively. It also constructed a hierarchical update strategy to speed up convergence and improve solution quality. Furthermore，this paper designed an adaptive mutation operator and a reward and punishment mechanism for the greedy search subpopulation to prevent RDMAD falling into the local optima. Simultaneously，this paper introduced a random disturbance strategy to increase the population diversity when RDMAD was stagnant. To verify the performance of the proposed algorithm，it compared RDMAD with the other seven advanced incomplete algorithms on three types of benchmark problems. The extensive experimental results show that the RDMAD algorithm is significantly superior to the state-of-the-arts algorithms in solution quality and convergence speed. In addition，RAMAD is far stable than the competing algorithms.

Key words：distributed constraint optimization problems; ant colony algorithm; adaptive mutation operator; incomplete algorithm

0 引言

多智能體系統（multi-agent system，MAS）［1］是分布式人工智能領域重要的一部分。分布式約束優化問題（distributed constraint optimization problems，DCOP）［2］是MAS基本框架之一，被廣泛地應用于許多實際問題建模，如傳感器網絡［3］、任務調度［4］等。

在過去的二十年里，許多算法被提出用來求解DCOP，其中完備算法可得到問題的最優解。SyncBB［5］、AFB［6］、ADOPT［7］、BnB-ADOPT［8］等是典型的基于搜索的完備算法。DPOP［9］作為典型的基于推理的完備算法，其利用動態規劃思想求解DCOP，但DPOP在求解過程中會遭受指數級的內存消耗。MB-DPOP［10］算法被提出用于降低DPOP算法內存消耗。為提高MB-DPOP算法性能，Chen等人［11］提出了RMB-DPOP算法減少了MB-DPOP算法中的冗余推理，提高了算法的可擴展性；Rashik等人［12］利用交叉邊一致性縮短了DPOP的運行時間。由于DCOP是NP-hard，相比之下，非完備算法雖然不能找到最優解，但在通信和計算方面有更好的性能。其中，基于局部搜索的非完備算法是目前的研究熱點，其中包括DSA［3］和GDBA［13］等。此外，ALS［14］、PDS［15］和LSGA［16］等框架被用來提高基于局部搜索的算法的求解質量。max-sum［17］和max-sum_ADVP［18］等是基于推理的非完備算法，其中agent通過因子圖傳播和積累效用。基于采樣的非完備算法（如DUCT［19］）則通過對搜索空間進行采樣來求解DCOP。近年來出現了一類利用種群求解DCOP的非完備算法。Mahmud 等人［20］提出了一種利用進化優化思想求解DCOP的算法；Chen等人［21］提出了利用蟻群優化思想求解DCOP的算法（ACO_DCOP），ACO_DCOP是目前唯一利用蟻群優化思想求解DCOP的算法，其從傳統蟻群算法演變而來，然而ACO_DCOP算法中僅利用單種群尋優，同時受信息素影響，收斂較慢，容易陷入局部最優。目前多種群策略被廣泛使用，薛宏全等人［22］通過分析螞蟻分工，利用核心蟻群和搜索蟻群的配合有效地解決了車間調度問題；朱佑滔等人［23］提出了一種多種群蟻群算法用于求解機械手臂的路徑規劃問題；陳佳等人［24］采用主從蟻群的多種群機制有效求解旅行商問題。因此針對ACO_DCOP收斂較慢、易陷入局部最優等問題，本文提出一種基于多種群的隨機擾動蟻群算法求解分布式約束優化問題（RDMAD）。本文的主要貢獻包括以下幾方面：a）提出了一種分工合作機制，子種群分別通過執行貪婪搜索和啟發式搜索使得局部和全局搜索相互協調，可以更好地探索解空間和開發優秀解；b）提出了一種隨機擾動策略，在算法陷入停滯時觸發隨機擾動策略，種群重新劃分為三個子種群，新增采用隨機選值的子種群，增加種群多樣性，有助于算法跳出局部最優；c）設計了一種分級更新策略，執行不同任務的子種群采用不同更新方式，提高了算法的收斂速度和求解質量。

1 相關工作

1.1 分布式約束優化問題

DCOP可定義為一個四元組〈X，D，F，A〉［25］，其中，A是agent的集合{a1，a2，…，an}；X是離散變量的集合{x1，x2，…，xm}，一個agent控制一個或多個變量，m≥n；D是離散變量值域的集合{D1，D2，…，Dm}，其中Di是變量xi的值域；F是約束關系函數的集合{f1，f2，…，fq}，其中fi∈F是子集xiX的函數，該函數定義了xi中變量間的約束關系。

DCOP求解算法的目標是為尋找一組賦值組合X*使式（1）所示全局約束代價最小。

X*=arg minX∑qi=1fi（xi）（1）

本文中一個agent控制一個變量，因此這里“agent”和“變量”可互換。圖1（a）為DCOP的約束圖，其中一個節點表示一個agent，兩個agent之間的邊表示它們之間存在約束關系；圖1（b）為DCOP的約束矩陣，其中0、1為變量的取值，矩陣中其余值為當有約束的兩個變量取值時對應的代價大小，例如當x1=0、x2=0時，對應代價值為5。

蟻群優化算法（ant colony optimization，ACO）是一種基于種群的求解組合優化問題的元啟發式算法，已成功應用于旅行商問題、約束滿足問題等。由于DCOP中沒有實際的路徑可用，傳統的ACO算法無法直接用于求解DCOP。目前僅有ACO_DCOP成功將蟻群優化思想應用于求解DCOP。

ACO_DCOP利用agent之間的消息傳遞機制來模擬螞蟻的運動，首次將群體智能應用于求解DCOP。以圖1為例得到圖2（c）所示的信息素路徑構造圖，其中節點表示agent。 首先將圖1（a）中的約束圖轉換為廣度優先搜索偽樹［26］，如圖2（a）所示；然后構建agent之間的消息傳遞順序（螞蟻爬行方向），如圖2（b）所示，其中上層agent的優先級高于下層agent，同層間的agent鄰居個數越多，值域越大優先級越高，若兩個同層的agent具有相同的鄰居數和值域大小，則agent的命名id越小，優先級越高。 因此agent ai的鄰居可分為高優先級鄰居Hi和低優先級鄰居Li，且消息從高優先級的agent傳向低優先級的agent，同時根據agent的取值不同，每兩個agent之間有多條信息素路徑。如圖2（c）信息素路徑構造圖，當ai取值為di，aj取值為dj時，該路徑上的信息素濃度為τij（di，dj）。

每次迭代中，螞蟻從優先級最高的agent出發，在每只螞蟻獲得取值后，agent將螞蟻取值發送給其低優先級鄰居。當接收到高優先級鄰居的螞蟻取值后，agent ai首先為每只螞蟻合并收到的解集合，當ai收到其所有高優先級鄰居的螞蟻取值后，采用轉移概率為每只螞蟻選取變量值域中的取值，否則等待其高優先級鄰居的取值。ai完成為每只螞蟻取值后將螞蟻取值發送給自己的低或最低優先級鄰居。當最低優先級agent收到所有螞蟻取值后，此時每只螞蟻已經完成解的構建，計算每只螞蟻構建的解的代價，代價越小解的質量越好，根據代價更新全局最優解并且計算每只螞蟻的信息素增量，然后將信息素增量發送給所有agent；agent收到信息素增量信息后，更新和蒸發與其高優先級鄰居間的信息素路徑上的濃度，到此一次迭代結束。

2 RDMAD算法

本文提出了一種基于多種群的隨機擾動蟻群算法用于求解DCOP，其主要采用分工合作機制、分級更新和隨機擾動策略。該算法利用子種群在尋優過程中的不同指導作用，有效地提高了算法收斂和求解性能。

2.1 初始化階段

RDMAD算法利用螞蟻在agent之間的運動來構造解。首先RDMAD將agent之間的約束圖轉換為廣度優先搜索的偽樹結構，然后根據偽樹結構構建agent消息傳遞順序，生成最終構造圖。RDMAD算法中，信息素信息由低優先級agent保存。在完成構造圖構建后，初始化參數，并且每個agent初始化螞蟻解集為空，然后優先級最高agent為每只螞蟻隨機取值，再將取值信息發送給自己的低優先級鄰居。以圖2為例，x1為優先級最高節點，假設種群規模為2，x1為螞蟻1取值為1，為螞蟻2取值為0，則將x1的id和螞蟻取值{1，0}發送給x1的低優先級鄰居x2、x3和x4。

2.2 分工合作機制

基于種群求解DCOP的策略近幾年才出現，這類算法都是直接從傳統群體智能算法中演變而來，僅利用了單種群來尋優。本文在現有采用螞蟻轉移概率取值的種群上增加了采用貪婪搜索的子種群，利用多種群合作更好地平衡開發和探索。當agent ai接收到來自其高優先級鄰居的取值時，首先合并所有取值，當ai接收到所有高優先級鄰居的取值時，ai開始為螞蟻選值，每個子種群的選值策略如下：

1）子種群1

agent ai采用貪婪搜索為子種群1中的螞蟻取值，該方式增強了螞蟻對局部的探索，有利于提高算法收斂速度。ai采用式（2）為螞蟻k選取使ai與其鄰居間約束代價和最小時的取值di。

di=arg mindi∈Di（∑j∈Hicostij（di，Vk，j）+esti（di））（2）

其中：Di是值域；Vk，j是ai的高優先級鄰居aj對螞蟻k的取值；costij（dj，Vk，j）是ai為螞蟻k取值為di、aj為螞蟻k取值為Vk，j時的約束代價。式（3）定義了ai與其低優先級鄰居Li之間的最小約束代價和的預估值esti（di），其初始化為最優解。

esti（di）=∑j∈Li mindj∈Djcostij（di，dj）（3）

為避免種群因貪婪搜索快速陷入局部最優，本文為子種群1設計了一種自適應調整的變異算子pm，其定義為

pm=1－mtotalcycle－curcycletotalcycle（4）

其中：m為權值，可調整變異算子大小；totalcycle為總的迭代次數；curcycle為當前迭代次數。當ai為種群1取值完成時，采用隨機概率q∈［0，1］挑選螞蟻個體進行值交換，當小于pm時，ai隨機選擇螞蟻k′，將當前螞蟻k的取值與螞蟻k′的取值互換，得到新個體。

2）子種群2

子種群2保留原有的轉移概率取值方式，其主要采用蟻群優化思想中的啟發式搜索，這有利于螞蟻對agent ai的解空間進行全局探索。該概率計算依賴于信息素因子和啟發式因子，同時配合輪盤賭。ai采用式（5）為螞蟻k取值為di的概率為

pk，i（di）=θk，i（di）αηk，i（di）β∑d′i∈Diθk，i（d′i）αηk，i（d′i）β（5）

其中：α和β分別為信息素因子和啟發式因子權重，信息素因子θk，i（di）影響螞蟻對路徑的探索，其定義如式（6）所示。

θk，i（di）=∑j∈Hiτij（di，Vk，j）（6）

其中：θk，i（di）為ai對螞蟻k取值di時，ai與其所有高優先級鄰居之間的信息素濃度之和。啟發式因子ηk，i（di）影響了螞蟻對解的開發，ai與其鄰居間的約束代價和越大，啟發式因子越小，當前解被開發的可能性越小，如式（7）所示。

ηk，i（di）=1∑j∈Hicostij（di，Vk，j）+eLi（di）－LC（7）

其中：LC為ai與其鄰居間的最小約束代價和，用于評估值di的可開發程度，如式（8）所示。

LC=mindi∈Di（∑j∈Himindj∈Djcostij（di，dj）+eLi（di））－1（8）

2.3 隨機擾動策略

種群的多樣性影響了算法對解空間的搜索范圍，由于螞蟻是依靠路徑上的信息素濃度尋優的，ACO_DCOP在迭代后期，種群多樣性越來越小，所以算法容易陷入局部最優。本文設計了一種隨機擾動策略來增加種群多樣性。當算法停滯次數等于設定的閾值count，此時觸發隨機擾動策略。算法將種群重新劃分成三個子種群，其中子種群1和2的任務不變，子種群3的任務則是擾動信息素積累，按式（9）采用完全隨機取值，打破原有信息素累積規律。

di=random（Di）（9）

2.4 分級更新策略

根據每個子種群的引導作用不同，構建分級更新策略。首先當最低優先級agent ai接收到所有高優先級鄰居的取值后，計算每只螞蟻的信息素增量Δk，如式（10）所示。

Δk=1－costk－bestcost1K∑Kk=1costk－bestcost（10）

其中：costk為螞蟻k構建的完整值分配對應的代價；bestcost為全局最優代價值；K為種群規模。最低優先級ai將信息素增量Δk、種群解集和最優解發送給其他所有agent，agent利用信息素增量Δk更新與其高優先級鄰居之間信息素路徑濃度，更新策略如式（11）所示。

τij（Vk，i，Vk，j）=τij（Vk，i，Vk，j）+Δ′k" j∈Hi（11）

Δ′k=δk，ij"" k∈子種群10.8Δkk∈子種群21.2Δkk∈子種群3

（12）

式（12）是各子種群信息素增量的定義。由于子種群1對種群的探索方向具有引導作用，子種群1的更新方式按式（13）所示獎懲機制進行。

δk，ij=Δkn1"" Δk≥0Δk/n1Δklt;0（13）

其中：n1為子種群1的規模。若Δk為正，相應路徑將獲得獎勵，否則將受到處罰。該機制可減小路徑上信息素濃度的差異，防止算法過快收斂。

分級更新策略體現了多種群在尋優過程中對算法的不同指導作用，通過這種模式提高了算法的收斂速度和尋優質量。

2.5 信息素蒸發

信息素蒸發階段可使得螞蟻忘記了之前不好的路徑，agent在更新信息素后，根據式（14）進行信息素蒸發，其中ρ為蒸發率，τ0為初始化濃度，信息素范圍為［τmin，τmax］。

τij（di，dj）=（1－r1ρ）τij（di，dj）+r2ρτ0（14）

其中：r1、r2控制了蒸發率的大小，默認為1。在觸發隨機擾動策略時，r1=2，r2=0.5，增強信息素蒸發有助于算法跳出局部最優。

2.6 RDMAD算法步驟

算法1 RDMAD算法（for agent ai）

輸入：初始化參數α，β，ρ，τ0，K，count。

輸出：使全局約束代價最小的一組賦值組合X*。

for each di∈Di do 計算esti（di）; end for

for each 螞蟻k do

初始化解集：Vk，←{}，V←V∪Vk，；

if ai是優先級最高節點

for each 螞蟻k do

ai為螞蟻隨機取值為Vk，i，Vk，←Vk，∪Vk，i；

end for

發送螞蟻取值信息V和ai的id給低優先級鄰居Li；

end for

when agent ai收到了取值信息（id，recv_V）

for each螞蟻k do Vk，←Vk，∪recv_V； end for

if ai從其高優先級鄰居收到了所有取值信息

for each螞蟻k do

if c==count

ai根據式（2）（4）為子種群1取值；

ai根據式（5）（9）分別為子種群2、3取值；

else ai根據式（2）（4）（5）為子種群1、2取值；

合并取值Vk，←Vk，∪Vk，i；

end for

ai發送取值信息{id，V}給Li或最低優先級ai；

if ai優先級最低且收到所有取值信息

更新bestcost和其對應的最佳值分配v*，更新count，按式（10）計算每只螞蟻的信息素增量Δk；

發送信息素信息{V，Δ，v*}給所有agent

when agent ai收到了信息素信息（id，recv_V）：

根據式（11）（14）分別更新和蒸發信息素，更新esti（di）；

if 不滿足終止條件 then 開始下一輪循環。

在信息素更新和蒸發階段結束過后，還要對agent ai與其低優先級鄰居Li之間的最小約束代價和的預估值esti（di）進行更新。由于在分布式場景中，agent僅知道其鄰居的信息，并且根據消息傳遞順序，agent僅知道其高優先級鄰居的取值。所以該預估值可幫助ai估算與其所有鄰居的最優代價和，有助于啟發式因子對當前取值的評估。

算法2 更新預估值esti（di） （for agent ai）

輸入：種群解集V。

輸出：更新后的預估值esti（di）。

for each di∈Di do

sum=0，num=0；

for each 螞蟻k do

if Vk，i=di then

sum+=∑j∈Li costij（di，Vk，j），num=num+1；

end for

if num！=0 then

ave= sum/num，esti（di）=（esti（di）+ave）/2；

end for

2.7 RDMAD算法復雜性分析

RDMAD算法的復雜性分析主要包含算法的消息數、空間復雜度和時間復雜度。將改進后的RDMAD與ACO_DOCP算法進行比較。在每次迭代中，除最低優先級agent外，每個agent都會向其低優先級鄰居（或最低優先級鄰居）發送取值信息，最低優先級agent會向所有agent發送信息素信息。由于取值信息中包含了螞蟻的解集，所以值消息的大小為O（nK），n為agent個數，所以RDMAD中值消息大小與ACO_DCOP算法一致；包含了螞蟻的解集、信息素增量和最優解的信息素消息的大小為O（（K+1）n+K），所以RDMAD算法中信息素消息大小與ACO_DCOP算法也一致。

每個agent ai存儲與其高優先級鄰居間的信息素路徑需要O（|Hi‖Di‖Dj|）大小的空間，因此RDMAD算法需要的空間大小與ACO_DCOP算法一致。時間復雜度主要是取值計算，在最壞情況下，當ai為螞蟻k取值時，對于值域Di中的每個值di會遍歷其所有高優先級鄰居的取值，因此ai計算一個值消息需O（K|Hi‖Di|）次操作。RDMAD算法的時間復雜度與ACO_DCOP算法一致。

3 實驗與結果分析

3.1 實驗設置

實驗采用三類基準問題進行算法性能測試，包括隨機DCOPs［25］（EXP-1、EXP-2）、無尺度網絡問題［27］（EXP-3、EXP-4）和加權圖著色問題 （EXP-5）。具體相關信息如表1所示。

3.2 參數分析

為驗證重要參數對RDMAD算法的影響，以隨機DCOPs（EXP-1）為例，對RDMAD中的信息素因子α、啟發式因子β、信息素蒸發率ρ以及觸發閾值count進行了實驗分析。為保證實驗結果的公平性，本實驗中采用控制變量法對每個參數進行調節，同時每個參數的每個值取獨立運行30次的平均值作為該取值下的實驗結果。各參數的實驗結果如圖3所示。

圖3（a）顯示了α變化對RDMAD性能的影響，從圖中可以看到，隨著α的增大算法求得的解質量也隨之提高，但在αgt;1后，算法的性能開始下降，因此根據實驗結果，α取1時RDMAD的性能最好。圖3（b）中的β取值也對RDMAD的性能有較大的影響，從圖中可以看出β越大，算法的求解質量和收斂性能都在提升，但當βgt;3后解的質量開始下降。從圖3（c）的實驗結果可以得出，信息素的蒸發率ρ也會影響算法的性能，但它的影響略小于參數α和β，當ρ=0.002 5時，RDMAD得到的解質量最好。圖3（d）為觸發間隔的選擇實驗，實驗結果表明在觸發隨機擾動策略時，設置合適的觸發間隔能有效提高求解質量。

因此根據實驗結果，適當設置重要參數的值有利于提高算法的求解質量和收斂性能。為不失公平性，對比算法的參數采用原文推薦值。RDMAD算法參數設置為：α=1，β= 3，ρ=0.002 5，τ0=3，count=80，K=20。在未觸發隨機擾動策略時，子種群1、2的規模分別為0.5K、0.5K；在觸發隨機擾動策略后，子種群1、2和3的規模分別為0.5K、0.3K和0.2K。

3.3 實驗結果及分析

為驗證RDMAD算法的魯棒性和尋優性能，在測試問題上與其他優秀的非完備DCOP算法進行比較，包括PDS-DSA［15］、GDBA［13］、ACO_DCOP［20］、DSAN［28］、DSA［3］、LSGA_DSA［16］、AED［21］。由于非完備算法具有隨機性，所以每個實例取獨立運行30次的均值為結果，每個測試問題隨機生成20個實例。

表2為RDMAD與ACO_DCOP以及其他對比算法在每個測試問題的20個實例上的約束代價的均值（mean）和標準差（std dev）。同時，采用 Wilcoxon符號秩和檢驗法對實驗結果進行統計分析，其中“+”表示RDMAD算法在20個實例上得到的結果優于對比算法的個數；而“-”則表示相反意思。從表2的mean值可以看出，在除EXP-2外的所有測試問題上，RDMAD得到的問題的約束代價值小于其他所有對比算法。且在EXP-2測試問題上， RDMAD算法的mean值只是略大于AED算法。從統計結果來看，RDMAD每次得到的結果都優于ACO_DCOP、DSA、DSAN和GDBA算法，且在其他測試問題上也具有明顯優勢，穩定性較高。另外，通過表2中的Wilcoxon符號秩和檢驗法的結果p-value也再一次驗證了RDMAD在求解質量方面優勢明顯。

圖4為所有算法在不同測試問題上的收斂曲線。在五個測試問題上，RDMAD均具有優秀的收斂和尋優性能。在EXP-1上， RDMAD相比原來的ACO_DCOP提高了約4.2%，相比其他算法提高了約1.3%～12.9%。從各算法的收斂曲線可以發現，由于缺乏全局信息，DSA和DSAN算法的尋優能力較差。采用LSGA框架的DSA雖然提高了DSA的局部搜索性能，但其對DSA的性能提升有限，相比LSGA-DSA，RDMAD具有更好的收斂性能。另外ACO_DCOP和AED算法都利用了種群對問題進行尋優，但從圖中可以發現，RDMAD在收斂和尋優質量上比這兩種算法表現更好。在EXP-2上，由于測試問題密度過高，agent間的約束增多，所以算法的性能受到一定影響，但RDMAD仍能保持較好的尋優性能，其收斂和尋優質量都優于ACO_DCOP，相比ACO_DCOP提高了約1.4%。同時RDMAD能夠得到與LSGA-DSA和AED算法同等質量的解，且收斂優勢明顯，相比其他算法提高了約1.1%～2.7%。同樣地，在EXP-3和EXP-4上RDMAD優于ACO_DCOP約4.4%和2.8%，相比其他算法分別提高約4.1%～17.2%和0.6%～8.3%。可以看出，RDMAD在無尺度網絡問題上（EXP-3，EXP-4）的表現更優秀，收斂速度也具有明顯優勢，這表明RDMAD在求解結構化問題時性能顯著。最后在EXP-5測試問題上，RDMAD同樣表現出了良好的收斂和尋優性能，優于ACO_DCOP約18.4%，同時相比其他算法提高了約18.7%～62.7%。

4 結束語

有效利用群體智能求解分布式約束優化問題是提高DCOP求解算法性能的新思路，本文提出了一種基于多種群的隨機擾動蟻群算法求解分布式約束優化問題。該算法首先充分地利用種群特性，通過多種群分工配合分級更新策略更好地平衡算法的探索和開發能力，提高了算法的收斂速度和求解質量。在此基礎上利用隨機擾動策略增加種群多樣性，避免算法陷入局部最優。將RDMAD與ACO_DCOP以及其他六種目前最先進的非完備算法在三類基準問題上進行比較，RDMAD算法在求解質量和收斂速度方面優勢顯著，且具有良好的穩定性。但是RDMAD缺少對agent局部收斂狀態的利用，在以后的工作中將考慮引入信息熵等狀態評價指標與隨機擾動機制結合。

參考文獻：

［1］劉鴻福，陳璟，沈林成. 分布式約束滿足問題及其在MAS任務分配中的應用 ［J］. 計算機應用研究，2009，26（2）： 515-517. （Liu Hongfu，Chen Jing，Shen Lincheng. Distributed constraint satisfaction problem and its application to multi-agent system task allocation ［J］. Computer Application Research，2009，26（2）： 515-517. ）

［2］Leite R，Fabricio E，Barthès J P. Distributed constraint optimization problems： review and perspectives ［J］. Expert Systems with Applications，2014，41（11）： 5139-5157.

［3］Zhang Weixiong，Wang Guandong，Xing Zhao，et al. Distributed stochastic search and distributed breakout： properties，comparison and applications to constraint optimization problems in sensor networks ［J］. Artificial Intelligence，2005，161（1-2）： 55-87.

［4］Sultanik E A，Modi P J，Regli W C. On modeling multiagent task scheduling as a distributed constraint optimization problem ［C］// Proc of the 20th International Joint Conference on Artificial Intel-ligence. 2007： 1531-1536.

［5］Hirayama K，Yokoo M. Distributed partial constraint satisfaction problem ［C］// Proc of International Conference on Principles and Practice of Constraint Programming. Berlin： Springer，1997： 222-236.

［6］Gershman A，Meisels A，Zivan R. Asynchronous forward bounding for distributed COPs ［J］. Journal of Artificial Intelligence Research，2009，34（1）： 61-88.

［7］Modi P J，Shen W M，Tambe M，et al. ADOPT： asynchronous distri-buted constraint optimization with quality guarantees ［J］. Artificial Intelligence，2005，161（1）： 149-180.

［8］Yeoh W，Felner A，Koenig S. BnB-ADOPT： an asynchronous branch-and-bound DCOP algorithm ［J］. Journal of Artificial Intelligence Research，2010，38（5）： 85-133.

［9］Petcu A，Faltings B. A scalable method for multiagent constraint optimization ［C］// Proc of the 19th International Joint Conference on Artificial Intelligence. 2005： 266-271.

［10］Petcu A，Faltings B. MB-DPOP： a new memory-bounded algorithm for distributed optimization ［C］// Proc of the 20th International Joint Conference on Artificial Intelligence. 2007： 1452-1457.

［11］Chen Ziyu，Zhang Wenxin，Deng Yanchen，et al. RMB-DPOP： refining MB-DPOP by reducing redundant inference ［C］// Proc of the 19th International Conference on Autonomous Agents and Multiagent Systems. Richland，SC： International Foundation for Autonomous Agents and Multiagent Systems，2020： 249-257.

［12］Rashik M，Rahman M M，Khan M M，et al. Speeding up distributed pseudo-tree optimization procedures with cross edge consistency to solve DCOPs ［J］. Applied Intelligence，2021，51（3）： 1733-1746.

［13］Okamoto S，Zivan R，Nahon A. Distributed breakout： beyond satisfaction ［C］// Proc of the 25th International Joint Conference on Artificial Intelligence. 2016： 447-453.

［14］Zivan R. Anytime local search for distributed constraint optimization ［C］// Proc of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. 2008： 1449-1452.

［15］Yu Zhepeng，Chen Ziyu，He Jingyu，et al. A partial decision scheme for local search algorithms for distributed constraint optimization problems ［C］// Proc of the 16th International Conference on Autonomous Agents and Multiagent Systems. Richland，SC： International Foundation for Autonomous Agents and Multiagent Systems，2017： 187-194.

［16］Chen Ziyu，Liu Lizhen，He Jingyuan，et al. A genetic algorithm based framework for local search algorithms for distributed constraint optimization problems ［J］. Autonomous Agents Multi-Agent Systems，2020，34（2）： article No. 41.

［17］Farinelli A，Rogers A，Petcu A，et al. Decentralised coordination of low-power embedded devices using the max-sum algorithm ［C］// Proc of the 7th International Conference on Autonomous Agents and Multiagent Systems. Richland，SC： International Foundation for Autonomous Agents and Multiagent Systems，2008： 639-646.

［18］Zivan R，Peled H. Max/min-sum distributed constraint optimization through value propagation on an alternating DAG ［C］// Proc of the 12th International Conference on Autonomous Agents and Multiagent Systems. Richland，SC： International Foundation for Autonomous Agents and Multiagent Systems，2012： 265-272.

［19］Ottens B，Dimitrakakis C，Faltings B. DUCT： an upper confidence bound approach to distributed constraint optimization problems ［J］. ACM Trans on Intelligent Systems and Technology，2017，8（5）： article No. 69.

［20］Mahmud S，Choudhury M，Khan M M，et al. AED： an anytime evolutionary DCOP algorithm ［C］// Proc of the 19th International Confe-rence on Autonomous Agents and Multiagent Systems. Richland，SC： International Foundation for Autonomous Agents and Multiagent Systems，2020.

［21］Chen Ziyu，Wu Tengfei，Deng Yanchen，et al. An ant-based algorithm to solve distributed constraint optimization problems ［C］// Proc of the 32nd AAAI Conference on Artificial Intelligence. Pola Alto，CA： AAAI Press，2018： 4654-4661.

［22］薛宏全，魏生民，張鵬，等. 基于多種群蟻群算法的柔性作業車間調度研究 ［J］. 計算機工程與應用，2013，49（24）： 243-248. （Xue Hongquan，Wei Shengmin，Zhang Peng，et al. Flexible Job-Shop scheduling based on multiple ant colony algorithm ［J］. Computer Engineering and Applications，2013，49（24）： 243-248. ）

［23］朱佑滔，何志琴，施文燁. 多種群蟻群算法在機械手臂路徑規劃中的設計與應用 ［J］. 機械傳動，2021，45（4）： 160-165. （Zhu Youtao，He Zhiqin，Shi Wenye. Design and application of multi-colony ant algorithm in path planning of manipulator ［J］. Journal of Mechanical Transmission，2021，45（4）： 160-165. ）

［24］陳佳，游曉明，劉升，等. 結合信息熵的多種群博弈蟻群算法 ［J］. 計算機工程與應用，2019，55（16）： 170-178. （Chen Jia，You Xiaoming，Liu Sheng，et al. Entropy-game based multi-population ant colony optimization ［J］. Computer Engineering and Applications，2019，55（16）： 170-178. ）

［25］Zivan R，Okamoto S，Peled H. Explorative anytime local search for distributed constraint optimization ［J］. Artificial Intelligence，2014，212（7）： 1-26.

［26］Chen Ziyu，He Zhen，He Chen. An improved DPOP algorithm based on breadth first search pseudo-tree for distributed constraint optimization ［J］. Applied Intelligence，2017，47（3）： 607-623.

［27］Barabási A L，Albert R. Emergence of scaling in random networks ［J］. Science，1999，286（5439）： 509-512.

［28］Arshad M，Silaghi M C. Distributed simulated annealing ［EB/OL］. （2017-08-23）. https：//cs.fit.edu/～msilaghi/papers/IOSDSA.pdf.