一种求解昂贵约束优化问题的快速广义代理辅助进化方法

摘要

本发明公开了一种求解昂贵约束优化问题的快速广义代理辅助进化方法，通过全局代理模型和局部代理模型管理构建了一种新的模型管理框架。首先,在基于集成代理模型构建全局代理模型后,提出差距准则来选择个体进行精确评估,进而指导进化算法搜索。其次,为了增强算法的开发能力,提出群体信任域来构建局部代理模型。此外,还引入顶部可行均值法则来保持可行区域与不可行区域之间的搜索平衡,提升可行解质量,加快收敛速度。因此该方法在优化计算资源有限的昂贵约束问题上的性能优于其他先进算法。

说明书

技术领域

本发明设计群智能优化算法领域，特别是一种求解昂贵约束优化问题的快速广义代理辅助进化方法(A Fast Generalized Surrogate-Assisted Evolutionary Algorithmfor Expensive Constrained Optimization Problems)。

背景技术

约束优化问题(Constrained Optimization Problems,COPs)需要在满足各种约束限制的基础上再对目标函数进行优化,而约束的存在会将搜索空间划分为可行区域和不可行区域,导致搜索空间结构改变,使得问题复杂化,这为求解COPs带来了巨大的挑战。然而,随着科技的不断发展,约束优化问题还面临着目标函数与约束计算需耗费巨大计算成本的挑战,因此这类问题被称为昂贵约束优化问题(Expensive ConstrainedOptimization Problems,ECOPs)。代理辅助进化算法(Surrogate-Assisted EAs,SAEAs)是求解昂贵无约束优化问题最流行方法之一。SAEAs旨在通过单个或多个代理模型来拟合目标函数以减少优化所需的适应度评估(Fitness Evaluations,FEs),但使用SAEAs的前提是建立代理模型(也称为元模型)的计算成本与精确的FEs相比可以忽略不计。此外,如何在有限的计算预算下将代理模型有效合理地与目标函数结合也是发明需要面临的挑战之一。同时，SAEAs在处理高维EUCOPs或ECOPs时将会面临巨大的挑战。在处理ECOPs时,由于约束的存在会使得可行域变得非凸和非连续,甚至可能仅剩几个孤立点。在这种情况下,很难在有限的精确FEs中找到可行的最优解。因此,如何处理约束也是本发明需要考虑的问题之一。

发明内容

为了解决现有技术存在的难题，本发明提出了一种求解昂贵约束优化问题的快速广义代理辅助进化方法，实质上是一种基于多策略混合麻雀搜索算法的快速广义代理辅助进化算法，通过全局代理模型和局部代理模型管理构建了一种新的模型管理框架。首先,在基于集成代理模型构建全局代理模型后,提出差距准则来选择个体进行精确评估,进而指导进化算法搜索。其次,为了增强算法的开发能力,提出群体信任域来构建局部代理模型。此外,还引入顶部可行均值法则来保持可行区域与不可行区域之间的搜索平衡,提升可行解质量,加快收敛速度。因此该方法在优化计算资源有限的昂贵约束问题上的性能优于其他先进算法。

本发明提出了基于多策略混合麻雀搜索算法的快速广义代理辅助进化算法(FastGeneralized Surrogate-Assisted Evolution Algorithm based on Multi-StrategyHybrid Sparrow Search Algorithm,FGSA-MSSA),来实现对高维EUCOPs或ECOPs的优化。

本发明的基本设计思路包括以下要点：

1.本发明提出了一种新的模型管理框架来平衡算法的探索能力与开发能力,即在全局模型管理策略下,选择适应度值最佳的个体进行精确FEs,提高代理模型准确性,扩大算法搜索范围,提升算法的探索能力,保证种群多样性,避免陷入局部最优,并为局部搜索定位出有希望区域：在局部模型管理策略中,基于可行性法则计算排名前t个个体位置的平均值并对其进行精确FEs,提升算法开发能力,加快收敛速度与提升收敛精度。

2.不同于传统的不确定性估计方法,本发明提出了一种同时考虑距离和代理模型预测间差异的差距法则(Variance and Distance,VD),即选择同时具有最大距离和最大差异的个体进行精确FEs。若采样的区域是密集的,则加入最大差异评估不确定性以提高准确性,该方法可以弥补传统基于距离的不确定准则评估相似的缺陷。

3.不同于传统的可行性法则,本发明提出了一种将可行性法则与顶部平均信息相结合的顶部可行均值法则(Top Feasible Mean Rule,TFMR)。若选择的顶部集合全是可行解,均值可以减轻代理模型所带来的误差：若包含了不可行解,均值还可以利用不可行区域中具有较好适应值的不可行解的信息,从而提高算法的收敛性,弥补了原方法易忽略不可行个体信息的不足。

