确定性全局优化算法

字数 3314 2025-12-14 03:49:14

好的，已经仔细核对过你提供的超长列表，里面确实包含了许多算法，涵盖面非常广。为了确保新鲜感，我将避开已提到的所有算法（特别是所有“混合算法”），为你讲解一个在非线性规划领域中非常重要且经典的确定性全局优化算法的基础题目。

基于空间分割与局部优化的确定性全局优化算法（DIRECT算法）基础题

题目描述：

考虑一个具有“黑箱”特性的非线性约束优化问题。所谓“黑箱”，是指目标函数和约束函数的具体解析形式未知，或者非常复杂难以求导，但给定一组设计变量 \(x\)，我们可以通过计算机仿真或物理实验来计算出对应的目标函数值 \(f(x)\) 和约束违反程度。这类问题常见于工程设计与仿真优化。

现有一个具体的二维测试问题（称为“六驼峰函数”），其数学形式如下：

\[\min_{x_1, x_2} f(x) = 4x_1^2 - 2.1x_1^4 + \frac{1}{3}x_1^6 + x_1 x_2 - 4x_2^2 + 4x_2^4 \]

约束条件为：

\[-3 \leq x_1 \leq 3, \quad -2 \leq x_2 \leq 2 \]

此函数在定义域内有六个局部极小值点，其中有两个是全局极小点，位于近似对称的位置。我们的任务是：设计并理解一种不依赖于梯度信息、能够系统性地搜索整个定义域，并最终以确定性的方式（而非随机地）收敛到全局最优解附近的算法。DIRECT（Dividing RECTangles）算法就是为此类问题设计的一种代表性方法。

解题过程循序渐进讲解：

第一步：理解问题核心与算法思想

问题难点：我们面对的是一个多峰（多个局部最优点）的“黑箱”函数。传统的局部优化方法（如梯度下降）严重依赖于初始点，很可能陷在某个局部最优而无法找到全局最优。随机方法（如遗传算法）虽然能探索全局，但收敛性无法保证，且结果可能每次不同。
DIRECT的核心思想：它是一种“空间分割”与“局部搜索”相结合的确定性全局搜索算法。其核心在于：
- 分割：将整个连续的搜索空间（超矩形）不断分割成许多更小的子超矩形。
- 采样：在每个子矩形的“中心”进行函数值评估（采样）。
- 选择：根据一套确定的规则，选择一批“有潜力”包含全局最优点的子矩形进行下一步分割。
- 迭代：重复分割、采样、选择的过程，使得搜索越来越精细，最终逼近全局最优点。

第二步：算法初始化

标准化空间：将原始变量的边界 \([-3, 3] \times [-2, 2]\) 映射到单位超立方体 \([0, 1] \times [0, 1]\) 上。这是为了算法处理的统一性。设变换后的变量为 \(y_1, y_2\)。

\[ y_1 = \frac{x_1 - (-3)}{3 - (-3)} = \frac{x_1 + 3}{6}, \quad y_2 = \frac{x_2 - (-2)}{2 - (-2)} = \frac{x_2 + 2}{4} \]

反之，当我们得到算法内部的 $ y $ 后，可以反变换回 $ x $ 去计算函数值 $ f(x) $。

初始采样：在标准化空间的中心点 \(y = (0.5, 0.5)\) 进行第一次函数评估，这对应原始空间的 \(x = (0, 0)\)。记下这个点的函数值 \(f_c\)。此时，整个单位正方形就是第一个，也是唯一一个待处理的“子矩形”。

第三步：理解一次迭代的核心循环

DIRECT算法的单次迭代包含以下关键操作，我们以第 \(k\) 次迭代为例说明：

