基于局部并行搜索的分布式約束優化算法框架

摘要：針對當前局部搜索算法在求解大規模、高密度的分布式約束優化問題（DCOP）時，求解困難且難以跳出局部最優取得進一步優化等問題，提出一種基于局部并行搜索的分布式約束優化算法框架（LPOS），算法中agent通過自身的取值并行地搜索局部所有鄰居取值來進一步擴大對解空間的搜索，從而避免算法過早陷入局部最優。為了保證算法的收斂性與穩定性，設計了一種自適應平衡因子K來平衡算法對解的開發和繼承能力，并在理論層面證明了并行搜索優化算法可以擴大對解空間的搜索，自適應平衡因子K可以實現平衡目的。綜合實驗結果表明，基于該算法框架的算法在求解低密度和高密度DCOP時性能都優于目前最新的算法。特別是在求解高密度DCOP中有顯著的提升。

關鍵詞：分布式約束優化問題； 多智能體系統； 局部搜索算法； 并行搜索優化

中圖分類號：TP13文獻標志碼：A

文章編號：1001-3695（2022）08-023-2376-05

doi：10.19734/j.issn.1001-3695.2022.02.0035

Local parallel search framework for distributed constraint optimization problems

Shi Meifeng， Yang Hai， Chen Yuan， Xiao Shichuan， Liao Xin， He Ying

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

Abstract：In order to solve the problem that it is difficult to get out of the local optimum to achieve further optimization in large-scale dense distributed constraint optimization problems（DCOP）， this paper proposed a local parallel search framework（LPOS） for solving algorithms of DCOP. In LPOS， the agent searched all the value assignments of its local neighbors in parallel according to its current value assignment to further expand the search of solution space， so as to avoid the algorithm falling into local optimum prematurely. In order to ensure the convergence of the algorithm， this paper designed an adaptive equilibrium factor K to balance the exploration and exploitation ability of the DCOP solving algorithms. At the theoretical analysis， it proved that the LPOS could expand the search of solution space and the K could achieve the balance. The experimental results demonstrate that the performance of the proposed LPOS is better than the-state-of-the-art algorithms in both low density and high density. Specifically， LPOS significantly superior to the competitors when solving high density DCOP.

Key words：distributed constrained optimization problem; multi-agent system; local search algorithm; local parallel optimization

0引言

隨著分布式協同運作的人工智能的出現，多智能體系統（MAS）［1］已經成為人工智能的一個重要分支，而分布式約束優化問題（distributed constraint optimization problems，DCOP）［2］作為智能體協同調度的一個重要框架，是解決分布式智能系統建模和目標之間協同優化的關鍵技術。DCOP強調通過局部智能體之間的信息交互以達到全局最優，且具有很強的容錯性以及很高的并行性，適用于求解規模大、難度高的組合問題，以分布并行計算的方式快速有效地解決這些問題。目前DCOP在任務調度［3］、傳感器網絡［4，5］、微電網優化控制等領域得到了廣泛的應用。然而，由于DCOP是NP難問題［6，7］，隨著問題規模和復雜程度的增加，完備算法所產生的指數級通信和時間導致了其應用的局限性。而非完備算法則是通過放棄找到問題的最優解，通過較少的通信和時間成本來尋找次優解，如此便能很好地應用于大規模的分布式應用模型問題。因此，近幾年非完備算法備受青睞。

非完備算法通常包括基于局部搜索的算法［8～12］、基于推理的算法［13～18］和基于采樣的算法［19～22］三類。而局部搜索算法是DCOP中最流行的非完備算法，其每個agent都是根據局部約束條件和從所有相鄰agent接收到的信息進行優化的，如DSA［23］、DBA［24］和MGM［25］等。然而，局部搜索算法又具有容易陷入局部最優的缺點。近年來，Chen等人［26］提出一種基于遺傳算法（GA-based framework，LSGA）的框架，利用遺傳算子的能力改進局部搜索算法。但交叉算子在優化過程中破壞了交叉塊中agent與鄰居之間的協調性，使得agent只能依靠自身的局部信息（局部代價以及取值頻次）指標來衡量當前解的優劣，仍然不能避免算法陷入局部最優。Yu等人［27］提出了一種局部決策（partial decision scheme，PDS）的框架，該算法框架通過忽略其中一個鄰居來搜索有希望的決策分區，從而提高agent的局部利益。然而在大規模高密度的問題中，agent周圍會有大量鄰居，此時PDS起到的效果甚微，難以取得進一步的優化。

