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

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

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

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

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