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

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

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

10 丁博;王懷民;史殿習;唐揚斌;;低約束密度分布式約束優(yōu)化問題的求解算法[J];軟件學報;2011年04期

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

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

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

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

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

5 金豪;朱德通;;雙邊校正約Hessian陣過濾仿射內點法解非負約束非線性等式約束優(yōu)化問題[A];中國運籌學會第十屆學術交流會論文集[C];2010年

6 鄧長壽;趙秉巖;;采用不可行解驅動的DE進化算法求解難約束優(yōu)化問題[A];2011年中國智能自動化學術會議論文集（第一分冊）[C];2011年

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

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

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

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

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

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

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

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

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

9 劉玉珍;基于進化計算的單目標優(yōu)化問題研究[D];湘潭大學;2012年

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

1 徐海東;人工蜂群算法理論與應用研究[D];山東大學;2015年

2 王小朋;兩類問題的Newton方法研究[D];武漢理工大學;2015年

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

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

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

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

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

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

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

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

，

本文編號：964359