針對在大規模高密度配置下，分布式約束優化問題難以被進一步優化的問題，本文提出了一種基于局部并行搜索策略（locall parallel optimization search，LPOS）的分布式約束優化算法框架，該框架根據agent自身取值發送給周圍所有鄰居并行地同時，搜索自身值域以尋找到最小代價取值來進一步擴大算法對解空間的探索，從而提升算法解的質量。

1介紹

1.1分布式約束優化問題

分布式約束優化問題（distributed constraint optimization problems，DCOP）由一個四元組〈A，X，D，F〉表示。其中：

A={a1，a2，…，am}為agent的集合；x={x1，x2，…，xn}為變量的集合，并且變量由所屬agent進行賦值，每一個agent負責一個或多個變量的取值；D={d1，d2，…，dn}為一個有限值域的集合，Di為X集合中對應變量xi的取值值域；F={f1，f2，…，fk}為agent之間約束關系的集合，每一條約束對應著非負映射fi：Di1×…×Dik→R+，它包含了當前約束的所有變量組合以及其對應的代價。

DCOP 也可以用約束圖來直觀地表示。在約束圖中，每個變量由其對應的agent控制賦值，每個agent僅知道關于控制變量上的約束；各agent在賦值時必須相互協調，使全局目標（如約束函數之和）最優。DCOP可抽象描述為由節點和邊組成的約束圖，每個節點對應一個agent，邊表示節點之間存在約束關系，約束函數表示約束各變量的任意賦值組合的收益（代價）。

圖1表示了一個二元約束關系的DCOP約束圖，其中變量Xi∈{1，2}，每一個agent控制一個變量Xi；fij表示Xi和Xj之間的約束函數。

由于agent可以控制一個或者多個變量，為了便于理解與討論，本文假設每個agent只控制一個變量Xi，它僅知道與該變量相關的約束函數。在DCOP中，每個agent與鄰居共享約束函數，agent之間相互協調找到使四個約束函數之和最優的變量賦值，因此DCOP的解可以被定義為

σ=argdi∈Di mindj∈Dj ∑fij∈Ffij（xi=di，xj=dj）（1）

1.2DSA算法與MGM2算法

隨機搜索算法（DSA）的基本思想是按照一個預先設定的概率P來進行決策。首先，agent將控制變量進行隨機取值Xi，并且將取值發送給周圍所有鄰居，然后各個agent進行重復迭代。在每一次迭代中，agent 先搜集周圍鄰居發送的值，然后根據鄰居的取值搜索自身值域，并計算取值Xi時局部代價與取值Xj時局部代價差值Δ；若Δ≥0且隨機生成數小于P，則更新值并發送給周圍鄰居。通過DSA算法能夠很快找到次優解，但也極易陷入局部最優，導致求解質量不好。

MGM2算法是一種在策略上比較保守的算法，通過兩個agent組合成聯合體的方式進行決策，只有agent之間收益最大的agent才能改變自身取值，否則只能等待下一輪的決策。MGM2與 DSA 算法思想類似，agent 將控制變量進行隨機取值Xi，然后進行迭代。在每一次迭代中，agent 先搜集周圍鄰居發送的值，然后選取能夠讓agent局部代價降低Δi最多的值，并將Δi發送給周圍鄰居；若Δ＞Δi，則更新值并發送給周圍鄰居。MGM2算法雖能在一定程度上改善算法陷入局部最優的問題，但也造成了組合體之間太過關注自身代價而導致算法不能進一步找到更優的解。

1.3LSGA框架與PDS框架

基于遺傳算法的框架［26］（LSGA）利用遺傳算子（包括選擇算子、交叉算子和變異算子）的能力改進局部搜索算法。選擇算子由每個個體執行，根據一個適應度函數來評估其基因，并通過適應度函數去取決個體的局部效益和基因值的出現頻率。然而由于交叉算子破壞了交叉塊中agent與鄰居之間的協調性，導致agent只能通過自身局部信息進行評估當前解的質量，所以基于遺傳算法框架并不能避免算法陷入局部最優。

局部決策框架（PDS）［27］是當算法陷入局部最優時，通過agent忽略局部其中一個鄰居的策略以擴大搜索解空間，而進一步尋求更優的解。但當面對大規模、高密度的DCOP問題時，僅通過忽略局部一個鄰居的策略已難以取得進一步的優化。