识别“有潜力”的矩形（潜力度量）：
- 对所有现有的子矩形 \(i\)，记录其三要素：中心点 \(c_i\)，中心点处的函数值 \(f_i = f(c_i)\)，以及矩形的“尺寸” \(\sigma_i\)（通常用矩形最长边的1/2长度来衡量，初始化时整个矩形的 \(\sigma = 0.5\)）。
- 潜力度量的目标是：既要关注那些函数值小的区域（可能已经接近最优），也要关注那些尺寸大的、还未被充分探索的区域（可能隐藏着更优解）。DIRECT用“估计的 Lipschitz 常数下限”来量化这种潜力。
- 具体操作：对于当前所有子矩形，按照其尺寸 \(\sigma\) 分组（例如，所有尺寸相同的矩形为一组）。在每一组内，找出函数值 \(f_i\) 最小的那个矩形。然后，将所有组中找到的这些“组内最优矩形”放在一起，进行下一步筛选。
选择进行分割的矩形：
- 将上一步得到的所有“组内最优矩形”，以它们的尺寸 \(\sigma\) 为横坐标，函数值 \(f\) 为纵坐标，画在图上。
- 想象一条从当前所有采样点中的全局最小函数值 \(f_{min}\) 出发，斜率为某个正常数 \(K\) 的直线 \(f = f_{min} - K \sigma\)。
- 选择所有位于这条直线下方的矩形。这意味着，如果一个矩形的函数值 \(f_i\) 足够低，或者它的尺寸 \(\sigma_i\) 足够大，它就会被认为“有潜力”，从而被选中进行分割。
- 要点：这里的 \(K\) 不是固定的，DIRECT通过选择位于下凸包（lower convex hull） 上的点来实现对所有可能的（正的）Lipschitz常数的同时考虑。这步操作是DIRECT的精华，它确保了算法在“局部求精”和“全局探索”之间的平衡。
分割被选中的矩形：
- 对于一个被选中的子矩形，找出它的最长边。如果有多个边都是最长的，则选择使得 \(w_j * |\text{方向}j\text{的偏导数估计}|\) 值最小的那个方向 \(j\) 进行分割（这里 \(w_j\) 是原始空间在第 \(j\) 维的宽度，偏导数可以用中心点附近的历史采样点估计，若无信息则随机选）。这有助于在函数变化平缓的方向多分割。
- 沿着选定的最长边，在三等分点处进行分割。具体来说：
  - 将这条边分成三段。
  - 在第一个1/3分点和第二个2/3分点处，垂直于该边将原矩形切割成三个新的、更小的子矩形。
  - 原矩形的中心点位于被切掉的中间那段，不再属于任何新矩形。
  - 在新的、较小的两个矩形的中心点进行函数评估。
  - 原来两端的两个矩形（包含原矩形的顶点）尺寸变小，但中心点已经评估过，无需重新计算。
- 这种分割方式保证了所有子矩形的形状不会过于狭长，且采样点（中心点）的分布具有一定的规律性。

第四步：迭代终止与结果获取

终止条件：重复执行第三步的迭代过程。常见的终止条件包括：
- 达到预设的最大函数评估次数（对于“黑箱”问题，这是最实际的限制，因为每次评估都对应一次昂贵的仿真或实验）。
- 所有子矩形的尺寸 \(\sigma_i\) 都小于一个给定的精度阈值 \(\epsilon\)。
- 连续多次迭代，全局最优估计值 \(f_{min}\) 的改进量小于某个容差。
输出结果：算法结束后，从所有已评估的采样点中，选择函数值最小的点 \(x^*\) 及其对应的 \(f(x^*)\) 作为全局最优解的估计。

总结与特点：

确定性：只要初始空间和采样规则固定，DIRECT的运行过程和结果就是完全可重现的。
无需梯度：完全基于函数值采样，适用于不可导或求导成本高的“黑箱”问题。
全局探索性：通过潜力度量和下凸包选择，系统性地平衡局部搜索和全局探索，最终收敛到全局最优。
计算成本：主要成本在于函数评估次数。DIRECT通过一套智能的选择机制，力求用尽可能少的评估来找到全局最优点。

对于“六驼峰函数”，DIRECT算法会从中心点开始，逐步将搜索矩形细分。它会首先在看起来有希望的区域（函数值较低）进行精细搜索，同时也不断地挑选那些尚未被充分探索的大区域进行采样。经过若干次迭代后，采样点会密集地分布在两个全局最优点附近，从而成功地识别出全局最优解。

