求解分布式約束優(yōu)化問題的搜索算法研究.pdf

1、分布式約束優(yōu)化問題（DCOP）作為多Agent系統(tǒng)協(xié)作問題的重要而有用的抽象，是解決分布式智能系統(tǒng)建模和多目標(biāo)協(xié)同優(yōu)化的有效技術(shù)，具有重要的研究意義和實(shí)用價(jià)值。與傳統(tǒng)的集中控制相比，DCOP提供了強(qiáng)的魯棒性、隱私性，適用于求解規(guī)模大、難度高的組合問題，已成為分布式人工智能領(lǐng)域的研究熱點(diǎn)。與此同時(shí)，分布式約束優(yōu)化問題的求解算法也隨之被廣泛研究，分為完備算法與非完備算法兩大類。完備算法旨在搜索所有組合空間，保證最終找到全局最優(yōu)解；非完備算法

2、旨在在有限的時(shí)間內(nèi)，盡最大努力找到一個(gè)較好解。搜索策略是這兩類算法采用的典型求解策略，已成為了研究的熱點(diǎn)。然而，目前的搜索策略存在較多局限性，不能滿足實(shí)際問題的需要。在完備算法中主要表現(xiàn)為搜索策略單一；在非完備算法中主要表現(xiàn)為僅依據(jù)個(gè)體局部信息引導(dǎo)搜索，易陷入局部最優(yōu)。
　　針對(duì)上述問題，論文從策略融合和群智能引導(dǎo)兩個(gè)方面分別對(duì)完備算法與非完備算法展開研究。主要工作如下：
　　①介紹了分布式約束優(yōu)化算法的研究現(xiàn)狀、分布式約束

3、優(yōu)化問題的相關(guān)定義和常用通信結(jié)構(gòu)以及分布式約束優(yōu)化實(shí)驗(yàn)的測(cè)試問題、實(shí)驗(yàn)平臺(tái)與評(píng)價(jià)指標(biāo)。較詳細(xì)介紹了基于最好優(yōu)先搜索與深度優(yōu)先搜索策略的兩個(gè)典型完備算法以及蟻群優(yōu)化的相關(guān)知識(shí)與蟻群優(yōu)化解決分布式約束滿足問題（DCSP）的算法。并且，深入分析了最好優(yōu)先搜索與深度優(yōu)先搜索策略各自的特征和存在的問題，探討了兩種搜索策略與偽樹的關(guān)系，為后面兩種策略的結(jié)合提供了依據(jù)。
　?、谔岢隽松疃葍?yōu)先搜索與最好優(yōu)先搜索策略結(jié)合的DCOP完備算法。該算法依

4、據(jù)兩種搜索策略與偽樹的關(guān)系，采用分層的思想，根據(jù)agent在偽樹中的位置特點(diǎn)分別采用深度優(yōu)先搜索策略或最好優(yōu)先搜索策略，并且給出了分層規(guī)則和兩種策略的無縫對(duì)接方法。該算法不僅充分發(fā)揮了兩種策略各自的優(yōu)勢(shì)，并且保持了原單一策略算法的數(shù)據(jù)結(jié)構(gòu)與消息類型，沒有加劇算法的處理復(fù)雜性。本文從理論和實(shí)驗(yàn)論證了BD-ADOPT的完備性和有效性。
　?、厶岢隽嘶谙伻簝?yōu)化引導(dǎo)的DCOP非完備算法。算法引入蟻群優(yōu)化的群智能特點(diǎn)，依據(jù)個(gè)體之間協(xié)作產(chǎn)生