本文針對當前局部搜索算法在求解大規模、高密度的DCOP問題中，難以進一步優化等問題，提出了一種基于局部并行搜索的分布式約束優化算法框架（LPOS）。

2局部并行搜索優化算法框架算法步驟及實例分析

2.1算法框架步驟

算法1局部并行搜索優化算法

a）隨機搜索算法初始化；

b）檢測agent處于局部最優狀態，并計算并行搜索優化概率POPi；

c）生成隨機數ai∈（0，1）；

d）若ailt;POPi，則進行并行搜索優化；

e）隨機選擇一個鄰居xb；

f）將xb取值發送給agent，并搜索自身值域選擇與xb之間代價最小值vi，然后發送給周圍所有鄰居；

g）計算agent局部代價增益gi；

h）若gigt;0，則更新為agent當前取值；

i）若gi≤0，則進一步計算決策優化消息V*m；

j）計算全局代價增益gc；

k）若gcgt;0，則更新為agent當前取值，否則重復進行步驟c）～j）。

根據步驟b），當檢測到處于局部最優狀態（ILB）［27］時，agent根據式（6）計算并行優化概率POPi進行局部并行搜索；并行優化概率POPi通過式（2）局部代價水平Li與當前迭代次數水平以及式（7）平衡因子K的乘積計算；當求得的代價較大時，局部代價水平會相對較大，且平衡因子K也會較大，迭代次數水平僅為控制進程收斂的線性不變函數，故最終的POPi會較大，使得當前agent有更大的概率改變自身的取值，探索求取更優的解，以此降低POPi的值來穩定解的質量。

Li=ci－cmincmax－cmin，cmax≠cmin（2）

ci=∑j∈neighbourIDcij（xi=ai，xj=aj）ai∈Di，aj∈Dj（3）

cmin=mina′i∈Di ∑j∈neighbourIDcijxi=a′ixj=arg mina′j∈Dj（xi=a′i，xj=a′j）（4）

cmax=maxa′i∈Di ∑j∈neighbourIDcijxi=a′ixj=arg maxa′j∈Dj（xi=a′i，xj=a′j）（5）

其中：ai和aj分別是xi和它的鄰居xj的當前值；cij是xi當前解的局部代價。式（4）與（5）中，cmin和cmax分別是xi的局部代價的最大值和最小值；a′i的初始值為原始算法處于ILB時的取值；neighbourID是xi周圍所有鄰居。由式（2）可知，Li越大，當前的局部代價越差。

POPi=Li×r_max-r_currentr_max×K（6）

K=（r_max-r_currentr_max）Li（7）

其中：r_current和r_max分別表示當前迭代次數和最大迭代次數。最大迭代次數被用做局部搜索的終止條件。由式（6）與（7）可知，xi的Li越大，局部并行搜索優化的概率越大，POPi的影響會隨著迭代次數的增加而逐漸減弱。

K是自適應平衡因子，平衡因子的作用是平衡優化過程中算法的探索和對當前期望解的開發能力。根據算法求解時的代價大小自適應地動態調整K值的大小。根據式（7）可知，隨著迭代次數的增加，K值總體趨勢逐漸減小，有利于算法收斂與穩定，而局部代價水平的大小使算法能夠自適應地調整算法對解的探索與開發能力。

根據步驟d），當xi處于ILB以及滿足POPi時，進行并行搜索優化。

根據步驟e），首先，xi隨機選擇它的一個鄰居。然后，xi分別通過式（8）～（10）計算新值a′i、a′j和最小局部代價c′min。a′i和a′j分別是xi和xj對應于c′min的值。

a′i=arg mini∈Di ∑j∈neighbourIDj≠bcij（xi=a′i，xj=a′j）（8）

a′j=arg minj∈neighbourIDx′i=a′icij（xi=a′i，xj=a′j）（9）

c′min=∑j∈neighbourIDj≠bcij（xi=a′i，xj=a′j）+cib（xi=a′i，xj=xb）（10）

gi=ci－c′min（11）

根據步驟g）～j），xi通過式（11）計算局部代價的增益gi，并通過決定是否將其當前值更改為a′i；如果gi不大于0，則進行計算決策信息V*m與全局代價增益gc，若gclt;o則意味著xi選擇鄰居xb進行局部并行搜索優化不能改善其狀態，xi將保持當前值，然后重復步驟c）～j）。

