求解分布式約束優化問題的鄰居忽略策略局部搜索算法

摘 要：針對現有基于局部搜索思想的分布式約束優化問題求解算法存在容易陷入局部最優的問題，提出了一系列用于求解分布式約束優化問題（DCOP）的基于鄰居忽略策略（NI）的局部搜索算法，以擴大對解空間的搜索，避免陷入局部最優。為了研究智能體之間約束關系的可變性和隨機性對局部搜索的影響和極值對于局部搜索的影響，分別設計了單個隨機鄰居忽略策略和極值鄰居忽略策略。同時，基于單個鄰居隨機忽略策略和極值鄰居忽略策略，設計了用于平衡算法探索和開發能力的混合策略。此外，還設計了多個鄰居隨機忽略策略，以探討求解DCOP時同時隨機忽略多個鄰居的可行性，并在理論上證明了隨機鄰居忽略策略對智能體之間的約束關系沒有影響。將提出的一系列基于鄰居忽略策略的局部搜索算法與十種先進的非完備算法在三類基準問題上的尋優結果進行了實驗對比，結果表明所提一系列用于求解DCOP的基于鄰居忽略策略的局部搜索算法顯著優于目前先進的非完備算法。

關鍵詞：分布式約束優化問題；鄰居忽略；解空間擴大搜索；局部搜索算法

中圖分類號：TP18"" 文獻標志碼：A"" 文章編號：1001-3695（2025）03-019-0788-07

doi：10.19734/j.issn.1001-3695.2024.08.0297

Series of neighbor ignoring strategies for local search algorithms for distributed constraint optimization problems

Shi Meifeng，Jia Guoyan

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

Abstract：The local search algorithm for solving DCOP has the advantages of high flexibility，high efficiency，and high fault tolerance，but also easy to fall into the local optimum as the incomplete algorithm.Considering this，this paper designed a series of neighbor ignoring strategies to expand the search for solution spaces.Specifically，the single random neighbor ignoring strategy delved into the impact of variability and randomness in the constraint relationships among agents on the local search.In contrast，extreme neighbor ignoring focused on discussing the influence of extreme values on the local search algorithm.Furthermore，the hybrid strategy denoted as single random and extreme neighbor ignoring integrated the previous two to strike a more optimal balance between exploration and exploitation.In addition，the multiple random neighbor ignoring strategy offers a way to investigate the feasibility and implications of ignoring multiple neighbors simultaneously when solving DCOP.Theoretical ana-lysis reveals that the proposed neighbor ignoring strategy has no discernible impact on the constraints between agents.The extensive experimental results on three benchmark problems demonstrate the superiority of utilizing the neighbor ignoring strategy within the local search framework over the current state-of-the-art incomplete algorithms.

Key words：distributed constraint optimization problem（DCOP）;neighbor ignoring（NI）;exploration space expanding;local search algorithms

0 引言

多智能體系統（multi-agent system，MAS）［1］是由多個獨立智能體組成的系統，這些智能體可以相互交互、協作和競爭，以實現共同目標或解決復雜問題。分布式約束優化問題（DCOP）［2］是多智能體系統的基本模型，已成功應用于任務調度、移動傳感器協調、合作搜索等實際問題［3～8］。

學者們提出了許多求解DCOP的算法，根據其求解目標可以分為完備算法和非完備算法。由于DCOP是NP-hard［2］問題，隨著問題規模的擴大，完備算法的計算開銷會呈指數級增長，所以并不適用于解決實際問題。與完備算法不同，非完備算法在保證全局最優的前提下，更加注重求解效率，即在有限資源的條件下盡可能以較低的計算開銷找到最終的賦值組合［8］。因此，非完備算法的研究方向一直是DCOP領域的研究熱點。具體來說，非完備算法的研究方向主要分為基于推理的算法、基于采樣的算法、局部搜索算法和基于種群的算法四個方向。

