| 标题 | Hilbert Curves for Efficient Exploratory Landscape Analysis Neighbourhood Sampling |
|---|---|
| 作者 | Johannes J. Pienaar, Anna S. Bosman, Katherine M. Malan |
| 机构 | Department of Computer Science, University of Pretoria, Pretoria, South Africa |
| 邮箱 | jpienaar85@gmail.com |
| 论文 | https://arxiv.org/abs/2408.00526 |
摘要
这篇论文主要讨论了一种利用希尔伯特曲线（Hilbert Curve）在探索性景观分析中进行高效邻域采样的方法。景观分析旨在通过优化问题的目标函数特性来描述搜索空间，通常通过采样并估算景观特征。该论文提出，传统的最近邻排序方法在高维空间中计算代价过高，因此建议使用希尔伯特曲线作为高效的替代方法。希尔伯特曲线不仅能保证搜索空间的均匀覆盖，还能生成空间上相关的采样序列。实验表明，与拉丁超立方采样相比，希尔伯特曲线能够在计算代价更低的情况下提取出显著特征，并且在样本排序时速度远超最近邻排序方法，且不牺牲提取特征的显著性。
Introduction
搜索景观分析已被证明是理解复杂优化问题并分析进化算法行为的有用方法。多年来，已经开发了许多景观分析技术，最常用的技术包括适应度距离相关性、本地最优网络和探索性景观分析（ELA）。当景观分析产生数值输出时，生成的特征向量可以作为问题实例的抽象表示，其中具有相似特征向量的实例被认为属于相似的问题类别。如果这些特征向量能有效捕捉问题的重要特征，它们可以用于自动化算法设计（AAD）——特别是自动化算法配置和选择。在特定上下文中，许多最近的研究已经在AAD的不同方面取得了进展。
景观分析方法在测量或预测内容（例如崎岖程度、多模态性、漏斗的存在等）方面有所不同，输出形式也有所不同（例如数值结果或现象的可视化）。它们还可以根据分析的规模进行区分——全球方法尝试描述整个搜索空间的特征，而局部方法则会考虑解邻域中的景观特征。
许多测量局部特征的景观分析技术基于空间相关的样本，即相邻解的序列，而不是从整个搜索空间中独立抽样的样本。需要此类样本解序列的技术包括用于测量崎岖度的相关长度、基于中性区域的崎岖度和平滑度的熵分布、梯度的近似值、信息内容特征以及中性的度量。
到目前为止，生成连续搜索空间中空间相关样本的两种主要策略是随机游走和全局样本的事后排序。用于估算局部特征的采样策略的理想属性是这些解提供良好的搜索空间覆盖率，连续点相对于样本中的其他解距离较近，以捕捉邻域中的景观变化，且过程具有较低的计算代价。用于数值优化的邻域采样的最常用方法是均匀随机采样或拉丁超立方采样（LHS），随后进行随机或最近邻排序。这些方法在flacco和pflacco中得到了实现。
希尔伯特曲线
填充曲线是一种从单位区间 到单位超立方体 的满射连续函数。满射性意味着超立方体中的每个点都映射到区间中的至少一个点，连续性确保 中没有区域被遗漏。填充曲线是分形曲线的一种特殊情况，保证在极限情况下填充连续空间。
我们对填充曲线的兴趣源于它们提供的两个有用属性：（1）在有限的 ddd 维空间中进行均匀覆盖的能力，以及（2）在 d 维空间中的点和 1 维曲线上的点之间提供唯一映射的能力。具体来说，本研究考虑了希尔伯特填充曲线，它由希尔伯特于1891年首次提出。希尔伯特曲线是递归定义的，可以通过迭代的极限过程来构建。每次连续迭代都会创建更接近真实希尔伯特曲线的近似，该曲线通过 d 维单位超立方体中的更多点。为了实际应用，迭代次数是有限的，称为希尔伯特曲线的阶数。
以2D中的希尔伯特曲线构建为例。在第一次迭代中，取闭区间 上的一条直线和正方形 ，并在线上选择四个等距点，起点为0，终点为1。将正方形划分为四个相等的部分，将线的每对相邻点的区间映射到正方形上，使得在线上相邻的区间在正方形上共享一个公共边。这会产生一个简单的U形，如图1(a)所示。在每次后续迭代中，将前一迭代的曲线划分为四个相等部分。然后，将每个部分按1/2的比例缩小，旋转并重新定位，使得四条曲线的端点以U形或反U形模式连接。图1展示了阶数为1到3的2D希尔伯特曲线。
希尔伯特曲线是双射的，即曲线上点与 d 维空间中的点之间的映射是可逆的。填充曲线的双射性在组织多维数据存储和检索系统中非常有用，因为它允许构建和搜索数据的线性索引。Faloutsos和Roseman研究了希尔伯特曲线与其他填充曲线的聚类特性，发现希尔伯特曲线在测量给定点到其最近邻居的平均距离（沿曲线）时表现更好。这一发现表明，希尔伯特曲线可能是替代最近邻排序的一种可行方
使用希尔伯特曲线作为采样工具
给定特定阶数的希尔伯特曲线，其顶点可以作为关联多维空间中样本的基础。表1展示了曲线阶数和搜索空间维度的不同组合下，顶点数量如何增长。在ELA采样中，通常使用样本规模为 到。表格中加粗的值显示了顶点数量超过常见样本预算的组合。为了保持采样预算，我们从阶数至少为3的希尔伯特曲线顶点中随机抽样。
3.1 使用希尔伯特曲线的随机采样
由于希尔伯特曲线的生成是确定性的，本研究评估了以下两种引入随机性的策略：
沿着希尔伯特曲线的边选择随机点：给定任意两个连续顶点和，选择新点，其中。 选择接近曲线顶点的点：对于每个顶点，生成一个以为中心、标准差为（受限于搜索空间边界）的正态分布新点。通过实验，步长为1，因此选择，以防止与邻近顶点生成的点过度重叠。
3.2 搜索空间覆盖率
我们接下来研究希尔伯特曲线采样与其他策略相比在搜索空间中的覆盖程度。通过三种不同的策略从搜索空间中抽取样本：
希尔伯特曲线：从曲线上随机选择所需数量的点（无替换）。 拉丁超立方采样（LHS）：使用拉丁超立方设计生成样本。 随机游走：使用最大步长为1的简单随机游走生成样本。
对于每个样本大小和维度组合，使用随机均匀样本作为参考集。计算每次采样策略的Hausdorff距离来衡量搜索空间的覆盖率。实验结果表明，希尔伯特曲线采样和LHS采样的Hausdorff距离相似，表明它们具有相似的搜索空间覆盖率，而随机游走的覆盖率最差。
3.3 计算代价
我们接下来比较了希尔伯特曲线与其他采样策略的计算成本。生成希尔伯特曲线样本虽然计算成本较高，但其在后续计算有序样本的景观特征时展示出显著的效率。信息内容度量计算实验显示，希尔伯特曲线采样在较大样本规模下明显快于LHS最近邻排序。
为了评估计算成本，使用了性能计时器来记录以下两方面的时间：(a) 生成样本，(b) 计算希尔伯特曲线和LHS的信息内容（information content）度量。通过pflacco库计算了COCO平台中定义的24个BBOB函数的信息内容（ic）度量。这是在表2中列出的每个维度和样本大小下进行的。需要注意的是，LHS要用于信息内容度量时，样本必须是有序的。我们评估了随机排序和最近邻排序策略。此外，pflacco库提供的信息内容函数被修改为接受none作为排序参数，以便使用预排序的希尔伯特曲线样本。
图4(a)显示，希尔伯特曲线采样器生成相同大小样本的速度比LHS要慢。尽管希尔伯特曲线采样器的计算成本似乎至少以二次方的方式增长，但即使对于大样本规模（如生成30,000个点样本仅需1.2秒左右），这一成本仍然是可以接受的。图4(b)显示，在信息内容度量方面，希尔伯特曲线采样策略比LHS的最近邻排序显著更快，尤其是在较大样本规模下。
希尔伯特曲线取样的预测性能
我们已经证明，希尔伯特曲线采样为从连续搜索空间生成空间相关的解序列提供了一种高效的方法，并且这些序列可以很好地覆盖搜索空间。现在我们研究从这些样本中提取的景观特征是否能够为算法选择提供良好的预测性能。
按照Muñoz等人的方法，我们将预测每个BBOB函数类别的任务作为算法选择的代理任务：如果问题实例的景观特征可以用于区分问题类别，那么它们也应该能够作为算法选择的有效预测变量。根据文献，BBOB函数按以下五个目标类别进行分组：(1) 可分离函数：{f1…f5}，(2) 低或中等条件数的函数：{f6…f9}，(3) 单峰函数和高条件数函数：{f10…f14}，(4) 具有适当全局结构的多峰函数：{f15…f19}，(5) 低或中等条件数的函数：{f20…f24}。
实验设置如下：使用维度 的24个BBOB函数，评估预算为 。每个BBOB函数有15个预定义实例，每个函数随机保留3个实例作为测试数据。对于每个实例和维度组合，从搜索空间 中抽取 个样本，使用三种采样策略：希尔伯特曲线（HC）、拉丁超立方体（LH）和随机游走（RW）。从pflacco包中选择了四个不需要进一步函数评估的特征集，分别是：分散度（disp）、ELA y分布（ela_distr）、ELA元模型（ela_meta）和信息内容（ic）。
表4给出了决策树、k近邻和随机森林分类器在根据景观特征预测函数类别任务中的测试精度。所有实例中使用了scikit-learn 1.1.3版本的默认设置。结果表明，随机森林模型在所有采样策略中是最有效的分类器。总体而言，RW策略表现最差，而希尔伯特曲线和拉丁超立方采样策略在所有三个分类器中表现相当。
表5展示了三种采样策略在四个特征集下的性能。一个可观察到的趋势是，ela_meta和ic特征非常显著，能够让分类器准确地区分函数类别，验证了Renau等人的研究结果。
总结
本文提出了在优化问题景观分析中使用希尔伯特填充曲线的两种应用：（1）用于生成空间相关且保证均匀覆盖的搜索空间样本，以及（2）用于对其他采样算法（如拉丁超立方体）生成的样本进行空间排序。实验评估了希尔伯特曲线的相对计算效率，以及通过希尔伯特曲线采样和排序提取的景观特征的显著性。就采样而言，希尔伯特曲线在生成与顺序敏感特征（如信息内容度量）相关的样本时，比拉丁超立方采样显著更快。通过希尔伯特曲线提取的特征能够有效区分问题类别，并允许成功的分类。作为一种排序工具，希尔伯特曲线的排序速度远超常用的最近邻排序，同时也能生成显著的景观特征。因此，希尔伯特曲线为景观分析中的拉丁超立方采样和样本的最近邻排序提供了可行且高效的替代方案。