其中，決策信息V*m根據式（12）改變其值V*k，通過選擇鄰居xb之外的每個鄰居的值來搜索其解空間，從而找到鄰居xj，使xij的代價最小。然后，xi通過式（13）（14）計算xi的新值a′i和全局代價gc。

V*k=arg minj∈neighbourIDj≠b∑a′i∈Dicij（V*m=a′i，xj=a′j）+mina′j∈Djcij（V*m=a′i，xj=a′j）（12）

a′i=arg mina′i∈Dicij（xi=a′i，xj=a′j）（13）

gc=∑j∈neighbourIDi∈Dicij（xi=ai，xj=aj）-

［∑j∈neighbourIDj≠bcij（xi=a′i，xj=a′j）+cib（xi=a′i，xj=xb）］

（14）

2.2局部并行搜索算法框架實例

以圖1為例來說明本文所提策略的基本思想。假設所有的agent在多輪之后處于ILB狀態，且取值分配都為1，并在下一輪將它們的值1發送給它們的鄰居。

若此時進行局部決策PDS，當x1選擇鄰居x3進行忽略，以尋求打開解空間時，發現當x1=1與x3=1時已經是最小值了，已經無法跳出當前取值改變現狀。因此本文嘗試采用局部并行搜索策略（LPOS），以迭代次數800為終止條件［24］，將其鄰居，即neighbourID={x1，x2}進行局部并行搜索以達到進一步擴大對解空間的探索，從而尋找到更小的局部代價。也就是說，對于x3的局部而言，通過式（4）（5）分別計算出局部最大值cmax=4+4+5=13與最小值cmin=1+1+1=3，x1與x2同時收到取值x3=1，然后分別并行地搜索遍歷自身值域，尋找最小代價取值。對于圖1，通過式（3）計算代價，當x1=1時代價為1，當x1=2時代價為2，故此時選擇x1=1；同時，計算當x2=1時代價為2，當x2=2時代價為1，故此時選擇x2=2。一輪局部并行搜索完成，通過式（8）（9）計算可知最終局部取值為x1=1，x2=2，x3=1；代價cost=1+3+1=5，通過式（2）計算Li=（5－1）/（13－1）=0.333，通過式（7）計算K=［（800－1）/800］0.333=0.999 583，通過式（6）計算可知POPi=0.333×0.998 75×0.999 583=0.332 4，然后再通過式（10）計算x4=2時最終代價為5+1=6，根據式（11）計算可知當所有agent取值為1時，gi=4+1+2+2－6=3gt;0；根據算法步驟d）可知，若隨機生成數ai≥POPi=0.332 4。則將當前所有agent取值為1更改為x1=1，x2=2，x3=1，x4=2。使得算法能夠跳出當前局部最優，進行進一步優化。

3實驗分析

為了驗證LPOS算法框架的有效性與優越性，本文在隨機DCOP、圖著色問題以及無尺度網絡問題中與基于PDS框架的算法、基于LSGA框架的算法以及GDBA算法進行性能比較分析。考慮到DCOP非完備算法的隨機性，實驗設計將對每一種模式生成的問題進行30次獨立求解，并取30次統計結果進行對比。為了保證實驗的公平性，根據文獻［27］，對于所有的實驗都統一采用800次迭代次數作為終止條件，具體實驗配置［24，26，27］如表1所示。

為了方便對比LPOS_DSA、LPOS_MGM2和PDS_DSA、PDS_MGM2［27］以及LSGA_DSA、LSGA_MGM2［27］和GDBA［27］算法之間性能的差異，圖2～6給出了這七種算法在三類問題中的收斂曲線，表2、3分別為LPOS_DSA與LPOS_MGM2較其他算法在性能上的提升率。

