基于最优传输的海上风电场布局置换不变贝叶斯优化

# 基于最优运输的排列不变贝叶斯优化在海上风电场布局中的应用  
来源：https://arxiv.org/html/2606.00009  

1]\\orgdiv经济、管理与统计系，\\orgname米兰比可卡大学，\\city米兰，\\country意大利  
2]\\orgdiv工业工程与创新科学系，\\orgname埃因霍温理工大学，\\city埃因霍温，\\country荷兰  
3]\\orgname埃因霍温人工智能系统研究所，\\city埃因霍温，\\country荷兰  

###### 摘要  
贝叶斯优化（BO）被广泛且成功地用于解决具有昂贵评估、黑箱和非凸目标函数的优化问题。然而，标准BO算法无法利用目标问题可能存在的对称性。一个直观的例子是最优位置问题，其决策变量指连续空间中的有限点集，且点的顺序不影响目标函数的值。我们将这种设置称为**布局优化**，以区别于**点云优化**（后者中点的顺序很重要）。作为布局优化的一个实例，我们考虑一个实际工业相关应用——海上风电场布局优化：给定相同的风力涡轮机，任意交换一对涡轮机对年发电量没有任何影响。基于最优运输理论，我们提出了一种排列不变的BO方法，即PIBO。实验证明，与标准BO方法相比，PIBO能够提供更好的风电场布局，同时计算时间大约减半。  

###### 关键词：贝叶斯优化，排列不变性，海上风电场布局优化  

## 1 引言  

### 1.1 问题陈述与动机  
本文解决的是黑箱、昂贵评估、非凸函数在**布局**上的全局优化问题。所谓**布局**，指的是一个点云，其中点的排列不影响目标函数的值。更一般的定义可以是**排列不变**优化，即目标函数不依赖于其输入或输入子集的任何排列。在不失一般性的前提下，我们仍倾向于引入“布局”这一术语，因为它与本文考虑的具体应用（以及许多其他实际应用）更为一致，但也将“排列不变”作为同义词使用。从实践角度看，许多涉及连续空间中最优放置的实际应用都符合所提出的形式，例如环境监测中的传感器放置\[Hellan2023BayesianOA\]、碳捕集与封存中的井位放置\[Fotias2024OptimizationOW\]、集成电路设计\[Deshwal2021BayesianOO\]以及风电场布局优化\[EXPObench\]。  

设 \(P \in \mathbb{R}^{m \times d}\) 表示一个**点云**，包含 \(d\) 维空间中的 \(m\) 个点（例如，一组 \(m\) 个传感器、井、泵等），并设 \(f: \Omega \subset \mathbb{R}^{m \times d} \rightarrow \mathbb{R}\) 为待最大化的评分函数。优化**点云**意味着求解：  

\[
\max_{P \in \Omega \subset \mathbb{R}^{m \times d}} f(P) \quad (1)
\]

一个简单的方法是考虑点云的**向量化** \(\varphi: \Omega \rightarrow \Omega_v \subset \mathbb{R}^{md}\)，并求解以下变换后的问题：  

\[
\max_{v_P \in \Omega_v \subset \mathbb{R}^{md}} f(\varphi^{-1}(v_P)) \quad (2)
\]