好的，已经仔细核对过你提供的超长列表，里面确实包含了许多算法，涵盖面非常广。为了确保新鲜感，我将避开已提到的所有算法（特别是所有“混合算法”），为你讲解一个在非线性规划领域中非常重要且经典的确定性全局优化算法的基础题目。基于空间分割与局部优化的确定性全局优化算法（DIRECT算法）基础题题目描述：考虑一个具有“黑箱”特性的非线性约束优化问题。所谓“黑箱”，是指目标函数和约束函数的具体解析形式未知，或者非常复杂难以求导，但给定一组设计变量 \( x \)，我们可以通过计算机仿真或物理实验来计算出对应的目标函数值 \( f(x) \) 和约束违反程度。这类问题常见于工程设计与仿真优化。现有一个具体的二维测试问题（称为“六驼峰函数”），其数学形式如下： \[ \min_ {x_ 1, x_ 2} f(x) = 4x_ 1^2 - 2.1x_ 1^4 + \frac{1}{3}x_ 1^6 + x_ 1 x_ 2 - 4x_ 2^2 + 4x_ 2^4 \] 约束条件为： \[ -3 \leq x_ 1 \leq 3, \quad -2 \leq x_ 2 \leq 2 \] 此函数在定义域内有六个局部极小值点，其中有两个是全局极小点，位于近似对称的位置。我们的任务是：设计并理解一种不依赖于梯度信息、能够系统性地搜索整个定义域，并最终以确定性的方式（而非随机地）收敛到全局最优解附近的算法。DIRECT（Dividing RECTangles）算法就是为此类问题设计的一种代表性方法。解题过程循序渐进讲解：第一步：理解问题核心与算法思想问题难点：我们面对的是一个多峰（多个局部最优点）的“黑箱”函数。传统的局部优化方法（如梯度下降）严重依赖于初始点，很可能陷在某个局部最优而无法找到全局最优。随机方法（如遗传算法）虽然能探索全局，但收敛性无法保证，且结果可能每次不同。 DIRECT的核心思想：它是一种“空间分割”与“局部搜索”相结合的确定性全局搜索算法。其核心在于：分割：将整个连续的搜索空间（超矩形）不断分割成许多更小的子超矩形。采样：在每个子矩形的“中心”进行函数值评估（采样）。选择：根据一套确定的规则，选择一批“有潜力”包含全局最优点的子矩形进行下一步分割。迭代：重复分割、采样、选择的过程，使得搜索越来越精细，最终逼近全局最优点。第二步：算法初始化标准化空间：将原始变量的边界 \([ -3, 3] \times [ -2, 2]\) 映射到单位超立方体 \([ 0, 1] \times [ 0, 1]\) 上。这是为了算法处理的统一性。设变换后的变量为 \( y_ 1, y_ 2 \)。 \[ y_ 1 = \frac{x_ 1 - (-3)}{3 - (-3)} = \frac{x_ 1 + 3}{6}, \quad y_ 2 = \frac{x_ 2 - (-2)}{2 - (-2)} = \frac{x_ 2 + 2}{4} \] 反之，当我们得到算法内部的 \( y \) 后，可以反变换回 \( x \) 去计算函数值 \( f(x) \)。初始采样：在标准化空间的中心点 \( y = (0.5, 0.5) \) 进行第一次函数评估，这对应原始空间的 \( x = (0, 0) \)。记下这个点的函数值 \( f_ c \)。此时，整个单位正方形就是第一个，也是唯一一个待处理的“子矩形”。第三步：理解一次迭代的核心循环 DIRECT算法的单次迭代包含以下关键操作，我们以第 \( k \) 次迭代为例说明：识别“有潜力”的矩形（潜力度量）：对所有现有的子矩形 \( i \)，记录其三要素：中心点 \( c_ i \)，中心点处的函数值 \( f_ i = f(c_ i) \)，以及矩形的“尺寸” \( \sigma_ i \)（通常用矩形最长边的1/2长度来衡量，初始化时整个矩形的 \( \sigma = 0.5 \)）。潜力度量的目标是：既要关注那些函数值小的区域（可能已经接近最优），也要关注那些尺寸大的、还未被充分探索的区域（可能隐藏着更优解）。DIRECT用“估计的 Lipschitz 常数下限”来量化这种潜力。具体操作：对于当前所有子矩形，按照其尺寸 \( \sigma \) 分组（例如，所有尺寸相同的矩形为一组）。在每一组内，找出函数值 \( f_ i \) 最小的那个矩形。然后，将所有组中找到的这些“组内最优矩形”放在一起，进行下一步筛选。选择进行分割的矩形：将上一步得到的所有“组内最优矩形”，以它们的尺寸 \( \sigma \) 为横坐标，函数值 \( f \) 为纵坐标，画在图上。想象一条从当前所有采样点中的全局最小函数值 \( f_ {min} \) 出发，斜率为某个正常数 \( K \) 的直线 \( f = f_ {min} - K \sigma \)。选择所有位于这条直线下方的矩形。这意味着，如果一个矩形的函数值 \( f_ i \) 足够低，或者它的尺寸 \( \sigma_ i \) 足够大，它就会被认为“有潜力”，从而被选中进行分割。要点：这里的 \( K \) 不是固定的，DIRECT通过选择位于下凸包（lower convex hull）上的点来实现对所有可能的（正的）Lipschitz常数的同时考虑。这步操作是DIRECT的精华，它确保了算法在“局部求精”和“全局探索”之间的平衡。分割被选中的矩形：对于一个被选中的子矩形，找出它的最长边。如果有多个边都是最长的，则选择使得 \( w_ j * |\text{方向}j\text{的偏导数估计}| \) 值最小的那个方向 \( j \) 进行分割（这里 \( w_ j \) 是原始空间在第 \( j \) 维的宽度，偏导数可以用中心点附近的历史采样点估计，若无信息则随机选）。这有助于在函数变化平缓的方向多分割。沿着选定的最长边，在三等分点处进行分割。具体来说：将这条边分成三段。在第一个1/3分点和第二个2/3分点处，垂直于该边将原矩形切割成三个新的、更小的子矩形。原矩形的中心点位于被切掉的中间那段，不再属于任何新矩形。在新的、较小的两个矩形的中心点进行函数评估。原来两端的两个矩形（包含原矩形的顶点）尺寸变小，但中心点已经评估过，无需重新计算。这种分割方式保证了所有子矩形的形状不会过于狭长，且采样点（中心点）的分布具有一定的规律性。第四步：迭代终止与结果获取终止条件：重复执行第三步的迭代过程。常见的终止条件包括：达到预设的最大函数评估次数（对于“黑箱”问题，这是最实际的限制，因为每次评估都对应一次昂贵的仿真或实验）。所有子矩形的尺寸 \( \sigma_ i \) 都小于一个给定的精度阈值 \( \epsilon \)。连续多次迭代，全局最优估计值 \( f_ {min} \) 的改进量小于某个容差。输出结果：算法结束后，从所有已评估的采样点中，选择函数值最小的点 \( x^* \) 及其对应的 \( f(x^* ) \) 作为全局最优解的估计。总结与特点：确定性：只要初始空间和采样规则固定，DIRECT的运行过程和结果就是完全可重现的。无需梯度：完全基于函数值采样，适用于不可导或求导成本高的“黑箱”问题。全局探索性：通过潜力度量和下凸包选择，系统性地平衡局部搜索和全局探索，最终收敛到全局最优。计算成本：主要成本在于函数评估次数。DIRECT通过一套智能的选择机制，力求用尽可能少的评估来找到全局最优点。对于“六驼峰函数”，DIRECT算法会从中心点开始，逐步将搜索矩形细分。它会首先在看起来有希望的区域（函数值较低）进行精细搜索，同时也不断地挑选那些尚未被充分探索的大区域进行采样。经过若干次迭代后，采样点会密集地分布在两个全局最优点附近，从而成功地识别出全局最优解。