Model-based evolutionary algorithms: a short survey 阅读笔记

Model-based evolutionary algorithms: a short survey

1、摘要

本综述通过探讨使用模型的不同动机，并对若干具有代表性的MBEAs进行了系统梳理。

第一，使用模型最常见的动机是估计候选解的分布。

在进化多目标优化过程中, 所用模型的主要目的之一是构建从目标空间到决策空间的逆模型.

第三，当解决计算量大的问题时，模型可以作为适应度函数的替代品。

2、引言

基于MBEAs的方法采用[机器学习模型]来取代传统操作算子，在每一代中都从当前环境抽取样本作为训练数据的来源。

为了实现不同目标的适应性需求，在EAs的主要组件中（即复制机制、适应度评估机制及选择策略）中均可集成机器学习技术。具体而言，在这些核心机制中都可以集成特定类型的机器学习模型以增强其性能。具体而言，在复制机制中可应用回归类算法（如高斯过程回归和人工神经网络），在适应度评估机制中可应用聚类算法（包括K均值聚类算法等），在选择策略中可应用分类算法（如支持向量机算法）。此外，在优化过程中还可以结合降维技术（例如主成分分析方法），以进一步提升计算效率和优化效果。

考虑到众多技术细节的影响，我们通过细致观察发现，在演化算法（EAs）中应用机器学习（ML）模型的主要驱动力体现在以下几个方面：首先，在决策空间中构建估计函数；其次，通过替代性地构建逆映射实现目标空间到决策空间的映射；最后，在适应度计算层面进行替代性设计以取代传统方法。

分布估计（Estimation of distribution）旨在通过分析决策空间中的数据来估算概率分布。
逆模型（Inverse modeling）用于建立从目标空间到决策空间的对应关系。
代理模型（Surrogate modeling）被用来为适应度函数构建精确且高效的替代品。

3、分布估计

分布估计算法(EDAs)是指基于训练模型以及抽样机制，在解空间中识别潜在优越解集的空间分布的一种优化方法。

如图所示的算法1中所示

为了将PF近似转换为MOP问题, 传统MEDAs通常依赖于新的选择算子来平衡候选解的收敛性和多样性. 与许多MEDAs采用新的选择算子不同, 基于规则模型的多目标估计分布算法(RM-MEDA)采用了新型繁殖算子[33]. 由于在KKT最优性条件下的正则性, PS被定义为分段连续流形, RM-MEDA通过局部PCA方法降低了决策向量的空间维度, 进而从潜在空间中生成新的候选解样本.

以...为例，在过去十年中EDAs展现了显著的进步。一种显著的优势在于能够适应性地应对适应度环境并解析学习问题结构。对于具有某些特定特性的优化问题而言，在这种情况下这非常有益。然而，在面对某些复杂情况时仍需进一步探索和完善相关机制。

从机器学习角度来看，在实际操作中构建机器学习模型往往需要更多的时间资源。相较于基于传统启发式算法的方法（例如两点交叉法）而言，在实际应用中我们需要对采用基于进化算法的启发式方法的计算开销进行合理的评估和权衡。这可能只是出于提高性能指标的目的所作的一种权衡。

其次，在大多数情况下（即候选方案对模型进行充分训练），EDAs面临严格的限制条件。然而，在优化过程中难以确保这些条件得到满足的情况下（即模型经过充分训练后仍可能存在不足），这可能导致其性能下降。

从通常情况来看，在面对高维度问题时，多数现代演化算法（EDAs）都会遭遇严重的问题。当决策变量数量显著增加时，在现有技术条件下难以有效应用机器学习模型来优化这些参数。这种局限性严重影响了其在实际应用中的鲁棒性和通用性。

第四点，在EDAs中对决策空间的分布估计给予重视的同时，并未对决策变量之间的关联性给予足够的关注。通过将EDA与[CMA]相结合的方式，在提取和利用统计信息的基础上显著提升了收敛速度的研究路径具有重要的研究价值。

4、逆模型

如图所示，在决策空间中获得的均匀分布解集未必能保证其图像集在PF上呈现均匀分布特征。为了直接调控候选解在帕累托前沿（PF）上的分布情况，在现有研究中通常采取以下方法：首先，在决策空间中生成一系列采样点集合；然后通过建立逆模型映射关系将这些候选解映射回决策空间区域。

考虑一个具有[MOP](Multi-objective Optimization Problem)特性的数学问题f(x)。逆向建模的过程涉及将目标空间中的点映射回决策空间中的点，并通过方程g(f(x))=x来描述这一关系。其中函数g(\cdot)被定义为从目标空间到决策空间的逆映射函数。严格而言，在这种情况下只有在函数g(\cdot)能够实现PF与PS之间一一对应的条件下才能实现精确建模；然而，在实际应用中即便上述理论条件无法完全满足我们仍然能够通过近似方法有效地进行建模工作；从机器学习的方法论角度来看构建这样的逆模型h(\cdot)=\text{argmin}_{y\in X}\|f(y)-t\|确实构成了一个典型的回归任务

程然所提出的多目标优化算法[IM-MOEA]采用基于高斯过程的逆建模方法，并将其整合到复制算子中用于生成新的候选解。具体内容暂不详细说明，请参考原文获取更多信息。

EDA主要致力于在决策空间中估算分布情况，并通过构建连接目标与决策空间的模型来实现这一过程。在处理多目标优化问题时，则特别适合构建相应的逆模型。然而，在当前的研究进展中可以看出，在这一领域仍然存在诸多未解之谜

首先，逆建模假设了目标空间至决策空间的一一对应关系。然而，在实际应用中，单个目标向量通常会对应多个可能的决策向量。针对此类问题，我们特别关注如何构建更具鲁棒性的逆模型。

第二部分类似多数其他MBEA,都受到了维度灾难的影响,该问题可分为两个主要方面:一方面,当涉及大量变量时,GP等机器学习方法可能导致计算时间过长;另一方面,构建逆模型所需的数据量随着变量数量呈现指数级增长,然而由于实际的人口数量和适应度评估资源受限,这方面的数据供应往往难以满足需求

5、代理模型

与其他两种类型的MBEAs不同，SAEAs的提出是为了解决昂贵的优化问题。

（暂略~）

6、总结

基于机器学习的视角而言

一方面，在适应度值的基础上构建训练数据集，并基于此逐步构建并持续更新学习模型；另一方面，则从模型中进行多次迭代采样，并从而生成候选解用于模拟再现过程。

由此可知，在采用恰当的候选方案进行模型训练方面存在较高的价值，在这一领域仍有许多值得深入探讨的问题。