其中 \(\varphi^{-1}(v_P)\) 表示向量化的逆。这假设了点云中点的顺序——即 \(P\) 中的行顺序和 \(v_P\) 中的坐标顺序——是重要的。然而，如果顺序不重要（如上述应用），则 \(\forall P \in \Omega, f(P) = f(\varsigma(P))\)，其中 \(\varsigma(P)\) 表示 \(P\) 的行的任意排列。这是严重的，因为即使目标问题只有一个全局最优布局，公式 (1) 和 (2) 也会有 \(m!\)（即 \(m\) 的阶乘）个全局最优。这种不期望的“复制机制”不仅影响全局最优，还会影响每一个可能的解，导致 \(f\) 被局部（和全局）最优“污染”，而这些最优来自于真正底层函数（该函数定义在布局上）的复制。由于假设 \(f\) 是黑箱、昂贵评估且非凸的，贝叶斯优化（BO）\[archetti2019bayesian, garnett2023bayesian\] 是解决该问题的最佳选择，但上述复制机制可能严重阻碍标准BO快速收敛到最优解。此外，如果可行域是典型的有界盒子搜索空间 \(\Omega\) 的子区域（对于**约束BO**来说正是如此），我们会发现 \(f\) 变得更加复杂，复制还会影响可行域。为简单起见，这里介绍一个 \(m=2\) 且 \(d=1\) 的例子。目的是在1维空间中寻找一对点，使得函数 \(f\) 最小化，且满足 \(f(x_1, x_2) = f(x_2, x_1)\)。在此例中，我们通过著名的Bird测试函数得到 \(f\)。图1（https://arxiv.org/html/2606.00009#S1.F1）展示了：左侧是原始的2维Bird函数（符号取反以考虑最大化而非最小化，搜索空间缩放到 \([0,1]^2\)），右侧是我们的函数 \(f\)。显然，对角线以上的函数是对角线以下函数的复制，因此原始Bird函数的两个全局最优也被复制，导致我们的函数 \(f\) 有四个全局最优。当然，也可以考虑只复制对角线以上的函数，但那样会丢失原始Bird函数的全局最优，导致示例无意义。虽然人们可能认为更多的全局最优意味着更多找到其中一个的机会，但事实并非如此，因为复制机制可能导致 \(f\) 极其“波动”，全局最优变成“大海捞针”，这是已知的阻碍BO收敛的条件\[bull2011convergence, wang2014theoretical, wabersich2016advancing, berkenkamp2019no, candelieri2024mle\]。当然，所举的例子相当简单，但它应有助于理解 \((m \times d)\) 维函数中发生的情况更难想象。

请参阅图注。  
请参阅图注。  

图1：一个简单的不期望复制示例：左侧是Bird测试函数（搜索空间缩放到 \([0,1]^2\)，符号取反以考虑最大化）；右侧是通过将原始Bird函数从对角线以下镜像到以上得到的布局函数（即排列不变函数，满足 \(f(x_1, x_2) = f(x_2, x_1)\)）。尽管真正的布局函数只是对角线以下的部分，仅有2个全局最优，但如公式1和公式2那样优化点云会导致考虑一个有4个全局最优的函数（即复制机制）。

### 1.2 主要贡献  
我们利用最优运输（OT）理论实现了一种排列不变的BO方法，称为PIBO。基本思想是将每个点云与一个参考点云（在搜索空间外适当采样）关联，并计算从参考到表示候选解的特定点云的最优运输。在一定的假设下，OT理论确保每个参考点唯一（或几乎唯一）地与候选解的一个点相关联，并且这种关联可以用一个**流**（即一个向量）来表示。实际上，BO将应用在这个**流空间**上，并且给定参考点云，任何流都可以变换为布局（而非点云），从而保证排列不变性。本文的主要贡献可总结如下：  

- • 我们提出了一种基于OT理论的排列不变BO方法，称为PIBO，用于解决连续空间中点云的优化问题，但其中点的顺序不重要。实际上，我们将其称为布局优化；  
- • 我们在一个实际相关应用——海上风电场布局优化上评估了PIBO；  
- • 我们通过实验证明，PIBO在目标函数的最优值和计算效率方面优于其他非排列不变的BO算法。  

### 1.3 相关工作  
BO中的排列不变性此前已被考虑过，通常是在组合优化的BO背景下，因为排列在路由、规划和调度等大量组合优化问题中很常见。在\[Deshwal2021BayesianOO\]中，高斯过程（GP）中使用的标准核被调整为两种不同的核：Kendall核和Mallows核，两者都考虑了排列。对于Kendall核，采集函数优化问题被建模为二次分配问题，并使用半定规划求解。对于Mallows核，使用考虑排列的局部搜索启发式算法优化采集函数。在\[Irurozki2021UnbalancedMM\]中，类似的核被用于不平衡的Mallows模型，并结合Borda排序算法。相同模型后来被应用于小行星路由问题\[LopezIbanez2022TheAR\]。Xie2025FromSA将这些核扩展到高维设置，使用Merge核将核的计算复杂度从 \(O(n^2)\) 降低到 \(O(n \log n)\)。  

最优运输理论也曾被用于神经架构搜索的BO中\[Kandasamy2018NeuralAS\]，其中使用类似于推土机距离或Wasserstein距离的度量来优化神经网络布局。  