基于推理的算法包括max-sum［9］、bouned max-sum［10］、max-sum_ADVP［11］ 和damped max-sum［12］。max-sum通過在因子圖中傳遞消息，不斷累積效用以尋找最優分配。bouned max-sum消除了對智能體構造無環圖傳遞消息影響最小的約束，并引入了近似比來提高解的質量。max-sum_ADVP發送選值并消除無效值，以解決重復效用問題。damped max-sum通過構建等效的分裂約束因子圖來描述智能體之間約束的不對稱性，以平衡探索和開發。

基于采樣的算法包括DUCT［13］、D-Gibbs［14］、SD-Gibbs［15］和PD-Gibbs［15］。DUCT是一種采用抽樣和置信界限來求解的DCOP算法。D-Gibbs將DCOP轉換為馬爾可夫隨機場中的最大似然估計問題。SD-Gibbs和PD-Gibbs可以在線性空間內解決大內存限制問題。

局部搜索算法憑借高靈活性、高效率和高容錯等優點，成為最受關注的非完備算法。局部搜索算法主要包括DSA［16］、MGM［17］、MGM-2［18］、MGM-3［17，18］、DSAN［19］和GDBA［20］。DSA是一種不需要通信結構的算法。它主要通過尋找一個最大程度降低局部代價的新值，并以一定概率替換原值來實現目標優化。MGM專注于調整產生最大局部收益的智能體的值。DSAN通過在退火算法中引入動態概率的思想，尋求一種跳出局部最優解的機制。MGM-2和MGM-3可以根據k-optimal思想［21，22］找到最優分配，但仍然面臨著一個巨大的挑戰，即時間復雜度隨著k的增加而急劇增加。GDBA是基于DSA的變體DBA［16］的改進算法，提出了有效成本、約束違反和修改矩陣范圍等方法實現更高的性能。局部搜索算法因其邏輯簡單、高靈活性和高有效性而成為最流行的算法，但是它們無法保證找到全局最優解。因此，研究者們提出了k-optimal、t-distance和anytime［23］等改進機制來提高算法的優化質量和魯棒性。此外，PDS［24］提出了局部決策框架，打破了傳統鄰居分配的依賴性，通過局部決策機制提高了解的質量。

近年來，基于種群的算法在DCOP求解中表現出優異的性能。ACO_DCOP［25］通過結合信息素和啟發式信息進行決策，將傳統的蟻群優化擴展到DCOP的求解中，其中信息素和啟發式信息分別為全局代價和局部代價。LSGA［26］是一種基于遺傳算法的框架，使用全賦值作為染色體進行編碼。VLSs［27］根據分配對應的概率進行抽樣，并設計方差調整機制設置初始解，在多個并行解中交替執行貪婪選擇。HLC［28］利用局部代價歷史記錄求解ADCOP。LPOS［29］通過自身的取值并行地搜索局部所有鄰居取值來進一步擴大對解空間的搜索。RDMAD［30］通過多種群分工配合分級更新策略更好地平衡算法的探索和開發能力。LIEAD［31］引入局部信息熵和重啟機制，幫助智能體自適應選擇信息素更新策略和值選擇策略，從而打破信息素的積累狀態。LCS［32］結合了指數加權移動平均法和群體優化技術，利用智能體的歷史值潛力，進一步提高局部搜索算法的探索能力。

然而，無論哪種非完備算法，陷入局部最優問題都是一個不可避免的問題。因此，如何設計相應的策略，盡可能避免算法陷入局部最優，是一個非常值得研究的課題和挑戰。為了盡可能擴大對解空間搜索的范圍，提出了一系列用于求解DCOP的基于鄰居忽略策略的局部搜索算法，以尋找算法跳出局部最優的路徑。隨機鄰居忽略策略通過減少智能體間的約束來進一步擴大對解空間搜索的范圍，即使這樣會增加噪聲，但也為算法尋找最優解提供了更多的機會。

