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

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

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

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

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