优化 | 全局收敛的机器学习赋能演化计算搜索框架

↑↑↑↑↑点击上方蓝色字关注我们！

原文信息:

Li B, Wei Z, Wu J, et al. Machine learning-enabled globally guaranteed evolutionary computation[J]. Nature Machine Intelligence, 2023, 5(4): 457-467.

编者按

演化算法（Evolutionary Algorithm, EA）在求解复杂实际问题时能给出满意解，然而，其缺乏通用且可靠的能收敛至全局最优解的理论保障掣肘其进一步发展。究其因是EA自身缺乏：（1）对问题决策空间的统一表征，以及（2）逃离局部最优解的机制。本次荐读的文献中，作者分别针对这两个问题提出有效的机制：（1）通过机器学习中的低秩表征学习技术与少量的结构化决策空间采样点，构建出对问题决策空间的近似表征；以及（2）在一些前提与假设下，在近似低秩表征决策空间中，基于距离指标识别出注意力子空间，并采用粒子群算法在子空间内搜索。此外，作者融合上述两种机制搭建出通用且可靠的EVOLER搜索框架。本文首先介绍研究动机，然后描述背景知识，之后介绍决策空间低秩表征方法，以及在低秩表征决策空间中识别注意力子空间并做搜索的机制，最后描述了EVOLER框架能以概率收敛至全局最优解的证明过程。

研究动机

优化问题可以建模为下述形式：

其中，为维决策变量，为待求解的目标函数，为约束条件，为欧氏空间，为变量的上下界。我们可以通过采样变量的值使用EA算法求解。

一个EA常常仅在具有某种特性的优化问题中求解效果好，故需要提出很多EAs来应对不同特性的优化问题，但是，很多EAs难以保证计算出的解是问题的全局最优解，因此，EA需提升其通用与可靠性。为此，文献[3]认为是现有EAs缺乏对问题决策空间的统一表征，以及基于该表征空间的针对性搜索才导致其缺乏通用与可靠性，并提出了EVOLER搜索框架来解决该问题。EVOLER框架如下图所示，它能通过改进的低秩学习方法来表征问题的决策空间，并识别出值得搜索的子区域（原文称为attention subspace，下文译为注意力子空间），在对比实验部分，该框架表现优越。

EVOLER框架，首先对问题决策空间进行低秩表征，然后在子空间内采用PSO搜索（图源本次荐读的文献[3]）

背景知识

为了更好的理解论文中的创新点，本节将介绍文献[3]中所提出的低秩表征技术中使用到的矩阵分解方法，以及在子空间内进行搜索的粒子群算法。

1. 矩阵分解方法

如果一个矩阵具有低秩结构，那么我们可以通过矩阵近似方法求得一个低秩的近似矩阵，使得能加速与有关的矩阵计算。下述2种矩阵近似分解法应用于文献[3]中的空间近似表征技术中：

上述方法的共性是：先对原始空间进行采样，然后进行低秩近似。在本文中，假设问题是2维的，对于变量两个维度分别进行和密度的离散化可以得到个网格点，对应的方程输出为，然后在此空间中进行采样，并基于这些采样点，通过上述矩阵分解法构建出一个与近似的矩阵，再通过求解矩阵来近似求解原问题，从而高效求解该优化问题。

2. 粒子群算法（Particle Swarm Optimization, PSO）[2]

经典PSO作为一种群智能优化算法，其流程图如下：

以2维单目标优化问题为例，可视化粒子群搜索过程如下：

（此图由Ephramac制作，源文件戳👉 粒子群搜索动画 https://commons.wikimedia.org/wiki/File:ParticleSwarmArrowsAnimation.gif）

论文创新点

1. 低秩表征学习方法

假设待求解的问题是秩约束问题且能被低秩表征。

以2维的问题决策空间为例，文献[3]提出的低秩表征学习方法流程如下：