本文算法在智能家居任務調度［33］、市場貿易［34］等領域均具有應用價值。在此，以智能家居任務調度為例展開闡釋，如圖1所示。在智能家居的場景下，將社區中的每個家庭視為一個智能體，智能家居設備傳感器則被當作變量，這些變量能夠反映智能家居系統的各種狀態信息。同時，設定智能家居運行過程中所產生的成本為約束代價，這里的成本涵蓋了多個方面，比如能源消耗成本、設備損耗成本等。基于現實中智能家居設備的實際環境狀況，構建約束圖以及與之相對應的DCOP模型，即可用本文算法進行求解。最終求解得到的結果是各個家居設備消耗能量的最小值集合。這個集合對于智能家居的能源管理具有重要意義，它能夠為家庭提供最優的設備使用策略，從而實現節能的目的，降低智能家居系統的運行成本。

本文的貢獻可總結如下：a）提出了一系列鄰居忽略策略，以減少智能體之間的約束條件，從而擴大算法對解空間搜索的范圍，增強算法的探索能力；b）從迭代優化的角度，理論證明了隨機鄰居忽略策略不會影響原始DCOP的約束關系；c）為解決大規模、高密度的DCOP提供了一種新思路，即通過忽略部分鄰居來降低問題的密度，從而通過解決密度較低的問題來處理復雜的高密度問題。

1 背景與相關工作

1.1 分布式約束優化問題

一個DCOP可以定義為一個四元組〈A、X、D、F〉，其中：A={a1，a2，…，an}是智能體的集合，其中智能體ai控制一個或多個離散變量；X={x1，x2，…，xm}是離散變量的集合，其中每個變量xj都分配給一個智能體；D={D1，D2，…，Dm}是離散變量的有限值域集合，其中X中各變量的值分別取自離散域D1，D2，…，Dm；F={f1，f2，…，fq}是約束關系函數的集合，約束fi∈F：Di1×…×Dik→R指定分配給每一組變量的集合的約束代價。

圖2展示了一個DCOP的實例。其中，圖2（a）是6個變量的約束圖，每條邊代表著約束代價函數。圖2（b）為各約束代價函數的約束矩陣。為了便于理解，假設一個智能體控制一個變量。因此，本文將智能體ai和變量xi視為同一概念。

一個DCOP的解是對所有變量的賦值組合X，X使所有智能體之間產生的所有約束代價函數之和最小化，如式（1）所示。

X*=arg mindi∈Di，dj∈Dj∑fi，j∈Ffi，j（xi∈di，xj∈dj）

（1）

1.2 分布式種群

分布式種群是傳統種群的一種變體，它將所有智能體的全部賦值中的一組賦值視為一個個體，其中每個個體代表一個解，所有智能體屬于一個分布式種群。分布式種群的優勢在于充分利用多個進程或節點來計算資源，加快進化算法的收斂速度，從而解決大規模問題。分布式種群是基于種群的DCOPs求解算法中常用的一種方法。如圖3所示，分布式種群中的任何個體都受所有智能體控制，每個智能體控制所有個體中特定維度的一個變量。

1.3 LCS

基于局部代價的模擬算法LCS是一種基于局部搜索的算法，它通過模擬歷史代價來優化局部代價，并在群體中不斷尋求最優解，從而解決優化問題。

如算法1所示，在初始化階段，所有個體模擬最壞情況下的初始代價值est0ck（di）并開啟循環。在初始輪中，每個個體從值域中隨機選擇一個初始值Vck，p并將其添加到取值集合Vi中。所有個體完成隨機選值后，智能體ai將Vi發送給其鄰居。當智能體ai接收到所有的鄰居值集合Vm時，根據式（3）計算所有個體的局部代價locck，p。隨后，根據式（4）更新局部模擬代價estrck（di）。為了加強種群交流，LCS設置交換輪次并根據式（5）更新局部模擬代價。最后，所有個體根據式（6）選取新值Vck，p，智能體ai將Vck，p加入Vi并發送給鄰居。

算法1 LCS算法（for智能體ai）