從圖2與3可以看出，在隨機DCOP問題中，在低密度與高密度問題下，PDS_DSA與LSGA_DSA算法都以很快的速率下降并隨后收斂，導致算法不能夠找到更好的解，PDS_MGM2與LSGA_MGM2算法由于MGM2算法本身采取較為保守的策略進行求解導致在隨機DCOP問題中表現都比較差；而LPOS_DSA與LPOS_MGM2算法通過并行搜索優化的策略，并采用自適應平衡因子K在求解過程中進行平衡解的開發與繼承能力，使得LPOS_DSA與LPOS_MGM2算法都能夠以較緩的速率下降代價，充分尋求更優的解，以避免快速陷入局部最優。如表2、3所示，LPOS_DSA較PDS_DSA、LSGA_DSA和GDBA算法在低密度隨機DCOP問題中，在性能上分別有2.22%、1.34%和4.9%的提升，在高密度隨機DCOP問題中分別有1.34%、0.62%和1.17%的提升；而LPOS_MGM2較PDS_MGM2與LSGA_MGM2算法在低密度隨機DCOP問題中有24.55%與2.85%的提升，而在高密度隨機DCOP問題中有12.13%和4.18%的提升。

在無尺度網絡問題中（圖4、5），在低密度與高密度問題下，LSGA_DSA、LSGA-MGM2與GDBA算法都在迭代150次左右達到收斂，使得算法不能進一步尋找到更優的解，而PDS_DSA在低密度問題中根據其忽略周圍其中一個鄰居的策略使得算法不斷擴大搜索解空間，最終求得比較優秀的解，但對于高密度問題，此策略作用已經非常微小，也在迭代150次左右就已經收斂；而LPOS_DSA與LPOS_MGM2算法通過并行搜索優化策略，不斷進行解空間的探索，以較緩的速率進行收斂，有效地避免了快速陷入局部最優的問題。最終在表2、3中可以看出，LPOS_DSA較PDS_DSA、LSGA_DSA和GDBA算法，在低密度無尺度網絡問題中在性能上分別有2.22%、8.25%和8.25%的提升，在高密度無尺度網絡問題中分別有5.05%、4.25%和4.08%的提升；而LPOS_MGM2較PDS_MGM2與LSGA_MGM2算法，在低密度無尺度網絡問題中有2.22%與8.25%的提升，且在高密度無尺度網絡中有19.66%和7.68%的提升。

由于圖著色問題是最大約束滿足問題，其約束代價取值為0或者1，相比其他問題會簡單很多。如圖6所示，各算法都能夠快速收斂，而LPOS_DSA算法通過并行搜索優化策略在200次迭代后還能繼續尋找到明顯優于其他算法的解。在表2、3中可以看出，LPOS_DSA相較于PDS_DSA、LSGA_DSA和GDBA算法，在性能上分別有29.8%、24%和38.9%的提升；而LPOS_MGM2較PDS_MGM2與LSGA_MGM2算法，有2.24%與8.26%的提升。

4結束語

本文提出了一種基于局部并行搜索優化的分布式約束優化算法框架（LPOS）。該算法框架通過agent自身取值發送給周圍所有鄰居并行的同時，搜索自身值域來進一步擴大對解空間的搜索。此外，還設計了一種自適應的平衡因子K，以平衡算法在搜索過程中對解的開發與繼承能力，有效避免了算法快速陷入局部最優的問題。實驗結果表明，與其他算法框架相比，基于局部并行搜索優化算法框架的算法在解的質量上都有較大的提升，特別是在高密度問題中具有更好的效果。未來的研究工作將通過群體算法的策略應用于局部并行搜索過程中以加快收斂速度；同時，將算法框架應用于連續型分布式約束優化問題也是一個重要的方面。

參考文獻：

［1］Pujol-Gonzalez M.Multi-agent coordination DCOPs and beyond［C］// Proc of the 22nd International Joint Conference on Artificial Intelligence. Palo Alto，CA： AAAI Press， 2011： 2838-2839.

［2］Mailler R， Lesser V. Solving distributed constraint optimization pro-blems using cooperative mediation ［C］// Proc of the 3rd International Conference on Autonomous Agents and Multiagent Systems. Washington DC： IEEE Computer Society， 2004： 438-445.

［3］肖宇， 許煒， 程文青. 一種基于分布式約束滿足的資源優化模型 ［J］. 計算機應用研究， 2009， 26（3）： 864-866. （Xiao Yu， Xu Wei， Cheng Wenqing. Resource allocation optimization model based on DCSP ［J］. Application Research of Computers， 2009， 26（3）： 864-866.）

［4］Farinelli A， Rogers A， Jennings N. Agent-based decentralised coordi-nation for sensor networks using the max-sum algorithm ［J］. Autonomous Agents and Multi-Agent Systems， 2014， 28（3）： 337-380.