4.本发明提出基于种群信任域的局部代理模型,该模型可以降低构建成本,进一步提高局部开发能力。

为实现上述目的，本发明具体采取如下技术方案：

一种求解昂贵约束优化问题的快速广义代理辅助进化方法，其特征在于：

采用MSHSSA作为搜索引擎，在全局模型管理策略下,选择适应度值最佳的个体进行精确FEs,并为局部搜索定位出有希望区域；在局部模型管理策略中,基于可行性法则计算排名前t个个体位置的平均值并对其进行精确FEs,以加快收敛速度与提升收敛精度；

采用同时考虑距离和代理模型预测间差异的差距法则VD,即选择同时具有最大距离和最大差异的个体进行精确FEs；若采样的区域是密集的,则加入最大差异评估不确定性以提高准确性；

采用将可行性法则与顶部平均信息相结合的顶部可行均值法则TFMR；首先,基于可行性法则对种群进行排序；然后,选择前t*100％个个体计算均值得到待评估的候选解C,其中t由用户指定；最后,利用精确FEs对其进行评估。

进一步地，采用RBF作为全局和局部代理模型来近似目标函数与约束函数；

集成RBF和PR作为全局代理模型来近似目标函数与约束函数。

进一步地，采用三次样条φ(r)＝r

进一步地，采用最小二乘法计算PR中的未知系数。

进一步地，首先采用拉丁超立方抽样LHS初始化k个样本,使用精确FEs对其进行适应度评估并添加到数据库DB中；根据可行性法则从DB中选择排名前m个样本作为初始种群,并更新算法所需参数；然后,利用DB中的所有样本来构建由PR和RBF集成的全局代理模型f

其次,基于群体信任域构建局部RBF模型f

最后,根据终止条件判断是否结束。

进一步地，基于全局代理模型辅助的MSHSSA和基于局部代理辅助的MSHSSA交替执行，即从基于全局代理模型辅助的MSHSSA开始进行全局探索，并在无法进一步改善全局最优时切换到基于局部代理辅助的MSHSSA进行局部搜索；

当基于局部代理辅助的MSHSSA无法再找到更优个体时，则切换回基于全局代理模型辅助的MSHSSA。

进一步地，所述差距法则VD选择同时具有最大距离和最大差异的个体进行精确FEs，具体为：

VD

V

Dist

MaxDist

MinDist

Dist

其中，m和n分别表示种群个数和DB中样本个数；Vens表示集成代理模型中成员在预测同一个候选解时产生的分歧，当分歧越大说明该区域适应度景观复杂而不易近似；Disti

相比于现有技术，本发明及其优选方案通过全局代理模型和局部代理模型管理构建了一种新的模型管理框架；首先，在基于集成代理模型构建全局代理模型后，提出差距准则来选择个体进行精确评估，进而指导进化算法搜索；其次，为了增强算法的开发能力，提出群体信任域来构建局部代理模型；此外，还引入顶部可行均值法则来保持可行区域与不可行区域之间的搜索平衡，提升可行解质量，加快收敛速度；因此该方法在优化计算资源有限的昂贵约束问题上的性能优于其他先进算法。

附图说明

图1为本发明实施例FGSA-MSSA流程图。

具体实施方式

为让本专利的特征和优点能更明显易懂，下文特举实施例，作详细说明如下：

应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的说明。除非另有指明，本说明书使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

以下结合具体的实施例对本发明方案进行进一步的介绍：

1.约束优化问题：

通常，约束优化问题COPs的数学描述如下：

