本文關(guān)鍵詞：求解分布式約束優(yōu)化問(wèn)題的搜索算法研究

  更多相關(guān)文章： 分布式約束優(yōu)化問(wèn)題 最好優(yōu)先搜索策略 深度優(yōu)先搜索策略 蟻群優(yōu)化

【摘要】：分布式約束優(yōu)化問(wèn)題(DCOP)作為多Agent系統(tǒng)協(xié)作問(wèn)題的重要而有用的抽象,是解決分布式智能系統(tǒng)建模和多目標(biāo)協(xié)同優(yōu)化的有效技術(shù),具有重要的研究意義和實(shí)用價(jià)值。與傳統(tǒng)的集中控制相比,DCOP提供了強(qiáng)的魯棒性、隱私性,適用于求解規(guī)模大、難度高的組合問(wèn)題,已成為分布式人工智能領(lǐng)域的研究熱點(diǎn)。與此同時(shí),分布式約束優(yōu)化問(wèn)題的求解算法也隨之被廣泛研究,分為完備算法與非完備算法兩大類。完備算法旨在搜索所有組合空間,保證最終找到全局最優(yōu)解;非完備算法旨在在有限的時(shí)間內(nèi),盡最大努力找到一個(gè)較好解。搜索策略是這兩類算法采用的典型求解策略,已成為了研究的熱點(diǎn)。然而,目前的搜索策略存在較多局限性,不能滿足實(shí)際問(wèn)題的需要。在完備算法中主要表現(xiàn)為搜索策略單一;在非完備算法中主要表現(xiàn)為僅依據(jù)個(gè)體局部信息引導(dǎo)搜索,易陷入局部最優(yōu)。針對(duì)上述問(wèn)題,論文從策略融合和群智能引導(dǎo)兩個(gè)方面分別對(duì)完備算法與非完備算法展開研究。主要工作如下:(1)介紹了分布式約束優(yōu)化算法的研究現(xiàn)狀、分布式約束優(yōu)化問(wèn)題的相關(guān)定義和常用通信結(jié)構(gòu)以及分布式約束優(yōu)化實(shí)驗(yàn)的測(cè)試問(wèn)題、實(shí)驗(yàn)平臺(tái)與評(píng)價(jià)指標(biāo)。較詳細(xì)介紹了基于最好優(yōu)先搜索與深度優(yōu)先搜索策略的兩個(gè)典型完備算法以及蟻群優(yōu)化的相關(guān)知識(shí)與蟻群優(yōu)化解決分布式約束滿足問(wèn)題(DCSP)的算法。并且,深入分析了最好優(yōu)先搜索與深度優(yōu)先搜索策略各自的特征和存在的問(wèn)題,探討了兩種搜索策略與偽樹的關(guān)系,為后面兩種策略的結(jié)合提供了依據(jù)。(2)提出了深度優(yōu)先搜索與最好優(yōu)先搜索策略結(jié)合的DCOP完備算法。該算法依據(jù)兩種搜索策略與偽樹的關(guān)系,采用分層的思想,根據(jù)agent在偽樹中的位置特點(diǎn)分別采用深度優(yōu)先搜索策略或最好優(yōu)先搜索策略,并且給出了分層規(guī)則和兩種策略的無(wú)縫對(duì)接方法。該算法不僅充分發(fā)揮了兩種策略各自的優(yōu)勢(shì),并且保持了原單一策略算法的數(shù)據(jù)結(jié)構(gòu)與消息類型,沒有加劇算法的處理復(fù)雜性。本文從理論和實(shí)驗(yàn)論證了BD-ADOPT的完備性和有效性。(3)提出了基于蟻群優(yōu)化引導(dǎo)的DCOP非完備算法。算法引入蟻群優(yōu)化的群智能特點(diǎn),依據(jù)個(gè)體之間協(xié)作產(chǎn)生的全局信息引導(dǎo)個(gè)體做決策選擇從而提高算法的搜索性能。該算法充分考慮了DCSP和DCOP的不同,采用偽樹結(jié)構(gòu)作為構(gòu)造圖,提高了搜索的并發(fā)性;針對(duì)DCOP的特點(diǎn),設(shè)計(jì)了對(duì)數(shù)運(yùn)算與求倒運(yùn)算結(jié)合的信息素更新與引導(dǎo)概率的計(jì)算方式;引入流水線的消息處理機(jī)制,提高了搜索效率。最后,通過(guò)與其他的算法進(jìn)行對(duì)比驗(yàn)證了該算法的可行性和有效性。
【關(guān)鍵詞】：分布式約束優(yōu)化問(wèn)題 最好優(yōu)先搜索策略 深度優(yōu)先搜索策略 蟻群優(yōu)化
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 摘要3-5
• abstract5-9
• 1 緒論9-15
• 1.1 研究背景、目的及意義9
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀9-13
• 1.3 論文的主要研究?jī)?nèi)容與創(chuàng)新之處13-14
• 1.3.1 論文的主要研究?jī)?nèi)容13
• 1.3.2 論文的創(chuàng)新之處13-14
• 1.4 論文的組織結(jié)構(gòu)14-15
• 2 分布式約束優(yōu)化算法研究基礎(chǔ)15-29
• 2.1 分布式約束優(yōu)化問(wèn)題15-16
• 2.2 分布式約束優(yōu)化實(shí)驗(yàn)16-20
• 2.2.1 實(shí)驗(yàn)測(cè)試問(wèn)題16-18
• 2.2.2 實(shí)驗(yàn)平臺(tái)18-19
• 2.2.3 算法評(píng)價(jià)指標(biāo)19-20
• 2.3 求解分布式約束優(yōu)化問(wèn)題完備搜索算法20-25
• 2.3.1 采用BFS策略的算法－ADOPT20-21
• 2.3.2 采用DFS策略的算法－BnB-ADOPT21-22
• 2.3.3 兩種搜索策略的分析22-25
• 2.4 求解分布式約束滿足問(wèn)題的蟻群優(yōu)化算法25-28
• 2.4.1 蟻群優(yōu)化算法基本介紹25-26
• 2.4.2 求解分布式約束滿足問(wèn)題的蟻群優(yōu)化算法26-28
• 2.5 本章小結(jié)28-29
• 3 深度優(yōu)先搜索與最好優(yōu)先搜索策略結(jié)合的DCOP完備算法29-55
• 3.1 引言29
• 3.2 DFS與BFS策略結(jié)合的完備算法29-47
• 3.2.1 基于分層的DFS與BFS策略結(jié)合思想29-30
• 3.2.2 分層規(guī)則30-32
• 3.2.3 算法描述32-36
• 3.2.4 算法的實(shí)例分析36-44
• 3.2.5 算法的完備性證明和復(fù)雜性分析44-47
• 3.3 實(shí)驗(yàn)結(jié)果及分析47-54
• 3.3.1 實(shí)驗(yàn)方案及配置47-48
• 3.3.2 參數(shù)a 實(shí)驗(yàn)分析48-49
• 3.3.3 BD-ADOPT算法分析49-53
• 3.3.4 實(shí)驗(yàn)總結(jié)53-54
• 3.4 本章小結(jié)54-55
• 4 基于蟻群優(yōu)化引導(dǎo)的DCOP非完備算法55-71
• 4.1 引言55
• 4.2 基于蟻群優(yōu)化引導(dǎo)的非完備搜索算法55-65
• 4.2.1 基于蟻群優(yōu)化引導(dǎo)的非完備搜索算法思路55-58
• 4.2.2 算法描述58-63
• 4.2.3 算法執(zhí)行過(guò)程63-65
• 4.3 實(shí)驗(yàn)結(jié)果及分析65-70
• 4.3.1 實(shí)驗(yàn)方案及配置65-66
• 4.3.2 螞蟻數(shù)量的確定66
• 4.3.3 算法的性能分析66-70
• 4.4 本章小結(jié)70-71
• 5 總結(jié)與展望71-73
• 5.1 論文工作總結(jié)71
• 5.2 未來(lái)工作的展望71-73
• 致謝73-75
• 參考文獻(xiàn)75-81
• 附錄81
• A. 作者在攻讀碩士學(xué)位期間發(fā)表及錄用的論文目錄81
• B. 作者在攻讀碩士學(xué)位期間參加的科研項(xiàng)目81