輸入：初始化參數C，P，α，β，γ，ecy。

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

a）初始化算法。

b）若收到鄰居智能體的信息Vm，進行下述步驟。

c）更新智能體的取值，并根據式（3）計算所有個體的局部代價locck，p。

d）根據式（4）更新當前輪次的局部模擬代價estrck（di）。

e）若該輪為交換輪次，根據式（5）進行種群交流，更新局部模擬代價。

f）根據式（6）進行下一輪選值Vck，p，智能體ai將Vck，p加入Vi并發送給鄰居。返回步驟b）進行下一輪。

本節以50輪為例來分析算法的收斂速度，如表4所示。根據表4可知，基于鄰居忽略策略的局部搜索算法在大多數情況下展現出更快的收斂速度。其中，LCS-SRNI僅忽略一個鄰居，其打破局部最優的能力break較弱，且噪聲干擾N相對較大，導致算法探索度Dexplore較小；而LCS-ENI、LCS-SRENI和LCS-MRNI由于忽略多個鄰居，使得算法跳出局部最優的概率增加，打破局部最優的能力break增大，相對噪聲干擾N也更強，其策略的算法探索度Dexplore比LCS-SRNI的算法探索度Dexplore大。

根據鄰居忽略策略，對各策略的收斂精度進行深入分析。針對單個鄰居隨機忽略策略，需要隨機忽略一個鄰居，則求解精度為1-1/E；針對極值鄰居忽略策略，需要忽略約束代價最大和最小的鄰居，則求解精度為1-2/E；針對混合鄰居忽略策略，由于單個隨機忽略的鄰居可能與約束代價最大和最小的鄰居重合，所以求解精度為［1-3/E，1-2/E］；針對多個鄰居隨機忽略策略，各約束邊被保留的概率為1-1/4r，則求解精度為1-1/4r。隨著智能體數量和輪次的增加，原始約束邊的集合E不斷擴大，則四種策略的求解精度隨之增加，得到的解越逼近問題的解。這是因為約束邊被保留的概率增加，算法在搜索解的過程中能夠更全面地考慮問題的約束條件，從而使得求解結果更接近原問題的最優解，提高了算法的精度。

4 復雜性分析

本章對基于鄰居忽略策略的局部搜索算法及其對比算法的復雜性進行了深入分析。由于部分對比算法較為久遠，本章選取了近年來較為典型的算法進行比較，包括LSGA、GDBA、ACO_DCOP、LIEAD、LCS。

對于空間復雜度，假設智能體鄰居總數為|A|=n且ai∈A。根據鄰居忽略策略，智能體只需保存每個種群的局部代價模擬值，每個種群的模擬值數量等于值域大小M，其空間復雜度為O（M），因此總的空間復雜度為種群數量與單個種群復雜度的乘積，即O（C×M）。根據參考文獻［20，25，26，31，32］，LSGA的最壞情況消息空間需求為O（2n×|Ni|），交叉消息空間為O（M）；GDBA的空間復雜度為O（|Ni|×|Di|×maxj∈Ni|Dj|）；ACO_DCOP空間復雜度包括值消息大小O（n×K），信息素消息大小O（（K+1）n+K）以及存儲信息素路徑空間為O（ω×|Di|×|Dj|）；LIEAD的空間復雜度主要由種群信息，信息素大小和存儲信息素軌跡構成，分別為O（n×m×K），O（n（mK+1）+mK），O（|Hi|×|Di|×|Dj|+2）；LCS需要O（|C|×|P|）。總體而言，基于鄰居忽略策略的局部搜索算法的空間復雜度與原始LCS算法相同，但較其他算法具有更低的空間開銷。

