A fast surrogate-assisted PSO algorithm for computationally expensive proble 阅读笔记

PII: S1568-4946(20)30243-X
DOI

本文贡献

• 应用了两种准则纵向应用来挑选精确评估过的候选人

准则1：基于性能的准则（performance-based criterion）。
1.exploit当前的全局最优，并且加速收敛率。 每个粒子的轨迹都有很多速度和位置，用RBF来找到最小适应度值的位置（代表每个粒子都要计算，这是相当耗时的计算）
2.评价的是预测适应度值良好的个体。

准则2：基于不确定性的准则（uncertainty-based criterion）
1.为了提高代理模型的准确性，将搜索趋向局部（explore）,提高exploration的能力。不确定性指的是适应度估计的可靠性，可靠性估计的值与不确定性成负相关。fitness landscape越复杂，不确定性越大。
2.评价的是具有很大不确定性的个体。

• 提出了一种准则，考虑了距离和适应度信息，同时进行勘探和开发（弥补了原来SAESs中基于距离的不确定性里缺少考虑不同问题fitness landscape的不同导致不能在多个问题中使用的缺点。）

实验背景

以往的代理模型通过使用一些预先筛选（pre-screening）标准来帮助选择个体（promising）进行准确的评估，从而平衡exploration&exploitation，但是pre-screening不应该被单独使用，因为许多FEs过的个体都去用做explore了，所以很耗时。

• 只考虑预测适应度值的pre-screening会导致早熟收敛（premature convergence）
• 只考虑不确定性的pre-screening会导致低收敛率（slow convergence rate）
• 因此两种准则都不能单独使用。
• 但是同时考虑预测适应度值和不确定性的预筛选准则难以确定准确评估个体数(Ns)，该值太大或太小都会让许多FEs去探索search space。

本文工作（FASPSO）

在代理辅助粒子群优化算法中，协同使用基于性能的准则和基于不确定性的准则，通过少量的有限元法来解决中等规模的计算代价较高的问题

两种准则只选择适合度值最好或不确定度最大的个体进行准确评价，以减少FEs的消耗

• The performance-based criterion is used to exploit the current global best
• The uncertainty-based criterion is used to enhance the exploration of the algorithm

该算法利用基于性能的准则，可以快速地挖掘当前有潜力的区域，同时利用基于不确定性的准则，降低了陷入局部最优的概率。

通过同时考虑距离和适应度值信息，提出了一个估计不确定性的准则。该准则通过考虑问题的适应度景观（fitness landscape），弥补了传统的基于距离的不确定性准则的不足，可以用到任意SAEAs上面。

本文主要贡献

1. 本文提出的FSAPSO算法使用两种标准来选择准确的FEs个体。基于性能的判别准则可以促进勘探，加快收敛速度，而基于不确定性的判别准则可以促进勘探，缓解过早停滞。

2. 提出了一种同时考虑距离和适应度值信息的基于不确定性的判据。通过考虑问题的适应度景观，弥补了传统基于距离的不确定性准则的缺点。

FSAPSO算法详解

• 基于性能的准则：在每次迭代时，精确评估拟合值最优的粒子和代理模型最优的粒子，控制粒子群的搜索方向。
• 基于不确定性的准则：选择不确定性最大的粒子进行精确评价，增强了算法的探索性。
• 一般情况下，不确定性较大的粒子只能对当前群体的全局最优做出微小的改进。如果每次迭代都准确地计算不确定度最大的粒子，可能会浪费一些FEs。只有在不改进当前群的全局最优时，才能准确地评估不确定性最大的粒子

CAL-SAPSO：和传统的代理辅助PSO的区别是增加了committee-based active learning 。

• FSAPSO算法使用两种准则从群体中选择粒子进行精确的FEs，而CAL-SAPSO主要工作是寻找符合这两种准则的模型的最优值。因此，CAL-SAPSO看起来像是一种基于代理模型的全局优化算法，而FSAPSO是一种代理辅助的粒子群优化算法。
• 其次，CAL-SAPSO使用多个代理模型预测的差异来估计不确定性，FSAPSO使用距离和适应度值信息来估计不确定性。

