求解分布式約束優(yōu)化問(wèn)題的鄰居忽略策略局部搜索算法

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

關(guān)鍵詞：分布式約束優(yōu)化問(wèn)題；鄰居忽略；解空間擴(kuò)大搜索；局部搜索算法

中圖分類(lèi)號(hào)：TP18"" 文獻(xiàn)標(biāo)志碼：A"" 文章編號(hào)：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 引言

多智能體系統(tǒng)（multi-agent system，MAS）［1］是由多個(gè)獨(dú)立智能體組成的系統(tǒng)，這些智能體可以相互交互、協(xié)作和競(jìng)爭(zhēng)，以實(shí)現(xiàn)共同目標(biāo)或解決復(fù)雜問(wèn)題。分布式約束優(yōu)化問(wèn)題（DCOP）［2］是多智能體系統(tǒng)的基本模型，已成功應(yīng)用于任務(wù)調(diào)度、移動(dòng)傳感器協(xié)調(diào)、合作搜索等實(shí)際問(wèn)題［3～8］。

學(xué)者們提出了許多求解DCOP的算法，根據(jù)其求解目標(biāo)可以分為完備算法和非完備算法。由于DCOP是NP-hard［2］問(wèn)題，隨著問(wèn)題規(guī)模的擴(kuò)大，完備算法的計(jì)算開(kāi)銷(xiāo)會(huì)呈指數(shù)級(jí)增長(zhǎng)，所以并不適用于解決實(shí)際問(wèn)題。與完備算法不同，非完備算法在保證全局最優(yōu)的前提下，更加注重求解效率，即在有限資源的條件下盡可能以較低的計(jì)算開(kāi)銷(xiāo)找到最終的賦值組合［8］。因此，非完備算法的研究方向一直是DCOP領(lǐng)域的研究熱點(diǎn)。具體來(lái)說(shuō)，非完備算法的研究方向主要分為基于推理的算法、基于采樣的算法、局部搜索算法和基于種群的算法四個(gè)方向。

基于推理的算法包括max-sum［9］、bouned max-sum［10］、max-sum_ADVP［11］ 和damped max-sum［12］。max-sum通過(guò)在因子圖中傳遞消息，不斷累積效用以尋找最優(yōu)分配。bouned max-sum消除了對(duì)智能體構(gòu)造無(wú)環(huán)圖傳遞消息影響最小的約束，并引入了近似比來(lái)提高解的質(zhì)量。max-sum_ADVP發(fā)送選值并消除無(wú)效值，以解決重復(fù)效用問(wèn)題。damped max-sum通過(guò)構(gòu)建等效的分裂約束因子圖來(lái)描述智能體之間約束的不對(duì)稱(chēng)性，以平衡探索和開(kāi)發(fā)。

基于采樣的算法包括DUCT［13］、D-Gibbs［14］、SD-Gibbs［15］和PD-Gibbs［15］。DUCT是一種采用抽樣和置信界限來(lái)求解的DCOP算法。D-Gibbs將DCOP轉(zhuǎn)換為馬爾可夫隨機(jī)場(chǎng)中的最大似然估計(jì)問(wèn)題。SD-Gibbs和PD-Gibbs可以在線(xiàn)性空間內(nèi)解決大內(nèi)存限制問(wèn)題。

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

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

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

本文算法在智能家居任務(wù)調(diào)度［33］、市場(chǎng)貿(mào)易［34］等領(lǐng)域均具有應(yīng)用價(jià)值。在此，以智能家居任務(wù)調(diào)度為例展開(kāi)闡釋?zhuān)鐖D1所示。在智能家居的場(chǎng)景下，將社區(qū)中的每個(gè)家庭視為一個(gè)智能體，智能家居設(shè)備傳感器則被當(dāng)作變量，這些變量能夠反映智能家居系統(tǒng)的各種狀態(tài)信息。同時(shí)，設(shè)定智能家居運(yùn)行過(guò)程中所產(chǎn)生的成本為約束代價(jià)，這里的成本涵蓋了多個(gè)方面，比如能源消耗成本、設(shè)備損耗成本等?；诂F(xiàn)實(shí)中智能家居設(shè)備的實(shí)際環(huán)境狀況，構(gòu)建約束圖以及與之相對(duì)應(yīng)的DCOP模型，即可用本文算法進(jìn)行求解。最終求解得到的結(jié)果是各個(gè)家居設(shè)備消耗能量的最小值集合。這個(gè)集合對(duì)于智能家居的能源管理具有重要意義，它能夠?yàn)榧彝ヌ峁┳顑?yōu)的設(shè)備使用策略，從而實(shí)現(xiàn)節(jié)能的目的，降低智能家居系統(tǒng)的運(yùn)行成本。