對于時間復雜度，基于鄰居忽略策略的局部搜索算法的時間復雜度主要為初始化模擬值、計算局部代價、更新模擬值種群交互和計算取值概率方面。在初始化模擬值階段，通過遍歷約束矩陣以找到最壞約束代價，其復雜度為O（N×M×M），其中N為鄰居數量。在計算局部代價時，查找約束表的復雜度為O（1）。然而，由于需要對所有個體進行查找，故總復雜度為O（C×P×N），其P為個體數量。在更新模擬值期間，復雜度為O（C×P×M），其中C是約束數量，M是種群大小。在種群交互階段，其復雜度為O（C×P）。在計算概率時，只需遍歷所有模擬值，因此復雜度為O（C×max（P×M）），其中P是個體數量，M是種群數量。就發送信息的大小而言，智能體需要發送值消息和局部代價消息，這兩者都與種群數量有關，故復雜度為O（C×P），其中C是約束數量，P是種群個體數量。關于信息數量方面，每輪迭代中智能體只需向其鄰居發送值消息和局部代價消息。對于隨機鄰居忽略策略的值消息，每次迭代發送值信息的復雜度為O（N-K），其中N為鄰居總數，K為忽略鄰居的數量。LSGA需要O（M×|Ni|）時間；GDBA的時間復雜度為O（|Ni|×|Di|）；ACO_DCOP的時間復雜度為O（K|Hi|×|Di|）；LIEAD的時間復雜度主要分為局部最優階段和更新局部信息熵階段，分別為O（K|Hi|×|Di|+1）和O（|Hi|×|Di|×|Dj|）；LCS的時間復雜度為O（n）。因此，基于鄰居忽略策略的局部搜索算法時間復雜度與原始LCS算法相同，但相較于其他算法具備更低的計算開銷和更高的效率。這說明基于鄰居忽略策略的局部搜索算法在保持良好性能的同時，能夠顯著降低計算資源的消耗，展現出較優的時間效率優勢。

5 實驗結果分析

本章通過實驗分析算法LCS-SRNI、LCS-ENI、LCS-SRENI和LCS-MRNI的性能。LCS-SRNI、LCS-ENI、LCS-SRENI和LCS-MRNI分別表示基于單個鄰居隨機忽略策略、極值鄰居忽略策略、混合鄰居忽略策略以及多個鄰居隨機忽略策略的LCS算法。基于鄰居忽略策略的局部搜索算法與最先進的局部搜索算法及種群算法，即LSGA、DSA（type C且p=0.6）、MGM、GDBA、PDS-DSA、Max-sum-ADVP、MaxsumDamping、LCS和ACO_DCOP（稀疏K=13，密集K=19）進行比較。實驗基準問題包括隨機DCOP、無尺度網絡和加權圖著色問題。此外，鑒于非完備算法的隨機性，所有問題算法都獨立執行30輪，并對實驗結果進行統計分析，平均值作為實驗結果。最大迭代次數設置為660。基準問題的具體配置如表5所示。

根據參考文獻［32］，LCS的參數分別設置為：C=4，P=24，β={0.9，0.8，0.7，0.6}，γ=0.7，α取值如表6所示。

為了深入了解各算法的收斂過程，圖4～9展示了算法在不同基準問題的收斂曲線。根據2.3節，鄰居忽略策略的概率呈遞增趨勢，這意味著跳出局部最優的概率在不斷增加。實驗結果顯示，求解質量依次為LCS-SRNI gt; LCS-ENI gt; LCS-SRENI gt; LCS-MRNI。LCS-SRNI忽略概率較低，適合小范圍調整；LCS-ENI忽略代價最大和最小的鄰居，提升全局優化的可能性；LCS-SRENI結合了隨機與極值忽略，兼顧靈活性和針對性；而LCS-MRNI通過大規模擾動顯著增加了全局搜索的機會，從而更有助于復雜問題的優化。

圖4、5展示了各個算法在求解70個智能體的稀疏和稠密隨機DCOP上的收斂曲線。在稀疏隨機DCOP上，相較于LCS，LCS-SRNI、LCS-ENI、LCS-SRENI和LCS-MRNI的性能分別提升了約17.1%、29.4%、40.7%和58.8%；LCS-MRNI 相較于其他算法提升了59.7%～68.6%。這表明引入不同的改進機制顯著增強了LCS的性能，特別是由于LCS-SRENI和LCS-MRNI忽略鄰居概率相對較高，優化效果最為顯著。從各算法的收斂曲線可以看出，MGM和DSA算法因缺乏全局信息，全局優化能力欠佳。盡管在DSA算法中引入了PDS框架提升了局部搜索能力，但整體性能提升幅度有限。相比之下，ACO_DCOP、LIEAD、LCS等算法通過種群協作機制提升了尋優能力。然而，基于鄰居忽略策略的局部搜索算法借助鄰居忽略策略在收斂速度和解質量方面表現更為突出，其優化過程中的效率明顯優于其他算法，展示了更強的全局搜索和收斂能力。在稠密問題中，由于測試問題密度的增加，智能體之間的約束變得更加復雜，鄰居忽略策略作用有限，相較于稀疏問題，本文算法尋優性能提升幅度較弱，其解質量相較于原始LCS分別提高了2.8%、5.1%、7.6%和53.4%。同時，與其他算法相比，LCS-MRNI性能提升幅度在53.7%～57.1%，進一步證明了該算法在應對高密度約束問題時，具備更強的全局優化能力和更優的解質量。通過這些改進，基于鄰居忽略策略的局部搜索算法在復雜問題情境下仍能保持穩健的性能。

在求解120個智能體的稀疏問題中，四種改進算法相較于原始LCS的性能提升顯著，分別約為9.5%、16.8%、24.3%和54.9%。相比于其他算法，忽略鄰居概率較高的LCS-MRNI性能提升幅度在55.2%～62.2%，在處理稀疏問題時存在明顯優勢。這表明，本文算法能夠更有效地利用稀疏問題的特性，顯著增強了優化能力。在求解120個智能體的稠密問題中，四種改進算法相較于原始LCS的性能提升分別為1.5%、2.9%、4.3%和51.9%。相較于其他算法，LCS-MRNI提升幅度在52.1%～55.1%。總體來看，四種本文算法在稀疏問題中表現出色，能夠有效提升優化性能，而在稠密問題中，因其忽略鄰居策略作用不明顯，提升幅度較小，但本文算法仍能提供一定的性能優勢，特別是LCS-MRN表現突出。這表明，這些算法在不同稠密問題下依然能發揮其獨特的優勢。

圖6、7展示了各個算法在求解150個智能體的稀疏和稠密無尺度網絡問題上的收斂曲線。在稀疏問題中，四種基于LCS的改進算法相較于原始LCS的性能分別提升了19.7%、33.0%、44.5%和56.5%。其中，LCS-MRNI相比其他算法提高了57%～67.1%。在稠密問題中，改進算法的提升幅度分別為6.1%、11.2%、16.3%和53.5%，而LCS-MRNI的提升幅度在53.3%～59.7%。本文算法在處理無尺度網絡問題時表現優越，證明了鄰居忽略策略在結構化問題求解中的有效性和顯著性能提升。

圖8、9比較了算法在求解120個智能體的加權圖著色問題時的收斂曲線。相較于原始LCS算法，本文算法性能提升分別為28.3%、38.2%、55.1%和76.5%。特別地，LCS-MRNI的性能提升幅度在84.1%～97.8%，顯著優于其他算法。實驗結果表明，基于鄰居忽略策略的局部搜索算法的性能優于其他對比算法。但值得注意的是，各個算法之間的性能差距并不明顯，這是因為與其他基準問題相比，加權圖著色問題是約束滿足問題，相較于其他約束優化問題更為簡單，求解難度較低。

表7詳細地展示了所有對比實驗結果。實驗具體數據也表明，LCS-MRNI在所有基準問題均表現出最佳的性能，其次是LCS-SRENI、LCS-ENI、LCS-SRNI。

6 結束語