在原始空间进行网格化采样。
每一维随机选取行（列），构建出2个子矩阵：.
使用随机矩阵近似方法[4-7]处理上述矩阵得到：
是计算最小化残差误差得到的。
为了衡量表征的与原空间的近似程度，需要得到残差的上限。原文中假设残差矩阵中每个元素服从长尾-稳定分布，得到残差矩阵的上界可以表征为，是的第个奇异值，是常数。
识别注意力子空间。
文章证明精确近似于原空间，故中1个注意力空间含有的1个全局最优解是原问题的1个全局最优解。
注意力子空间的定义如下：
其中，常数项与步骤1的网格化采样相关：

综上，该流程分为下图所示3部分：

对原始决策空间的低秩表征学习方法（图源文献[3]）

PSO在注意力子空间内以概率收敛至全局最优解的收敛性证明

粒子群的初始化是限制在内。基于前述的残差表示，算法可靠性的证明过程分为3部分：

算法找到中的全局最优解是原空间局部最优解的概率。
a. 无残差情况下，，中的全局最优解不是原空间的局部最优解。
b. 残差非零情况下，假设原空间是秩约束问题，借助双参数的柯西-高斯混合（Cauchy-Gaussian Mixture, CGM）分布是用来近似-稳定分布密度。
得到该概率为：
其中，为Frobenius范数。
粒子群初始化在含全局最优解的吸引域内的概率。
假设全局最优解所在的吸引域是单模态的。
得到概率为：
找到全局最优解的概率。
粒子群在中演化代后找到全局最优解的概率可以表示为：
而说明全局最优解无法被粒子群搜到，故：
根据文献[8]中得到的结论：PSO 算法将以概率 1 收敛到该局部子空间的最优值，得到：

结论

为了改善EA在求解优化问题中存在缺乏通用性和可靠性的情况，文献[3]提出了EVOLER 搜索框架，它通过改进的低秩表征学习方法学得问题决策空间的表征空间，然后基于此表征空间识别出注意力子空间，并于其中进行启发式搜索。它在理论层面能找到全局最优解，克服了基于数据驱动的黑箱方法中的不确定性。然而，在求解不具有低秩结构或者决策空间维度较高的优化问题时，该搜索框架尚存在性能提升空间。

参考文献：

[1]Drineas P, Mahoney M W, Muthukrishnan S. Relative-error CUR matrix decompositions[J]. SIAM Journal on Matrix Analysis and Applications, 2008, 30(2): 844-881.

[2]Kennedy J, Eberhart R. Particle swarm optimization[C]//Proceedings of ICNN'95-international conference on neural networks. ieee, 1995, 4: 1942-1948.

[3]Li B, Wei Z, Wu J, et al. Machine learning-enabled globally guaranteed evolutionary computation[J]. Nature Machine Intelligence, 2023, 5(4): 457-467.

[4]Drineas P, Mahoney M W, Muthukrishnan S. Relative-error CUR matrix decompositions[J]. SIAM Journal on Matrix Analysis and Applications, 2008, 30(2): 844-881.

[5]Wang S, Zhang Z. Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling[J]. The Journal of Machine Learning Research, 2013, 14(1): 2729-2769.

[6]Li B, Chen P, Liu H, et al. Random sketch learning for deep neural networks in edge computing[J]. Nature Computational Science, 2021, 1(3): 221-228.

[7]Liu H, Wei Z, Zhang H, et al. Tiny machine learning (tiny-ml) for efficient channel estimation and signal detection[J]. IEEE Transactions on Vehicular Technology, 2022, 71(6): 6795-6800.

[8]Van den Bergh F, Engelbrecht A P. A convergence proof for the particle swarm optimiser[J]. Fundamenta Informaticae, 2010, 105(4): 341-374.

微信公众号后台回复

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

文章须知

责任编辑：胡明杰陈宇文

微信编辑：疑疑

文章由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知

关注我们