本文的貢獻(xiàn)可總結(jié)如下：a）提出了一系列鄰居忽略策略，以減少智能體之間的約束條件，從而擴(kuò)大算法對(duì)解空間搜索的范圍，增強(qiáng)算法的探索能力；b）從迭代優(yōu)化的角度，理論證明了隨機(jī)鄰居忽略策略不會(huì)影響原始DCOP的約束關(guān)系；c）為解決大規(guī)模、高密度的DCOP提供了一種新思路，即通過(guò)忽略部分鄰居來(lái)降低問(wèn)題的密度，從而通過(guò)解決密度較低的問(wèn)題來(lái)處理復(fù)雜的高密度問(wèn)題。

1 背景與相關(guān)工作

1.1 分布式約束優(yōu)化問(wèn)題

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

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

一個(gè)DCOP的解是對(duì)所有變量的賦值組合X，X使所有智能體之間產(chǎn)生的所有約束代價(jià)函數(shù)之和最小化，如式（1）所示。

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

（1）

1.2 分布式種群

分布式種群是傳統(tǒng)種群的一種變體，它將所有智能體的全部賦值中的一組賦值視為一個(gè)個(gè)體，其中每個(gè)個(gè)體代表一個(gè)解，所有智能體屬于一個(gè)分布式種群。分布式種群的優(yōu)勢(shì)在于充分利用多個(gè)進(jìn)程或節(jié)點(diǎn)來(lái)計(jì)算資源，加快進(jìn)化算法的收斂速度，從而解決大規(guī)模問(wèn)題。分布式種群是基于種群的DCOPs求解算法中常用的一種方法。如圖3所示，分布式種群中的任何個(gè)體都受所有智能體控制，每個(gè)智能體控制所有個(gè)體中特定維度的一個(gè)變量。

1.3 LCS

基于局部代價(jià)的模擬算法LCS是一種基于局部搜索的算法，它通過(guò)模擬歷史代價(jià)來(lái)優(yōu)化局部代價(jià)，并在群體中不斷尋求最優(yōu)解，從而解決優(yōu)化問(wèn)題。

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

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

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

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

a）初始化算法。

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

c）更新智能體的取值，并根據(jù)式（3）計(jì)算所有個(gè)體的局部代價(jià)locck，p。

d）根據(jù)式（4）更新當(dāng)前輪次的局部模擬代價(jià)estrck（di）。

e）若該輪為交換輪次，根據(jù)式（5）進(jìn)行種群交流，更新局部模擬代價(jià)。

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

本節(jié)以50輪為例來(lái)分析算法的收斂速度，如表4所示。根據(jù)表4可知，基于鄰居忽略策略的局部搜索算法在大多數(shù)情況下展現(xiàn)出更快的收斂速度。其中，LCS-SRNI僅忽略一個(gè)鄰居，其打破局部最優(yōu)的能力break較弱，且噪聲干擾N相對(duì)較大，導(dǎo)致算法探索度Dexplore較小；而LCS-ENI、LCS-SRENI和LCS-MRNI由于忽略多個(gè)鄰居，使得算法跳出局部最優(yōu)的概率增加，打破局部最優(yōu)的能力break增大，相對(duì)噪聲干擾N也更強(qiáng)，其策略的算法探索度Dexplore比LCS-SRNI的算法探索度Dexplore大。

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

4 復(fù)雜性分析

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

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

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

5 實(shí)驗(yàn)結(jié)果分析