為了盡可能避免算法陷入局部最優解，本文提出了一系列用于求解DCOP的基于鄰居忽略策略的局部搜索算法，包括LCS-SRNI、LCS-ENI、LCS-SRENI和LCS-MRNI。這些算法通過擴大對解空間的搜索范圍找到更好的解決方案，從而引導算法跳出局部最優解。在理論上證明了，從迭代優化的角度來看，隨機鄰居忽略策略對智能體之間的約束關系沒有影響。此外，大量的實驗結果表明，鄰居忽略策略可以通過減少智能體之間的約束，進一步擴大算法對解空間的搜索，即使這會在一定程度上增加噪聲，但也為算法尋找更優解提供了更多的機會。因此，基于鄰居忽略策略的局部搜索算法可以極大地提升算法的全局探索能力，為求解大規模高密度DCOP提供了一種新穎的思路。未來，將深入探究低密度問題的解決方法，并將其應用于復雜的高密度問題的處理。

參考文獻：

［1］Cerquides J，Farinelli A，Meseguer P，et al.A tutorial on optimization for multi-agent systems［J］.The Computer Journal，2014，57（6）：799-824.

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

［3］Fioretto F，Pontelli E，Yeoh W.Distributed constraint optimization problems and applications：a survey［J］.Journal of Artificial Intelligence Research，2018，61：623-698.

［4］Sato D M V，Borges A P，Peter M，et al.I-DCOP：train classification based on an iterative process using distributed constraint optimization［J］.Procedia Computer Science，2015，51：2297-2306.

［5］Zivan R，Parash T，Cohen-Lavi L，et al.Applying max-sum to asymmetric distributed constraint optimization problems［J］.Autonomous Agents and Multi-Agent Systems，2020，34（1）：13.

［6］Sultanik E A，Modi P J，Regli W C，et al.On modeling multiagent task scheduling as a distributed constraint optimization problem［C］//Proc of the 20th International Joint Conference on Artificial Intelligence.New York：ACM Press，2007：1531-1536.

［7］Acevedo J J，Arrue B C，Maza I，et al.Cooperative large area surveillance with a team of aerial mobile robots for long endurance missions［J］.Journal of Intelligent amp; Robotic Systems，2013，70（1）：329-345.

［8］Vinyals M，Juan A.Rodríguez et al.Generalizing DPOP：action-GDL，a new complete algorithm for DCOPs［C］//Proc of the 8th International Conference on Autonomous Agents amp; Multiagent Systems.［S.l.］：International Foundation for Autonomous Agents and Multiagent Systems，2009：1239-1240.

［9］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 Joint Conference on Autonomous Agents and Multiagent Systems.New York：ACM Press，2008：639-646.

［10］Rogers A，Farinelli A，Stranders R，et al.Bounded approximate decentralised coordination via the max-sum algorithm［J］.Artificial Intelligence，2011，175（2）：730-759.

［11］Zivan R，Peled H，Zivan R，et al.Max/Min-sum distributed constraint optimization through value propagation on an alternating DAG［C］//Proc of the 11th International Conference on Autonomous Agents and Multiagent Systems.New York：ACM Press，2012：265-272.

［12］Cohen L，Zivan R.Max-sum revisited：the real power of damping［C］//Autonomous Agents and Multiagent Systems.Cham：Springer International Publishing，2017：111-124.

［13］Ottens B，Dimitrakakis C，Faltings B.DUCT：an upper confidence bound approach to distributed constraint optimisation problems［J］.ACM Trans on Intelligent Systems，2017，8（5）：1-69.27.

［14］Nguyen D T，Yeoh W，Lau H C.Distributed Gibbs：a memory-bounded sampling-based DCOP algorithm［C］//Proc of the 12th International Conference on Autonomous Agents and Multiagent Systems.［S.l.］：International Foundation for Autonomous Agents and Multiagent Systems，2013：167-174.

［15］Nguyen D T，Yeoh W，Lau H C，et al.Distributed Gibbs：a linear-space sampling-based DCOP algorithm［J］.Journal of Artificial Intelligence Research，2019，64：705-748.

