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

在審

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

1.一種基于分布估計算法的連續型分布式約束優化問題求解方法(EDA-CD)，其特征在于，連續型分布式約束優化問題(C-DCOP)求解算法的目標是優化一個由多個約束代價函數構成的全局目標函數，其中每個約束代價函數都由一組連續變量定義。針對現有C-DCOP求解算法的局限性，如約束函數的限制、易陷入局部最優、缺少anytime屬性等，提出一種基于分布估計算法的C-DCOP求解方法，具體內容包括如下：

S1、設計一種分布式的個體表示方法以應對種群在分布式環境中的構建。

S2、設計一種分布式環境中計算個體適應度的方法以評估個體的優劣。

S3、設計一種分布式方法將全局最優解傳遞到所有智能體以完成并行概率模型的構建。

S4、設計一種精英策略來保證EDA-CD的收斂性。

2.根據權利要求1中所述的一種基于分布估計算法的連續型分布式約束優化問題求解方法，其特征在于，步驟S1具體包括：

一般情況下，C-DCOP由一個五元組＜A,X,D,F,α＞定義，其中：

A＝{a₁,a₂,...,a_n}表示一組智能體的集合，一個智能體控制一個或者多個變量；

X＝{x₁,x₂,...,x_m}表示一組由智能體控制的連續變量集合；

D＝{D₁,D₂,...,D_m}表示一組連續值域的集合，每個變量x_i能夠取得值域D_i＝[LB_i,UB_i]中的任意值，其中LB_i和UB_i分別表示值域的下界和上界。

F＝{f₁,f₂,...,f_l}是一組約束代價函數的集合，其中每一個約束代價函數f_i∈F被變量集合X的一組子集所定義，即f_i的約束個數為k。本文僅考慮二元約束，即k＝2。

α:X→A是變量集合X到智能體集合A的映射函數，表示將每個變量x_j∈X的控制權分配給智能體a_i∈A。為便于理解，假設一個智能體控制一個變量，因此智能體a_i與變量x_i所代表的含義相同，可認為是同一概念。

在C-DCOP中，各個智能體協同賦值，通過局部的通信完成全局的優化。C-DCOP的解表示為所有變量的賦值集合X^*，使得所有約束代價函數之和最小如公式(1)所示。

將C-DCOP表示為約束圖，每個變量由相應的一個智能體控制，每條邊代表一個約束代價函數。且每一個智能體a_i分別通過公式(2)和公式(3)計算持有樣本的一個維度的均值與標準差以構建概率模型，其中t表示當前迭代次數。

。

3.根據權利要求2所述的基于分布估計算法的連續型分布式約束優化問題求解方法，其特征在于，步驟S2具體包括：

智能體a_i接收高優先級鄰居H_ij∈H_i(H_i表示為智能體a_i的所有高優先鄰居集合，H_ij為其中的一個高優先級鄰居)發送的S.x_j(S.x_j表示智能體x_j在所有維度上的選值)并分別計算與每一個高優先級鄰居相應的部分適應度S.fitness(x_i,x_j)，然后發送給相應的高優先級鄰居H_ij∈H_i。除了葉智能體和根智能體，其他智能體通過BFS偽樹向高優先級鄰居發送從低優先級鄰居接收的部分適應度。最終，所有的部分適應度都會傳遞到根智能體，通過公式(4)，根智能體計算每個樣本的完整適應度S_k.fitness，其中S.xⁱ表示兩個具有約束關系的變量賦值。單個智能體不能計算樣本的完整適應度，完整適應度需要在所有智能體的配合下協同計算。

。