【相似文獻(xiàn)】

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

1 介婧,曾建潮;基于思維進(jìn)化計(jì)算求解約束優(yōu)化問(wèn)題的新算法[J];計(jì)算機(jī)工程與應(yīng)用;2003年04期

2 李相勇;田澎;孔民;;解約束優(yōu)化問(wèn)題的新粒子群算法[J];系統(tǒng)管理學(xué)報(bào);2007年02期

3 石曉明;柴玉梅;;基于合作仲裁求解分布式約束優(yōu)化問(wèn)題的研究[J];微計(jì)算機(jī)信息;2008年36期

4 張書花;李艷龍;李磊;景孟旗;;求解線性等式約束優(yōu)化問(wèn)題的移動(dòng)漸近線法[J];電子測(cè)試;2013年20期

5 樊重俊，韓崇昭，胡保生，王潔;一類約束優(yōu)化問(wèn)題的改進(jìn)遺傳算法[J];控制與決策;1996年05期

6 顧宏杰;許力;;利用帶感知能力的粒子群算法求解約束優(yōu)化問(wèn)題[J];計(jì)算機(jī)應(yīng)用;2011年01期

7 郭鵬;宋福慶;;求解約束優(yōu)化問(wèn)題的新方法[J];計(jì)算機(jī)工程與應(yīng)用;2011年24期