［16］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.

［17］Maheswaran R T，Pearce J P，Tambe M.Distributed algorithms for DCOP：a graphical-game-based approach［C］//Proc of the 17th ISCA International Conference on Parallel and Distributed Computing Systems.2004：432-439.

［18］Maheswaran R T，Pearce J P，Tambe M.A family of graphical-game-based algorithms for distributed constraint optimization problems［M］//Scerri P，Vincent R，Mailler R.Coordination of Large-Scale Multiagent Systems.New York：Springer-Verlag，2006：127-146.

［19］Arshad M，Silaghi M C.Distributed simulated annealing［EB/OL］.（2014）.https：//cs.fit.edu/～msilaghi/pages/papers/IOSDSA.pdf.

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

［21］Pearce J P，Tambe M，Pearce J P，et al.Quality guarantees on k-optimal solutions for distributed constraint optimization problems［C］//Proc of the 20th International Joint Conference on Artifical Intelligence.New York：ACM Press，2007：1446-1451.

［22］Bowring E，Pearce J，Portway C D，et al.On k-optimal distributed constraint optimization algorithms：new bounds and algorithms［C］//Proc of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems.2008：607-614.

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

［24］Yu Zhepeng，Chen Ziyu，He Jingyuan，et al.A partial decision scheme for local search algorithms for distributed constraint optimization problems［C］//Proc of the 16th Conference on Autonomous Agents and Multiagent Systems.New York：ACM Press，2017：187-194.

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

［26］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 and Multi-Agent Systems，2020，34（2）：article No.41.

［27］Li Fukui，He Jingyuan，Zhou Mingliang，et al.VLSs：a local search algorithm for distributed constraint optimization problems［J］.International Journal of Pattern Recognition and Artificial Intelligence，2022，36（3）：2259006.

［28］石美鳳，吳俊，陳媛.一種歷史局部代價求解ADCOPs的算法［J］.重慶理工大學學報：自然科學，2022，36（9）：156-163.（Shi Mei-feng，Wu Jun，Chen Yuan.Historical local cost based algorithm to solve ADCOPs［J］.Journal of Chongqing University of Technology Natural Science，2022，36（9）：156-163.）

［29］石美鳳，楊海，陳媛，等.基于局部并行搜索的分布式約束優化算法框架［J］.計算機應用研究，2022，39（8）：2376-2380.（Shi Mei-feng，Yang Hai，Chen Yuan，et al.Local parallel search framework for distributed constraint optimization problems［J］.Application Research of Computers，2022，39（8）：2376-2380.）

［30］石美鳳，肖詩川，馮欣.基于多種群的隨機擾動蟻群算法求解分布式約束優化問題［J］.計算機應用研究，2022，39（9）：2683-2688.（Shi Meifeng，Xiao Shichuan，Feng Xin.Random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems［J］.Application Research of Computers，2022，39（9）：2683-2688.）

［31］Shi Meifeng，Xiao Shichuan，Feng Xin.An adaptive ant colony algorithm based on local information entropy to solve distributed constraint optimization problems［J］.International Journal of Pattern Recognition and Artificial Intelligence，2023，37（9）：2359013.

［32］Shi Meifeng，Liang Feipeng，Chen Yuan，et al.A local cost simulation-based algorithm to solve distributed constraint optimization problems［J］.PeerJ Computer Science，2023，9：e1296.

［33］Fioretto F，Yeoh W，Pontelli E，et al.A multiagent system approach to scheduling devices in smart homes［C］//Proc of the 16th Conference on Autonomous Agents and MultiAgent Systems.New York：ACM Press，2017：981-989.

［34］Cerquides J，Picard G，Rodríguez-Aguilar J A，et al.Designing a market place for the trading and distribution of energy in the smart grid［C］//Proc of International Conference on Autonomous Agents and Multiagent Systems.New York：ACM Press，2015：1285-1293.