［5］Muldoon C， Hare G， Grady M， et al. Distributed constraint optimization for resource limited sensor networks ［J］. Science of Computer Programming， 2013， 78（5）： 583-593.

［6］Fioretto F， Pontelli E， Yeoh W. Distributed constraint optimization problems and applications ［J］. Artificial Intelligence， 2016， 10（6）： 23-47.

［7］劉燕麗. 基于沖突的NP難問題完備算法的研究 ［D］. 武漢： 華中科技大學， 2019. （Liu Yanli. Research on complete algorithm of NP hard problem based on conflict［D］. Wuhan： Huazhong University of Science and Technology， 2019.）

［8］Deng Yancheng， Chen Ziyu， Chen Dingding， et al. AsymDPOP： complete inference for asymmetric distributed constraint optimization problems ［J］. Trans on Fundamentals of Electronics， 2019， 19（5）： 1182-1189.

［9］Arshad M， Silaghi M. Distributed simulated annealing ［M］// Distributed Constraint Problem Solving and Reasoning in Multi-Agent Systems.［S.l.］：IOS Press， 2004： 1-12.

［10］Uribe L， Lara A， Deb K， et al. A new gradient free local search mechanism for constrained multi-objective optimization problems ［J］. Swarm and Evolutionary Computation， 2021， 10（9）： 31-38.

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

［12］張元恪. 基于局部搜索和遺傳策略的網絡關鍵節點算法研究 ［D］. 大連： 大連理工大學， 2021. （Zhang Yuanke. Research on network key node algorithm based on local search and genetic strategy［D］. Dalian ：Dalian University of Technology， 2021.）

［13］張文昕. 分布式約束優化問題推理求解算法的可擴展性優化研究 ［D］. 重慶： 重慶大學， 2020. （Zhang Wenxin. Study on optimizing the scalability of inference-based algorithms for distributed constraint optimization problems［D］. Chongqing： Chongqing University， 2020.）

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

［15］Rollon E， Larrosa J. Improved bounded max-sum for distributed constraint optimization ［C］// Proc of International Conference on Principles and Practice of Constraint Programming. Berlin： Springer， 2012： 624-632.

［16］Rollon E， Larrosa J. Decomposing utility functions in bounded max-sum for distributed constraint optimization ［C］// Proc of International Conference on Principles and Practice of Constraint Programming. Berlin： Springer， 2014： 646-654.

［17］Zivan R， Peled H. 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. Richland， SC： International Foundation for Autonomous Agents and Multiagent Systems， 2012： 265-272.

［18］Chen Ziyu， DengYancheng， Wu Tengfei， et al. A class of iterative refined max-sum algorithms via non-consecutive value propagation strategies ［J］. Autonomous Agents and Multi-Agent Systems， 2018，32（6）： 822-860.

［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］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（1）： 705-748.

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

［22］張海鵬， 張揚帆， 孫俊. 基于Lévy分布的柔軟自適應演化采樣算法 ［J］. 計算機應用研究， 2019， 36（7）： 1994-1997，2039. （Zhang Haipeng， Zhang Yangfan， Sun Jun. Evolutionary sampling approach with soft adaptive Lévy probability distribution. ［J］. Application Research of Computers， 2019， 36（7）： 1994-1997，2039.）

［23］余澤鵬. 基于局部搜索的分布式約束優化問題求解算法研究 ［D］. 重慶： 重慶大學， 2017. （Yu Zepeng. The study on local search algorithms for distributed constraint optimization problems［D］. Chongqing： Chongqing University，2017.）

［24］ Hirayama K， Yokoo M. The distributed breakout algorithms ［J］. Artificial Intelligence， 2005， 161（1）： 89-115.

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

［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）： 1-31.

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

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

作者簡介：石美鳳（1989-），女，重慶人，講師，博士，主要研究方向為人工智能及應用、多目標優化；楊海（1995-），男（通信作者），重慶人，碩士，主要研究方向為人工智能及應用（teachmiss@163.com）；陳媛（1966-），女，重慶人，教授，碩導，碩士，主要研究方向為數據挖掘；肖詩川（1996-），女，四川成都人，碩士，主要研究方向為人工智能及應用；廖鑫（1996-），男，四川達州人，主要研究方向為人工智能及應用；何穎（1988-），男，重慶人，博士，主要研究方向為圖像處理.