(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210714937.X (22)申请日 2022.06.22 (71)申请人 重庆理工大 学 地址 400054 重庆市巴南区红光大道69号 (72)发明人 石美凤　张彭　廖鑫　赵晴川　 梁飞鹏　 (51)Int.Cl. G06F 30/20(2020.01) G06F 30/27(2020.01) G06N 3/00(2006.01) G06F 111/04(2020.01) (54)发明名称 一种基于分布估计算法的连续型分布式约 束优化问题求 解方法 (57)摘要 本发明公开了一种基于分布估计算法的连 续型分布式约束优 化问题求解方法(EDA ‑CD)， 在 EDA‑CD中， 一组解被刻画为一个个体， 通过对解 的各个维度构建概率模型来刻 画智能体(Agent) 取值的分布， 从宏观的角度出发捕获解集的全局 统计信息。 智能体首先构建分布式种群， 分别计 算其变量的均值与方差以并行构建概率模型； 然 后所有智能体通过在广度优先搜索(Breadth   First Search,BFS)伪树上的协同通信来评估个 体的适应度； 最后智能体基于个体的评估更新概 率模型。 在四类基准问题上的广泛实验结果表 明， 相较于最先进的C ‑DCOP求解算法， EDA ‑CD的 求解质量有20％左右的提升 。 权利要求书2页 说明书9页 附图3页 CN 115099033 A 2022.09.23 CN 115099033 A 1.一种基于分布估计算法的连续型分布式约束优化问题求解方法(EDA ‑CD)， 其特征在 于， 连续型分布式约束优化问题(C ‑DCOP)求解算法的目标是优化一个由多个约束代价函数 构成的全局目标函数， 其中每个约束代价函数都由一组连续变量定义。 针对现有C ‑DCOP求 解算法的局限性， 如约束函数的限制、 易陷入局部最优、 缺少anyt ime属性等， 提出一种基于 分布估计算法的C ‑DCOP求解方法， 具体内容包括如下： S1、 设计一种分布式的个 体表示方法以应对种群在分布式环境中的构建。 S2、 设计一种分布式环境中计算个 体适应度的方法以评估个 体的优劣。 S3、 设计一种分布式方法将全局最优解传递到所有智能体以完成并行概率模型的构 建。 S4、 设计一种精英策略来保证EDA ‑CD的收敛性。 2.根据权利要求1中所述的一种基于分布估计算法的连续型分布式约束优化问题求解 方法， 其特 征在于， 步骤S1具体包括： 一般情况 下， C‑DCOP由一个五元组＜A,X,D,F, α ＞定义， 其中： A＝{a1,a2,...,an}表示一组智能体的集 合， 一个智能体控制一个或者多个 变量； X＝{x1,x2,...,xm}表示一组由智能体控制的连续变量 集合； D＝{D1,D2,...,Dm}表示一组连续值域的集合， 每个变量xi能够取得值域Di＝[LBi,UBi] 中的任意 值， 其中LBi和UBi分别表示 值域的下界和上界。 F＝{f1,f2,...,fl}是一组约束代价函数的集合， 其中每一个约束代价函数fi∈F被变量 集合X的一组子集 所定义， 即 fi的约束个数为k。 本文 仅考虑二元约束， 即k ＝2。 α :X→A是变量集合X到智能体集合A的映射函数， 表示将每个变量xj∈X的控制权分配给 智能体ai∈A。 为便于理解， 假设一个智能体控制一个变量， 因此智能体ai与变量xi所代表的 含义相同， 可认为是同一 概念。 在C‑DCOP中， 各个智能体协同赋值， 通过局部的通信完成全局的优化。 C ‑DCOP的解表示 为所有变量的赋值 集合X*， 使得所有约束代价 函数之和最小如公式(1)所示。 将C‑DCOP表示为约束图， 每个变量由相应的一个智能体控制， 每条边代表一个约束代 价函数。 且每一个智能体ai分别通过公式(2)和公式(3)计算持有样本的一个维度的均值与 标准差以构建概 率模型， 其中t 表示当前迭代次数。 。 3.根据权利要求2所述的基于分布估计算法的连续型分布式约束优化问题求解方法， 其特征在于， 步骤S2具体包括： 智能体ai接收高优先级邻居Hij∈Hi(Hi表示为智能体ai的所有高优先邻居集合， Hij为其 中的一个高优先级邻居)发送的S.xj(S.xj表示智能体xj在所有维度上的选值)并分别计算 与每一个高优先级邻居相应的部分适应度S.fitness(xi,xj)， 然后发送给相应的高优先级 邻居Hij∈Hi。 除了叶智能体和根智能体， 其他智能体通过BFS伪树向高优 先级邻居发送从低权　利　要　求　书 1/2 页 2 CN 115099033 A 2优先级邻居接收的部分适应度。 最终， 所有的部分适应度都会传递到根智能体， 通过公式 (4)， 根智能体计算每个样本的完整适应度Sk.fitness， 其中S.xi表示两个具有约束关系的 变量赋值。 单个智能体不能计算样本的完整适应度， 完整适应度需要在所有智能体的配合 下协同计算。 。 4.根据权利要求2所述的基于分布估计算法的连续型布式约束优化问题求解方法， 其 特征在于， 步骤S3具体包括： 根智能体首先对样本的适应度大小进行排序， 记为Ssort， 将最小值， 次小值和最大值分 别记为 Sworst； 然后选择适应度靠前的G个精英样本， 记为 最后根智能体将 information发送给低优先级邻居L1。 当低优先级智能体接收到高优先级邻居发送的 information后， 通过公式(5)计算精英样本 的均值， 此外， 智能体ai通过公式(6)和公式 (7)分别更新 概率模型的均值与标准差 。 。 5.根据权利要求2所述的基于分布估计算法的连续型分布式约束优化问题求解方法， 其特征在于， 步骤S4具体包括： 智能体ai通过更新后的概率模型N(S.xi( μt+1),S.xi(σt+1)2) 随机采样， 为了保持种群样本数量的稳定， 采样数量为|K ‑G|。 最后， 智能体ai将精英样本 与随机采样的样本S|K‑G|.xi合并为新种群的一个维度SK.xi并向低优先级邻居Li发送 SK.xi。 6.根据权利要求1至6项所述的基于分布估计算法的连续型分布式约束优化问题求解 方法， 其特征在于， 该算法从解的每个维度构建概率模型来刻画 解的分布情况， 并采用随机 采样和保留最优样本的方式来更新和优化种群， 通过智能体之 间的协同交互来找到高质量 的解。权　利　要　求　书 2/2 页 3 CN 115099033 A 3