以上工作都考虑了纯粹的组合优化问题，如旅行商问题或二次分配问题，或其他路由或调度问题。相比之下，有一些工作考虑了排列不变的情况，其中点之间的关系是连续的，但这些工作中可能的位置数量仍然是有限或离散的。在\[Garnett2010BayesianOF\]中，解决了一个传感器集选择问题，其中传感器可以根据一组有限的可能位置放置。尽管组合搜索空间超过200万种可能性，但这仍然不同于纯粹的连续问题。他们的解决方案基于推土机距离（与Wasserstein或Mallows距离相关），并使用匈牙利算法求解相关的线性规划。类似的环境监测传感器放置问题在\[Hellan2023BayesianOA\]中提出，作者提供了一个基于真实空气污染数据的问题生成器，具有2D空间中的有限可能位置集。  

或许与我们的工作更相似的是Fotias2024OptimizationOW关于碳捕集与封存的井位放置工作。虽然点之间的关系像传感器放置问题一样是连续的，但该工作将搜索空间离散化为网格单元。他们计算所有单元格到原点的距离（在该问题中每个单元格唯一），并使用此距离得到一个分配形式的线性规划，并用匈牙利算法求解。他们还考虑了需要放置两种不同类型物体的情况，使问题进一步复杂化。  

此外，连续空间中的排列不变性也是深度学习（DL）中的一个具有挑战性的研究课题\[elaarabi2025adaptive, perez2025quantification\]，特别是对于图神经网络（GNNs）\[balan2203permutation, liu2025rotation\]、Transformer\[patil2025permutation, selvaraj2025permutation\]，以及最近的物理信息网络\[chen2026permutation\]。在这些研究中，学习过程必须确保神经网络的输出对输入神经元的排列是不变的，从而导致训练损失函数的排列不变优化。  

据我们所知，唯一同时考虑点之间的关系和可能点的空间都是连续的排列不变BO的工作，是使用近似集合核的BO\[Kim2021BayesianOW\]。在该工作中，集合核通过随机标量投影进行近似。对结果标量进行排序是一项简单的任务，大大降低了计算复杂度。该算法在合成问题以及为聚类算法选择初始解的问题上优于向量化方法。  

## 2 方法  

### 2.1 贝叶斯优化简介  
贝叶斯优化（BO）是一种样本高效的基于序列模型的方法，用于黑箱、昂贵评估、非凸目标函数的全局优化\[garnett2023bayesian, archetti2019bayesian\]。在典型的迭代中，BO执行两个动作：(a) 根据当前观测集 \(\mathcal{D} = \{(x^{(i)}, y^{(i)})\}_{i=1:n}\) 拟合目标函数的概率代理模型；(b) 通过优化一个依赖于概率代理模型并在利用（即局部搜索）和探索（即全局搜索）之间取得平衡的采集函数来选择下一个**查询点**。然后，评估下一个查询点 \(x'\)，并相应地更新 \(\mathcal{D}\)，即 \(\mathcal{D} \leftarrow \mathcal{D} \cup \{(x', y' = f(x'))\}\)。高斯过程（GP）\[gramacy2020surrogates, williams2006gaussian\] 是最广泛采用的概率代理模型选项，它为每个新输入 \(x\) 提供预测 \(\mu(x|\mathcal{D})\) 和相关的预测不确定性 \(\sigma(x|\mathcal{D})\)。这两个量还依赖于预先选择的**核**（又称协方差函数），其超参数通常通过最大似然估计（MLE）或最大后验估计（MAP）（可视为惩罚MLE）进行调优。不同的核会导致不同的GP模型，其中指数核和平方指数核代表了两种最不同的情况：前者GP预测连续但处处不可微，后者连续且无限可微。在采集函数方面，存在广泛的选择，通常分为两类：**基于改进**和**基于熵**\[shahriari2015taking\]。第一类采集函数旨在搜索 \(f(x^*)\)，而其他采集函数则旨在搜索 \(x^*\)。虽然看似无关，但这种区别导致了完全不同的策略，基于信息的采集函数通常提供更高的样本效率，但在确定下一个查询点时计算负担较大，因此仅当评估 \(f(x)\) 的成本显著更高时才有用。在本文中，我们考虑一种