min/max：f(X)X＝(x

L

s.t：g

h

Ω＝{X∈S|g

j＝l+1,...,m}(1)

其中,f是目标函数：X是D维决策向量，Ω为可行域,S＝∏

其中，n表示种群规模，δ是等式约束h

2.多策略混合麻雀搜索算法

麻雀搜索算法(Sparrow Search Algorithm,SSA)是一种受麻雀觅食和反捕食行为启发的群智能优化算法。SSA具有较强的搜索能力，且实现简单、参数少、可扩展性高。然而,SSA在面对具有强约束,非凸性和不可微等特征的复杂问题时,存在开发与探索能力不平衡、易陷入局部最优、过早收敛和种群多样性较低等不足。为此,针对SSA的不足,发明人在公开号为：CN114065626A的中国专利中提出了多策略混合麻雀搜索算法(Multi-Strategy Hybrid SSA,MSHSSA)。

MSHSSA主要由4个阶段组成。首先,构建双向初始化机制，以获得最优的初始种群。其次,基于交叉与变异算子的位置更新公式生成新的种群X

3.代理模型

3.1径向基函数(Radial Basis Function,RBF)

RBF是一种插值模型,已被广泛作为近似函数来拟合多元不规则数据。这是由于RBF能在具有不同景观特征问题上体现良好性能,且对问题维数的增加相对不敏感。此外,RBF还适用于全局和局部建模。因此,本发明采用RBF作为全局和局部代理模型来近似目标函数与约束函数。

假设有m个不同的训练点X＝[x

其中,φ(·)、||·||分别表示核函数和欧几里得范数。常用核函数包括线性样条、薄板样条、三次样条、多四次样条和高斯函数。本发明选择三次样条φ(r)＝r

其中,Φ是一个m×m的矩阵,Φ

3.2多项式回归(Polynomial Regression,PR)

PR适用于模拟非线性可分的数据,能够拟合一些复杂的函数,且实现简单,建模快,因此得到了广泛的应用。本发明集成RBF和PR作为全局代理模型来近似目标函数与约束函数。

假设有m个不同的训练点X＝[x

其中,b＝[b

其中,A是全部元素都为1的m×1的矩阵。

4.代理模型可行性法则

求解约束优化进化算法的性能取决于两个因素：一是作为搜索引擎的进化算法,二是用来处理约束的约束处理方法。本发明应用的可行性法则实现简单,无需定义额外参数,具有高普遍性(适合与不同的算法结合,而不去过多地改变算法本身),因此得到了广泛的应用。其定义如下：

(1)当作比较的两个个体(x

(2)当x

(3)当比较的两个个体(x

5.总体框架

本发明所提算法的流程图如图1所示。本发明提出算法采用拉丁超立方抽样(Latin Hypercube Sampling,LHS)初始化k个样本,使用精确FEs对其进行适应度评估并添加到数据库DB中。此外,本算法根据可行性法则从DB中选择排名前m个样本作为初始种群,并更新算法所需参数,如全局最优(G

6.全局管理模型

本发明提出了一种新的不确定性准则：差距法则(Variance and Distance,VD)。该法则选择同时具有最大距离和最大差异的个体进行精确FEs：

VD

V

Dist

MaxDist

MinDist

Dist

其中，m和n分别表示种群个数和DB中样本个数。Vens表示集成代理模型中成员在预测同一个候选解时产生的分歧，当分歧越大说明该区域适应度景观复杂而不易近似。该算法选择最大不确定性进行评估有利于平滑该区域，防止搜索陷入局部最优。Disti

7.基于群体信任域的局部管理模型

已知单独执行全局搜索可能会减缓算法收敛速度，此外在有限FEs的情况下，其还可能会降低收敛精度。因此本发明在使用全局搜索快速帮助算法定位到有希望区域后，将采用局部搜索策略，使算法能够充分挖掘该区域，从而达到在进一步增强算法开发能力的同时提升收敛精度与速度的目的。局部搜索旨在从有希望的区域中搜索局部代理模型的最优解。那么，如何选择局部代理模型呢？如何定义有希望区域呢？基于何种筛选标准来选择最优候选解进行精确FEs呢？

为了解决该问题，本发明提出了一种将可行性法则与顶部平均信息相结合的顶部可行均值法则。首先，基于可行性法则对种群进行排序。然后，选择前t*100％个个体计算均值得到待评估的候选解C,其中t由用户指定。最后,利用精确FEs对其进行评估。该策略可以在充分利用每个维度所携带的有用信息的同时弥补可行性法则未充分利用不可行解所携带的有价值信息的不足,有效调节目标与约束之间的不平衡。本发明的研究动机可用以下例子进行说明。假设给定的a＝b＝1且x

8.计算复杂度

为了更好说明发明提出算法的计算复杂度,以下分析仅考虑算法中的一次迭代。本发明提出算法的计算成本主要是由构建全局代理模型、MSHSSA优化、执行差距准则、构建群体信任域、训练局部代理模型和执行顶部可行均值法则这六个部分组成。

训练RBF和PR模型的计算复杂度分别为O(N

由上述分析可知,本发明提出算法在一次迭代中的计算复杂度为O(N

以上所述，仅是本发明的较佳实施例而已，并非是对本发明作其它形式的限制，任何熟悉本专业的技术人员可能利用上述揭示的技术内容加以变更或改型为等同变化的等效实施例。但是凡是未脱离本发明技术方案内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与改型，仍属于本发明技术方案的保护范围。

本专利不局限于上述最佳实施方式，任何人在本专利的启示下都可以得出其它各种形式的一种求解昂贵约束优化问题的快速广义代理辅助进化方法，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本专利的涵盖范围。