基于局部搜索的分布式約束優(yōu)化問題求解算法研究.pdf

1、分布式約束優(yōu)化問題(DCOP)作為多Agent系統(tǒng)協(xié)作問題的重要抽象，具有隱私性、信息局部性、控制分散化等特點，是對分布式智能系統(tǒng)和多目標優(yōu)化等問題的有效建模技術。因此，對分布式約束優(yōu)化問題的求解成為該領域的研究熱點。局部搜索算法作為一類求解DCOP的非完備算法，由于其簡單的邏輯結構和靈活的優(yōu)化方式，受到了廣泛的關注。本文介紹了分布式約束優(yōu)化問題求解算法的國內(nèi)外研究現(xiàn)狀，分析了各類算法的優(yōu)點和局限性，并針對局部搜索算法存在的局限性以及智

2、能優(yōu)化引導兩個方面展開研究，主要工作如下：
　　①針對局部搜索算法中相鄰Agent之間賦值相互依賴的限制，提出了部分決策機制(PDS)。該機制通過Agent在決策過程中忽略部分鄰居結點的賦值信息來打破相鄰Agent之間的賦值依賴關系，獲取更大的決策空間，做出更優(yōu)的決策，從而以較小的代價有效地提高了算法的求解質量。PDS包含兩個部分決策過程：觸發(fā)式部分決策和遞歸式部分決策。前者在Agent不能提高自身利益時觸發(fā)，通過忽略鄰居的取值信

3、息來跳出賦值依賴造成的潛在局部收斂狀態(tài)；而后者不斷地由被忽略的Agent觸發(fā)來提升全局利益。此外，PDS通過一個包含自適應概率的觸發(fā)條件來控制部分決策的執(zhí)行。該機制可以結合任意局部搜索算法進行優(yōu)化，具有很大的普適性。本文從理論上論證了部分決策機制的可行性和收斂性，并通過實驗驗證了該機制的有效性。
　?、谔岢隽嘶诰植克阉鞯倪z傳優(yōu)化算法(LS-GA)。算法結合了遺傳優(yōu)化的智能性和局部搜索的靈活性，作為智能優(yōu)化算法求解DCOP的一種新