[發明專利]一種基于分布估計算法的連續型分布式約束優化問題求解方法

在審

• 申請號: 202210714937.X
• 申請日: 2022-06-22
• 公開（公告）號: CN115099033A
• 公開（公告）日: 2022-09-23
• 發明（設計）人: 石美鳳;張彭;廖鑫;趙晴川;梁飛鵬
• 申請（專利權）人: 重慶理工大學
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06F30/27;G06N3/00;G06F111/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種基于分布估計算法的連續型分布式約束優化問題求解方法(EDA?CD)，在EDA?CD中，一組解被刻畫為一個個體，通過對解的各個維度構建概率模型來刻畫智能體(Agent)取值的分布，從宏觀的角度出發捕獲解集的全局統計信息。智能體首先構建分布式種群，分別計算其變量的均值與方差以并行構建概率模型；然后所有智能體通過在廣度優先搜索(Breadth First Search,BFS)偽樹上的協同通信來評估個體的適應度；最后智能體基于個體的評估更新概率模型。在四類基準問題上的廣泛實驗結果表明，相較于最先進的C?DCOP求解算法，EDA?CD的求解質量有20％左右的提升。

技術領域

本發明涉及約束優化方法，特別涉及基于分布估計算法的連續型分布式約束優化問題求解方法。

背景技術

分布式約束優化問題(Distributed Constraint Optimization Problems,DCOPs)是解決分布式智能系統建模的有效框架。DCOPs廣泛應用于實際生活中，如會議調度，資源分配、導彈路線規劃、傳感器網絡、微電網控制和智能家居等。DCOP求解算法分為完備算法和非完備算法。完備算法旨在提供全局最優解，但計算開銷和內存需求隨著問題規模的增加呈現指數增長，如ADOPT、DPOP和PT-FB等；非完備算法旨在通過提供一個近似解來降低計算開銷和內存需求，如DSA、Max-Sum、MGM和ACO_DCOP等。在一些連續變量的應用中，智能體需取得連續型參數，如方向，速度和傳感器激活時間等，這使得DCOP不再適用于建模連續型問題。因此，連續型分布式約束優化問題(Continuous DCOPs,C-DCOPs)就被提出來建模連續型問題。在C-DCOP中，變量和值域都是連續的，約束代價以函數的形式表示；而在DCOP中，約束代價以表格的形式呈現。

連續最大和算法(Continuous Max-Sum,CMS)是離散最大和的連續版本，與C-DCOP同時被提出以應對變量、值域和約束代價的改變。在CMS中，約束代價函數被近似為分段線性函數，但只有極少數實際應用適用于分段線性函數，這使得CMS的應用范圍并不廣?；旌线B續最大和算法(Hybrid Continuous Max-Sum,HCMS)的提出解決了CMS的局限性。HCMS首先通過離散最大和獲得一組近似解，然后通過連續非線性優化方法提高近似解的質量。由于連續非線性優化方法如梯度下降需要導數計算，因此HCMS不適用于不可微的應用并且無法保證收斂。精確DPOP(Exact Continuous DPOP,EC-DPOP)、近似DPOP(ApproximateContinuous DPOP,AC-DPOP)和聚類近似DPOP(Clustered AC-DPOP,CAC-DPOP)被同時提出求解C-DCOP。EC-DPOP擴展DPOP中的加法和投影操作來精確求解C-DCOP；AC-DPOP和CAC-DPOP近似求解C-DCOP。然而，這三種算法會產生指數級的計算開銷和內存需求。Moumita等人提出了基于C-DCOP的粒子群優化算法(Particle Swarm Optimization based C-DCOP,PFD)來降低計算開銷和內存需求。PFD將粒子群優化算法引入C-DCOP，通過種群尋優的方式獲得高質量的解，然而搜索能力差和容易陷入局部最優的問題限制了求解質量的提升。連續協同約束近似算法(Continuous Cooperative Constraint Approximation,C-CoCoA)通過半貪婪的局部搜索，以較小的通信開銷和極快的執行時間獲得高質量的解，但在大規模的復雜問題上，C-CoCoA的求解質量不佳。同時，C-CoCoA作為一種非迭代算法，不具備anytime屬性。

發明內容

針對以上存在的問題，本發明提供如下技術方案：一種基于分布估計算法的連續型分布式約束優化問題求解方法(Estimation of Distribution Algorithm for C-DCOP,EDA-CD)用于解決目前C-DCOP求解算法的局限，包括如下步驟：

一個C-DCOP可以由一個五元組＜A,X,D,F,α＞定義，其中: