基于推理的分布式約束優(yōu)化完備算法研究及實驗平臺實現(xiàn).pdf

1、分布式約束優(yōu)化是對多Agent系統(tǒng)的建模，廣泛應(yīng)用于求解分布式計劃、分布式調(diào)度和分布式資源分配問題，典型應(yīng)用有災(zāi)難救援、多Agent小組合作、分布式機器人、會議調(diào)度、傳感器網(wǎng)絡(luò)等。DPOP算法是一種基于動態(tài)規(guī)劃思想的推理式算法，也是當(dāng)前分布式約束優(yōu)化完備算法中效率最高的算法之一。DPOP算法的性能和效率遠遠高于許多搜索類算法，非常適合于實際應(yīng)用問題的求解。本文基于DPOP算法，從通信結(jié)構(gòu)的角度提出改進和優(yōu)化思路，并在自主開發(fā)的分布式約束

2、優(yōu)化算法實驗平臺DCOPSolver上實驗和證明思路的可行性，具體研究工作如下：
　?、俳榻B了分布式約束優(yōu)化的研究現(xiàn)狀和最新研究動態(tài)，詳細闡述了分布式約束優(yōu)化的基本概念和定義，包括約束圖、通信結(jié)構(gòu)和圖著色、會議調(diào)度、隨機DCOP三類典型問題，并重點介紹了本文的主要研究對象DPOP算法。
　?、谔岢鲆环N新的以廣度優(yōu)先搜索偽樹為通信結(jié)構(gòu)的BFSDPOP算法。相比DPOP采用的深度優(yōu)先搜索偽樹通信結(jié)構(gòu)，BFSDPOP采用的廣度優(yōu)先

3、搜索偽樹通信結(jié)構(gòu)具有分支多、通信路徑短的特點，使得BFSDPOP算法的并行運算性能和通信效率更優(yōu)。同時，本文提出ClusterRemoving算法通過合理分配偽樹中的交叉邊，很好地控制了算法中生成的最大消息大小。
　?、厶岢鲆环N新的以深度優(yōu)先搜索偽樹為通信結(jié)構(gòu)的CVDPOP算法，它以最佳割點和最大度數(shù)優(yōu)先的策略構(gòu)建其偽樹通信結(jié)構(gòu)。CVDPOP算法的創(chuàng)新之處在于引入割點引導(dǎo)深度優(yōu)先搜索偽樹的構(gòu)建，借助割點促進分支生成的特點構(gòu)建分支更

4、多、質(zhì)量更優(yōu)的深度優(yōu)先搜索偽樹，從而提高算法性能。
　?、荑b于已有實驗平臺的復(fù)雜性，本文自主開發(fā)了一套新的分布式約束優(yōu)化算法實驗平臺DCOPSolver，它具有功能模塊更加精簡，新算法擴展集成難度更小、速度更快的特點。本文的所有實驗均在DCOPSolver上實施，實驗比較了DPOP、BFSDPOP、CVDPOP三種算法分別求解圖著色問題、會議調(diào)度問題和隨機DCOP問題時的運行時間和最大消息維度。實驗結(jié)果顯示BFSDPOP和CVDP