多精度优化

2018-11-23 本文已影响0人 Hello_Star

Wang, Handing, Yaochu Jin, and John Doherty. "A Generic Test Suite for Evolutionary Multi-Fidelity Optimization." IEEE Transactions on Evolutionary Computation (2017). Doi: 10.1109/TEVC.2017.2758360

很多实际优化问题的解的适应度评价涉及很复杂的运算，十分耗时。但评价的精度往往是可以控制的，精度越高，对解的评价就越准确，但计算代价就越高。反之，则评价误差越大，但计算代价低。因此就衍生出了多精度优化。

根据这篇文章的叙述，目前针对多精度进化优化的研究还不是很多，为了促进这方面的研究，作者在文章中设计了三组多精度测试集，用来模拟实际的多精度优化问题。同时作者提供了基于PSO算法的实验结果。

文章要点：

1. 设计原则

在设计测试集时，主要的原则是在真实的评价函数 $f(x)$ 基础上增加误差 $e(x,\phi)$ ，得到的测试函数输出为 $\tilde{f}(x,\phi )$ 。所以设计不同的测试集就转变为设计不同的误差函数了。

$\tilde{f}(x,\phi ) =f(x)+e(x,\phi)$

2. 误差及误差函数设计

在对实际问题的解进行模拟（评价）时可能会有各种各样的误差，作者总结除了一下三种误差，同时所提出的测试集的差别在于包含这三种不同的误差。

Resolution errors（精度误差）可以理解为对真实的适应度曲线模拟得有一定误差，不同精度下的模拟适应度曲线中的全局最优和局部最优可能和真实的最优解有一定距离。像下图那样。

精度为1000时的适应度曲线和真实的（精度为10000）时还是有不小的差距的。

Stochastic（随机误差）可以理解为在每次评价中加入随机扰动，在文章中，作者加入了高斯噪声。

Instability （不稳定误差）可以理解为以一定概率让解的评价失败，作者通过以一定概率让误差函数的值无限大（相对于真实的适应度值来说无限大，其实不是无限大，作者使用了 $l=10d$ ，其中d是变量的维度）。

作者针对上面的三种误差总共设计了13个测试函数，作者在解空间采样了10000解，分别计算了在不同精度下的目标函数值，并且计算了与真实目标函数值之间的皮尔逊相关系数(Pearson correlation coefficient)和RMSE来解释不同精度下的评价函数和真实精度的评价函数值之间的相关性。

3. 优化方法

测试集设计好了，应该怎么去求解这类多精度的问题呢。其实质是不同精度的目标函数该怎么使用的问题。使用最高精度的评价函数很耗时，使用最低精度的评价函数虽然会很快，但是求解精度很差，所以作者设计了三种精度调节策略，算法框架使用了PSO。

1）基于代数的调整策略

该策略需要对每一代种群评价其收敛性 $M_{c}$ 和多样性 $M_{d}$ ，然后用这两个值 $s=(M_{c} ,M_{d} )$ 作为比较支配关系的指标去和之前所有代中积累下来的非支配解集 $S$ 作比较。若 $s$ 支配 $S$ 中的某些值，则去掉 $S$ 中被 $s$ 支配的值，且将代价累加变量 $C_{deg}$ 置0。否则将该代的计算代价累加到 $C_{deg}$ 中，且将 $s$ 加入 $S$ 。当 $C_{deg}$ 的值达到设定的阈值时，将精度等级调高一级。直到达到最高等级。

2）基于个体的调整策略

该策略的主要思想为：将两个解 $x_{1}$ 和 $x_{2}$ 的目标函数的差 $\Delta =|\tilde{f} (x_{1},\phi )-\tilde{f} (x_{2},\phi )|$ 转换为将这两个解错误排序的概率。作者在文章中使用了logistic回归模型（即logisti函数）来计算此概率。计算方式如下

$LR^\phi(\Delta ) =\frac{1}{1-e^-(\beta _{0}+\beta _{1}\Delta ) }$

优化过程为：首先，在每一代的优化中都使用最低级别的精度去评价个体；之后，在更新个体最优(personal best)和全局最优（global best）时估计两个解的 $LR^\phi(\Delta )$ 值，若超过设定的阈值（0.05），则使用更高的精度 $\phi$ 重新计算 $LR^\phi(\Delta )$ 值，若仍大于阈值，则直接使用最高级别的精度来更新个体最优和全局最优。

3）混合调整策略

将1）和2）混合。

4. 实验

参数设置：种群大小为50，独立实验 30次，算法停止准则为运算代价达到5e-09（这么低吗？）。13个测试集中有的函数的精度等级是[0,10000]，有的是[0,10000]之间的若干值。通过实验，作者将精度等级取值范围为[0, 10000]的函数的精度等级划分为11个等级。最终的实验结果如下。

其中PSO表示用最高等级精度的目标函数来优化，PSO-AFAg，PSO-AFAi，及PSO-AFAh分别表示基于代、个体和混合调整策略，GOEME为一个代理模型算法。

从实验结果可以看出PSO-AFAh的性能最好，PSO-AFAg次之。奇怪的是使用最高精度评价函数的PSO结果居然比不过前三种算法，考虑到停止准则是计算代价达到一定阈值，也就可以理解了。用最高精度的评价函数的计算代价肯定很高，所以在相同的计算代价条件下，使用动态调整评价函数精度的策略能使得算法收敛得更快。同时，低精度的评价函数虽然和真实的（或者高精度的）评价函数之间有误差，但是也能帮助算法向最优解收敛。

5. 总结

作者最后指出了几条将来的研究方向：1. 文章中所提出的测试集能在多大程度上模拟真实的情况；2. 文中所提出的调整策略没有考虑代理模型；3. 不同精度的目标函数之间的关系需要深入研究，以提出更有效的调整策略；4. 目前还没有合适的评价方法来对比不同的多精度优化算法；5. 多精度测试集以及多精度优化算法的研究还需深入。

6. 感受

读好文章可以一口气读到参考文献，没有晦涩难懂的表述，也没有复杂的公式。读得过程中心中产生的每一个疑问都能在文章中得到解答，仿佛作者知道读者会产生哪些疑问，继而很恰到好处地帮读者解开心中的疑惑。惊叹作者思路之缜密，设计之精妙，表述之简洁。是为榜样！