本章通過(guò)實(shí)驗(yàn)分析算法LCS-SRNI、LCS-ENI、LCS-SRENI和LCS-MRNI的性能。LCS-SRNI、LCS-ENI、LCS-SRENI和LCS-MRNI分別表示基于單個(gè)鄰居隨機(jī)忽略策略、極值鄰居忽略策略、混合鄰居忽略策略以及多個(gè)鄰居隨機(jī)忽略策略的LCS算法?；卩従雍雎圆呗缘木植克阉魉惴ㄅc最先進(jìn)的局部搜索算法及種群算法，即LSGA、DSA（type C且p=0.6）、MGM、GDBA、PDS-DSA、Max-sum-ADVP、MaxsumDamping、LCS和ACO_DCOP（稀疏K=13，密集K=19）進(jìn)行比較。實(shí)驗(yàn)基準(zhǔn)問(wèn)題包括隨機(jī)DCOP、無(wú)尺度網(wǎng)絡(luò)和加權(quán)圖著色問(wèn)題。此外，鑒于非完備算法的隨機(jī)性，所有問(wèn)題算法都獨(dú)立執(zhí)行30輪，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析，平均值作為實(shí)驗(yàn)結(jié)果。最大迭代次數(shù)設(shè)置為660?；鶞?zhǔn)問(wèn)題的具體配置如表5所示。

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

為了深入了解各算法的收斂過(guò)程，圖4～9展示了算法在不同基準(zhǔn)問(wèn)題的收斂曲線(xiàn)。根據(jù)2.3節(jié)，鄰居忽略策略的概率呈遞增趨勢(shì)，這意味著跳出局部最優(yōu)的概率在不斷增加。實(shí)驗(yàn)結(jié)果顯示，求解質(zhì)量依次為L(zhǎng)CS-SRNI gt; LCS-ENI gt; LCS-SRENI gt; LCS-MRNI。LCS-SRNI忽略概率較低，適合小范圍調(diào)整；LCS-ENI忽略代價(jià)最大和最小的鄰居，提升全局優(yōu)化的可能性；LCS-SRENI結(jié)合了隨機(jī)與極值忽略，兼顧靈活性和針對(duì)性；而LCS-MRNI通過(guò)大規(guī)模擾動(dòng)顯著增加了全局搜索的機(jī)會(huì)，從而更有助于復(fù)雜問(wèn)題的優(yōu)化。

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

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

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

圖8、9比較了算法在求解120個(gè)智能體的加權(quán)圖著色問(wèn)題時(shí)的收斂曲線(xiàn)。相較于原始LCS算法，本文算法性能提升分別為28.3%、38.2%、55.1%和76.5%。特別地，LCS-MRNI的性能提升幅度在84.1%～97.8%，顯著優(yōu)于其他算法。實(shí)驗(yàn)結(jié)果表明，基于鄰居忽略策略的局部搜索算法的性能優(yōu)于其他對(duì)比算法。但值得注意的是，各個(gè)算法之間的性能差距并不明顯，這是因?yàn)榕c其他基準(zhǔn)問(wèn)題相比，加權(quán)圖著色問(wèn)題是約束滿(mǎn)足問(wèn)題，相較于其他約束優(yōu)化問(wèn)題更為簡(jiǎn)單，求解難度較低。

表7詳細(xì)地展示了所有對(duì)比實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)具體數(shù)據(jù)也表明，LCS-MRNI在所有基準(zhǔn)問(wèn)題均表現(xiàn)出最佳的性能，其次是LCS-SRENI、LCS-ENI、LCS-SRNI。

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［1］Cerquides J，F(xiàn)arinelli 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，F(xiàn)arinelli 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，F(xiàn)altings 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］石美鳳，吳俊，陳媛.一種歷史局部代價(jià)求解ADCOPs的算法［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)，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］石美鳳，楊海，陳媛，等.基于局部并行搜索的分布式約束優(yōu)化算法框架［J］.計(jì)算機(jī)應(yīng)用研究，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］石美鳳，肖詩(shī)川，馮欣.基于多種群的隨機(jī)擾動(dòng)蟻群算法求解分布式約束優(yōu)化問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（9）：2683-2688.（Shi Meifeng，Xiao Shichuan，F(xiàn)eng 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，F(xiàn)eng 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.