步骤：

1. 初始样本点设计：用拉丁超立方找样本点，用真值函数计算初始样本值，存在DB里面
2. 初始种群设计：从初始样本点中挑选N个适应度值最好的点，确定出PSO需要的速度、每个例子的最佳状态、粒子群的全局最佳
3. 用所有样本点建立初始RBF模型，找到模型的最小值： x m i n R B F xmin_{RBF} xminRBF​，判断当 x m i n R B F xmin_{RBF} xminRBF​与其他评估样本的最小距离大于阈值（ η \eta η）时，评估 x m i n R B F xmin_{RBF} xminRBF​（计算真值）并将其添加到数据库（DB）中，计数NFEs，并更新粒子群的全局最好解，这样就能准确地评价该RBF模型的最优性。（采用阈值分割方法避免样本过于靠近）
4. 对于N个样本点：更新速度和位置
5. 利用RBF模型预测粒子的适应度值: p r e pre pre
6. 找到 p r e pre pre最小值的粒子，将其命名为粒子 i i i
7. 计算粒子 i i i与DB中其他样本点的最小距离： d x dx dx，判断当 d x dx dx与其他评估样本的最小距离大于阈值（ η \eta η）时，用精确函数评估粒子 i i i，记作 f p o p 1 = f ( p o p i ) fpop_{1}=f(pop_{i}) fpop1​=f(popi​)，并将其作为新样本点添加到DB中，计数NFEs，并更新粒子 i i i的个人最好位置，和粒子群的全局最好解
8. 如果全局最佳解没有提升，找到粒子群不确定性最大的地方，将其命名为粒子 i i i，用精确函数评估粒子 i i i，记作 f p o p 1 = f ( p o p i ) fpop_{1}=f(pop_{i}) fpop1​=f(popi​)，并将其作为新样本点添加到DB中，计数NFEs，并更新粒子 i i i的个人最好位置，和粒子群的全局最好解
   

模型管理

当最优值较优时，精确地评估 R B F RBF RBF模型的最优值来更新粒子群的全局最优值（ o p t i m u m optimum optimum）。

提出的基于不确定性的准则（The proposed uncertainty-based criterion）

作者在文中提出了三种情况

1. 如果样本点的离散度差不多，那么复杂的适应度地形就会有更大的不确定性（因为他们更难以找近似）
2. 如果整个空间的景观的复杂性是相似的，接近评估过的点的候选点就会有相似的不确定性（因为离他最近的样本点会有很大的影响）
3. 和第二种情况差不多，一个候选点的不确定性通常会随着其相邻点的取值而减小，

总结：不确定性受问题的适应度景观、候选对象到离其最近评估点的距离以及最近评估点的数量的影响。
传统的距离准则只考虑候选点与被评估邻近点之间的距离，因此预测的不确定性可能不可靠

相比于传统的距离准则，在本文中增加了适应度值的信息，命名为 D F DF DF准则。

如上图所示，
（a）表示四个样本点均匀分布在[0,1]的一维Forrester函数克里格模型，
（b）表示候选点到样本点的最小距离( d m i n dmin dmin)、候选点的DF值和克里格法预测的MSE

• 可以看出， d m i n dmin dmin准则只与样本点的分布有关，而DF准则可以反映景观的复杂性

dmin判据只考虑到最近邻的距离，所以峰值只与距离有关。DF准则也考虑了适应度值，因此适应度值方差较大的区域在样本点分布相似的情况下往往具有较大的不确定性。

解释上图：
在高维搜索空间中，在算法初始阶段，样本稀疏分布在搜索空间中。粒子与最近样本之间的距离相对较大。
如果最近的距离很大，适应度值的方差可能不能表示候选人所在区域的真实适应度景观。在这种情况下，粒子可能都有很大的不确定性，因为代理模型显然在任何地方都不准确，所以
DF准则也可以用来选择不确定度最大的候选对象。
随着迭代的进行，在群存在的区域会有更多的评估点。粒子之间的距离最近的样本逐渐变小。
适应度值的方差是可靠的，DF准则能够识别出最不确定的候选人。