分布式約束優(yōu)化完備算法的通信結構研究.pdf

1、分布式約束優(yōu)化是解決分布式推理任務的一個基本框架，是目前多Agent領域的研究熱點。近幾年來提出了許多優(yōu)秀的分布式約束優(yōu)化算法，這些算法大體上分為完備算法和非完備算法。非完備算法通過局部搜索，旨在找到最好的解，適用于求解大規(guī)模問題，但這類算法容易陷入局部最優(yōu)解。而完備算法通過遍歷搜索空間，旨在找到全局最優(yōu)解，適用于中小規(guī)模問題。本論文針對如何提高完備算法的性能展開研究。完備算法的性能不僅依靠算法自身的求解策略，還依靠預處理階段形成的Ag

2、ent通信結構。目前針對完備算法的求解策略已提出了許多優(yōu)化方法，但對Agent通信結構的優(yōu)化研究較少。因此，研究分布式約束優(yōu)化完備算法的Agent通信結構具有重要的學術意義和實際應用價值。本文從結點自身的屬性特征和結點之間的約束關系特征這兩方面對基于樹型的通信結構進行研究。具體研究工作如下：
　　①介紹了分布式約束的研究現(xiàn)狀，并對分布式約束優(yōu)化相關定義、完備算法的通信結構做了進一步闡述。另外，分別介紹了鏈式結構和樹型結構的形成過程

3、以及相應的典型完備算法。
　?、谔岢隽艘环N基于結點貢獻的通信結構構建方法。該方法采用了約束一致性(ArcConsistency,AC)的思想，以結點對全局最優(yōu)代價的貢獻來對結點進行排序以構建Agent樹型通信結構；將貢獻值較高的結點優(yōu)先排序，使得在求解過程中可以迅速地接近全局最優(yōu)解。通過對不同的Agent樹型通信結構對算法性能影晌的實驗對比，表明該方法減少了算法的搜索空間，提高了算法的求解效率。
　?、厶岢隽艘环N基于圖割點的

4、通信結構構建方法。該方法利用問題建模后的約束圖特征，以約束圖的割點作為構建樹型通信結構的依據(jù)，并在沒有割點的情況下結合結點貢獻的策略，在一定程度上提高了算法的并行性。實驗結果表明，該方法提高了并行性，并減少搜索空間從而提高了算法的性能。最后，將本文提出的兩種構建方法通過對比，分析這兩種構建方法適合的問題類型。
　　④為了驗證所提的通信結構構造方法的可行性，本文將采用圖割點通信結構的完備算法用于解決會議安排問題。與采用基于結點連接邊