本文關(guān)鍵詞：基于推理的分布式約束優(yōu)化完備算法研究及實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)

  更多相關(guān)文章： 分布式約束優(yōu)化 動(dòng)態(tài)規(guī)劃 通信結(jié)構(gòu) 廣度優(yōu)先搜索 割點(diǎn)

【摘要】：分布式約束優(yōu)化是對(duì)多Agent系統(tǒng)的建模,廣泛應(yīng)用于求解分布式計(jì)劃、分布式調(diào)度和分布式資源分配問(wèn)題,典型應(yīng)用有災(zāi)難救援、多Agent小組合作、分布式機(jī)器人、會(huì)議調(diào)度、傳感器網(wǎng)絡(luò)等。DPOP算法是一種基于動(dòng)態(tài)規(guī)劃思想的推理式算法,也是當(dāng)前分布式約束優(yōu)化完備算法中效率最高的算法之一。DPOP算法的性能和效率遠(yuǎn)遠(yuǎn)高于許多搜索類(lèi)算法,非常適合于實(shí)際應(yīng)用問(wèn)題的求解。本文基于DPOP算法,從通信結(jié)構(gòu)的角度提出改進(jìn)和優(yōu)化思路,并在自主開(kāi)發(fā)的分布式約束優(yōu)化算法實(shí)驗(yàn)平臺(tái)DCOPSolver上實(shí)驗(yàn)和證明思路的可行性,具體研究工作如下:(1)介紹了分布式約束優(yōu)化的研究現(xiàn)狀和最新研究動(dòng)態(tài),詳細(xì)闡述了分布式約束優(yōu)化的基本概念和定義,包括約束圖、通信結(jié)構(gòu)和圖著色、會(huì)議調(diào)度、隨機(jī)DCOP三類(lèi)典型問(wèn)題,并重點(diǎn)介紹了本文的主要研究對(duì)象DPOP算法。(2)提出一種新的以廣度優(yōu)先搜索偽樹(shù)為通信結(jié)構(gòu)的BFSDPOP算法。相比DPOP采用的深度優(yōu)先搜索偽樹(shù)通信結(jié)構(gòu),BFSDPOP采用的廣度優(yōu)先搜索偽樹(shù)通信結(jié)構(gòu)具有分支多、通信路徑短的特點(diǎn),使得BFSDPOP算法的并行運(yùn)算性能和通信效率更優(yōu)。同時(shí),本文提出ClusterRemoving算法通過(guò)合理分配偽樹(shù)中的交叉邊,很好地控制了算法中生成的最大消息大小。(3)提出一種新的以深度優(yōu)先搜索偽樹(shù)為通信結(jié)構(gòu)的CVDPOP算法,它以最佳割點(diǎn)和最大度數(shù)優(yōu)先的策略構(gòu)建其偽樹(shù)通信結(jié)構(gòu)。CVDPOP算法的創(chuàng)新之處在于引入割點(diǎn)引導(dǎo)深度優(yōu)先搜索偽樹(shù)的構(gòu)建,借助割點(diǎn)促進(jìn)分支生成的特點(diǎn)構(gòu)建分支更多、質(zhì)量更優(yōu)的深度優(yōu)先搜索偽樹(shù),從而提高算法性能。(4)鑒于已有實(shí)驗(yàn)平臺(tái)的復(fù)雜性,本文自主開(kāi)發(fā)了一套新的分布式約束優(yōu)化算法實(shí)驗(yàn)平臺(tái)DCOPSolver,它具有功能模塊更加精簡(jiǎn),新算法擴(kuò)展集成難度更小、速度更快的特點(diǎn)。本文的所有實(shí)驗(yàn)均在DCOPSolver上實(shí)施,實(shí)驗(yàn)比較了DPOP、BFSDPOP、CVDPOP三種算法分別求解圖著色問(wèn)題、會(huì)議調(diào)度問(wèn)題和隨機(jī)DCOP問(wèn)題時(shí)的運(yùn)行時(shí)間和最大消息維度。實(shí)驗(yàn)結(jié)果顯示BFSDPOP和CVDPOP算法相比原始DPOP算法均具有顯著優(yōu)勢(shì),證明了廣度優(yōu)先搜索偽樹(shù)和最佳割點(diǎn)最大度數(shù)優(yōu)先策略對(duì)提高算法效率和性能的積極作用。
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：TP181

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 曾凡刊;求線圖樹(shù)集的綜合方法——二模域代數(shù)拓?fù)錁?shù)組法[J];華中工學(xué)院學(xué)報(bào);1982年02期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 何振;基于推理的分布式約束優(yōu)化完備算法研究及實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)[D];重慶大學(xué);2016年

，

本文編號(hào)：1201824