8 彭宏,馮正柱,楊立洪;解約束優(yōu)化問(wèn)題的進(jìn)化策略與混合進(jìn)化策略的比較[J];數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用;1998年01期

9 楊艷;周永權(quán);羅林;袁冠遠(yuǎn);;人工螢火蟲群優(yōu)化算法求解約束優(yōu)化問(wèn)題[J];小型微型計(jì)算機(jī)系統(tǒng);2014年01期

10 丁博;王懷民;史殿習(xí);唐揚(yáng)斌;;低約束密度分布式約束優(yōu)化問(wèn)題的求解算法[J];軟件學(xué)報(bào);2011年04期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前6條

1 賀春華;張湘?zhèn)?呂文閣;謝慶華;;基于競(jìng)選算法的非線性約束優(yōu)化問(wèn)題實(shí)現(xiàn)[A];數(shù)學(xué)·力學(xué)·物理學(xué)·高新技術(shù)交叉研究進(jìn)展——2010（13）卷[C];2010年

2 趙志剛;韋兆文;;基于粒子群算法求解約束優(yōu)化問(wèn)題[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展——全國(guó)第17屆計(jì)算機(jī)科學(xué)與技術(shù)應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2006年

3 周巖;濮定國(guó);;解非線性不等式約束優(yōu)化問(wèn)題的序列線形方程法[A];中國(guó)運(yùn)籌學(xué)會(huì)第十屆學(xué)術(shù)交流會(huì)論文集[C];2010年

4 孫超利;曾建潮;潘正祥;;一種新的約束優(yōu)化問(wèn)題初始解的產(chǎn)生方法[A];2009中國(guó)控制與決策會(huì)議論文集（2）[C];2009年

5 金豪;朱德通;;雙邊校正約Hessian陣過(guò)濾仿射內(nèi)點(diǎn)法解非負(fù)約束非線性等式約束優(yōu)化問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第十屆學(xué)術(shù)交流會(huì)論文集[C];2010年

6 鄧長(zhǎng)壽;趙秉巖;;采用不可行解驅(qū)動(dòng)的DE進(jìn)化算法求解難約束優(yōu)化問(wèn)題[A];2011年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第一分冊(cè)）[C];2011年

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

1 程維新;約束優(yōu)化問(wèn)題的QP-free算法研究[D];武漢大學(xué);2013年

2 劉水霞;互補(bǔ)約束優(yōu)化問(wèn)題若干算法研究[D];內(nèi)蒙古大學(xué);2009年

3 萬(wàn)中;平衡約束優(yōu)化問(wèn)題的理論與算法研究[D];湖南大學(xué);2001年

4 胡一波;求解約束優(yōu)化問(wèn)題的幾種智能算法[D];西安電子科技大學(xué);2009年

5 時(shí)貞軍;約束優(yōu)化問(wèn)題的參數(shù)控制算法研究[D];大連理工大學(xué);2002年

6 王祝君;非線性優(yōu)化問(wèn)題的過(guò)濾線搜索方法[D];上海師范大學(xué);2010年

7 孫祥凱;約束優(yōu)化問(wèn)題的若干對(duì)偶以及微分性研究[D];重慶大學(xué);2012年

8 姜永;二階錐均衡約束的優(yōu)化問(wèn)題[D];大連理工大學(xué);2011年

9 劉玉珍;基于進(jìn)化計(jì)算的單目標(biāo)優(yōu)化問(wèn)題研究[D];湘潭大學(xué);2012年

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

1 徐海東;人工蜂群算法理論與應(yīng)用研究[D];山東大學(xué);2015年

2 王小朋;兩類問(wèn)題的Newton方法研究[D];武漢理工大學(xué);2015年

3 段慶松;約束優(yōu)化問(wèn)題的序列近似方法收斂性[D];大連理工大學(xué);2015年

4 池倩倩;錐約束優(yōu)化問(wèn)題的罰逼近[D];蘇州大學(xué);2015年

5 王佳;基于Chen-Harker-Kanzow-Smale函數(shù)的概率約束優(yōu)化問(wèn)題的光滑D.C.近似[D];遼寧師范大學(xué);2015年

6 戚雪彩;人工蜂群算法求解約束優(yōu)化問(wèn)題的研究[D];南京師范大學(xué);2015年

7 何琛;求解分布式約束優(yōu)化問(wèn)題的搜索算法研究[D];重慶大學(xué);2016年

8 楊亞飛;約束優(yōu)化問(wèn)題的粒子群算法方法[D];中國(guó)地質(zhì)大學(xué)(北京);2012年

9 李_g;非線性約束優(yōu)化問(wèn)題的自適應(yīng)三次正則化方法[D];大連理工大學(xué);2013年

10 胡一波;解決約束優(yōu)化問(wèn)題的兩種新的進(jìn)化算法[D];西安電子科技大學(xué);2006年

，

本文編號(hào)：964359