# Global_Search **Repository Path**: bpyhome/global_-search ## Basic Information - **Project Name**: Global_Search - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2025-03-23 - **Last Updated**: 2025-03-23 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README **脚本 main 在Nelder-Mead.py 实现绘制三维图像以及使用Nelder-Mead搜索的功能** **iter_curv.py 实现了绘制迭代曲线的能力** **folder record 里面存了随机生成的函数的图像** # 实验报告 - **实验名称**：使用Nelder-Mead单纯形法结合随机初始化全局搜索 - **实验者**：白培琰 - **指导老师**：赵一 - **实验时间**： 2025年三月22 ### 摘要 使用Python实现了Nelder-Mead单纯形法，并结合随机初始化实现全局搜索。使用matplotlib 画出了优化的迭代曲线，以及函数的三维图像。比较手写Nelder-Mead 和numpy.optimizer.minmize的区别。分析不同超参数对搜索的影响。 ### Nelder-Mead 单纯形法的原理与公式 **Nelder-Mead 单纯形法**是一种基于几何操作的迭代优化算法，它通过操作一个**单纯形**（simplex）在多维空间中逼近最优解。为了更清楚地理解这个方法，可以通过公式详细说明其基本步骤和计算过程。 #### 1. **单纯形（Simplex）** 在一个 **n** 维空间中，单纯形是由 **n+1** 个点构成的几何体。比如在二维空间中，单纯形是一个三角形，三维空间中的单纯形是四面体。算法通过这些顶点来探索函数的极值点。 设目标函数为 f(x)，其中$ x = (x_1, x_2, \dots, x_n) $是问题的决策变量。\ #### 2. **初始化** 首先，选择$ n+1$个初始点，形成一个初始单纯形。假设初始单纯形的顶点为 $ x1,x2,…,x_{n+1}$，它们的目标函数值为$ f(x_1), f(x_2), \dots, f(x_{n+1}) $。 #### 3. **排序** 对所有顶点的目标函数值进行排序，得到： $$ f(x_1) \leq f(x_2) \leq \dots \leq f(x_{n+1}) $$ 其中，$ x_1 $对应最优的顶点（最小的目标函数值），而$ x_{n+1} $对应最差的顶点（最大目标函数值）。 #### 4. **反射（Reflection）** 反射操作计算反射点 $ x_r$，其公式为： $$ x_r = x_{\text{centroid}} + \alpha (x_{\text{centroid}} - x_{n+1}) $$ 其中： - $ x_{\text{centroid}}$是除最差点外其他顶点的重心，即：$ x_{\text{centroid}} = \frac{1}{n} \sum_{i=1}^{n} x_i $ - $\alpha$ 是反射系数，通常取值为 $\alpha = 1$。 如果反射点 $ x_r $比最差点的目标函数值更好（即 $ f(x_r) < f(x_{n+1} $），则接受反射点，并用它替换最差点 $ x_{n+1} $。 #### 5. **扩展（Expansion）** 如果反射点 $x_r$的目标函数值更好，且比重心附近的点更好，即：$f(x_r) < f(x_1)$ 则进行扩展，计算扩展点 $ x_e$： $$ x_e = x_{\text{centroid}} + \gamma (x_r - x_{\text{centroid}}) $$ 其中，$\gamma$ 是扩展系数，通常取 $\gamma = 2$。 如果扩展点 $x_e$ 比反射点 $x_r$ 还好，则用 $x_e$ 替换最差点 $x_{n+1}$。 #### 6. **收缩（Contraction）** 如果反射点不好，即 $f(x_r) > f(x_{n+1})$，则进行收缩，计算收缩点 $x_c$： $$ x_c = x_{\text{centroid}} + \beta (x_{n+1} - x_{\text{centroid}}) $$ 其中，β\betaβ 是收缩系数，通常取 $\beta = 0.5$。 如果收缩点 $x_c$ 的目标函数值较好，则用 $x_c$ 替换最差点 $x_{n+1}$。 #### 7. **终止条件** 当单纯形的大小小于某个预设的阈值（如，所有顶点之间的距离小于某个值），或者目标函数值的变化足够小，或者达到最大迭代次数时，算法终止。 ### 代码 ![code1](pic/1.png) ![code2](pic/2.png) **完整代码请见[Gitee](https://gitee.com/bpyhome/global_-search)** 因为Nelder-Mead单纯形一般只适用于求局部最优解，所以通过**随机初始化100个点**来进行全局搜索化 ### 结果 以$y=5x^2+7y^2-3xy+5d+2e+10f$为例： 反射系数 $\alpha$=1 扩展系数 $\gamma$=2 收缩系数$\rho$=0.5 缩减系数 $\sigma$=0.5 最大迭代次数 max_iter=1000 收敛公差tol=1e-6 ![迭代图像](iter_curve/Figure_1.png) 由图可见，优化在迭代8次后收敛。 ![3D diagram](iter_curve/Figure_1_3D.png) 使用matplotlib.mpl_toolkits.mplot3 画出函数式的三维图像，图中标出了使用numpy预测的最小值 实验结果： **best_point**: [-0.58031275 -0.26726023] **best_value**: 8.282442885726038 #### 实验结果对比 | | x_value | y_value | z_value | | ------------------------ | ----------- | ----------- | ----------------- | | Nelder-Mead单纯形 | -0.58031275 | -0.26726023 | 8.282442885726038 | | numpy.optimizer.minimize | -0.58 | -0.57 | 8.28 | 由图可见，手写Nelder-mead得出的结果已经相当接近numpy的结果，差异应该是由于numpy精度的问题。 ### 使用不同超参数的结果分析 我通过查阅资料得到如下，得到对几种超参数的初步认识： ### 1. **反射系数 (`alpha`)** - **作用**：反射系数决定了反射操作的步长，即从最差点反射到新点时，步长的倍数。 - **常见值范围**：`1.0` 到 `2.0` 之间。较高的值可能会使算法跳过一些局部最优解，从而探索更广泛的搜索空间。 - 推荐值 ： - `alpha = 1.0`：默认值，通常适用于大多数情况。 - `alpha = 1.5` 或 `alpha = 2.0`：在某些情况下可以加速收敛，但也可能导致不稳定的行为，尤其是当目标函数不平滑时。 ### 2. **扩展系数 (`gamma`)** - **作用**：扩展系数决定了在扩展操作中的步长，即当反射点比最优点还好时，扩展步骤的步长倍数。 - **常见值范围**：`2.0` 到 `4.0` 之间。 - 推荐值： - `gamma = 2.0`：较常用的默认值。 - `gamma = 3.0` 或 `gamma = 4.0`：在需要强烈扩展时使用，可以增加搜索空间的探索深度，但可能导致过度扩展，结果偏离最优解。 ### 3. **收缩系数 (`rho`)** - **作用**：收缩系数决定了在收缩操作中的步长，即当反射点不如最优点时，收缩步骤的步长倍数。 - **常见值范围**：`0.5` 到 `0.7` 之间。 - 推荐值： - `rho = 0.5`：较常用的默认值。 - `rho = 0.7`：适用于较慢收敛的情况，但也有可能导致收缩过多。 ### 4. **缩减系数 (`sigma`)** - **作用**：缩减系数决定了缩减操作的步长，即当没有任何进展时，单纯形的所有点会朝着最优点缩减。 - **常见值范围**：`0.5` 到 `0.75` 之间。 - 推荐值： - `sigma = 0.5`：通常用于收缩操作，适用于不需要过多收缩的情况。 - `sigma = 0.6` 或 `sigma = 0.75`：在某些情况下，较高的值可以使算法避免早期收敛，但也可能导致收敛速度变慢。 --- 我调整了参数 以$y=5x^2+7y^2-3xy+5d+2e+10f$为例： 反射系数 $\alpha$=2 扩展系数 $\gamma$=4 收缩系数$\rho$=0.7 缩减系数 $\sigma$=0.75 最大迭代次数 max_iter=1000 收敛公差tol=1e-6 ![a](iter_curve/Figure_2.png) 由图可见：算法步长很大，但是迭代了1000次仍然无法收敛，且结果明显大于最优值 | | x_value | y_value | z_value | | ---- | ------- | ------- | ------- | | | 0 | 1 | 18 | 当超参数设置过大时，尤其是在 **Nelder-Mead** 优化算法中，算法可能会出现收敛困难的情况。具体来说，如果反射系数 (`alpha`)、扩展系数 (`gamma`) 等参数设置得过大，优化过程中每一步的搜索步长就会显著增加。这可能导致以下几个问题： 1. **过度探索，无法收敛：** 由于步长过大，算法可能会跳过局部最优解，导致无法细致地收敛到真正的最优点。每次迭代可能会跨越目标函数的多个极值区域，浪费计算资源并使优化过程变得不稳定，导致最终结果大大偏离理想解。 2. **优化过程过长：** 由于超参数的过大设置，算法可能会在多次反射和扩展过程中不断尝试过大的步伐。尽管可能在某些情况下加速了探索过程，但却可能无法在1000轮内收敛，造成优化过程极其缓慢或最终无法收敛。 3. **收敛性能不稳定：** 当超参数设置较大时，尤其是 `gamma` 和 `alpha` 等扩展相关的参数，算法会倾向于做出较大幅度的探索。尽管这种方法有可能加速搜索过程，带来更广泛的搜索空间覆盖，但缺乏足够的控制，导致优化过程的不稳定，最终使得结果大大偏离真实的最小值。 另一方面，更新状态的参数（例如合理的增量步长和较小的 `gamma`）确实能**加速收敛**。通过调整这些参数，算法能够更快速地接近目标函数的最优解，从而**减少迭代次数**。但这种加速通常是建立在一个折中的基础上，优化算法的**收敛性可能受到损害**。具体而言，快速收敛可能导致算法在某些复杂的多峰目标函数上停留在局部最优解，而无法找到全局最优解。这就要求我们在使用加速收敛的策略时，**同时考虑算法的稳定性与收敛性之间的平衡**。 ### 另一个问题 $y=5x^2+7y^2-3xy+5d+2e+10f$ 在某些参数下，不存在最小值，例如： ![](records/record_5/3d_plot.png) 这种情况下，Nelder-Mead 只能尽可能地接近最小值 --- ### 总结 在本次实验中，首先基于 **Python** 编程语言实现了 **Nelder-Mead 单纯形法**（Nelder-Mead Simplex Method），该算法是一种常用于无约束优化问题的数值优化方法。为了提高优化过程的全局搜索能力，采用了随机初始化的方法，这样能够使得优化过程从多个初始点开始搜索，从而提高了找到全局最优解的概率。 实验中，我们不仅实现了优化算法，还通过绘制 **目标函数的三维图** 展示了函数的形状和特性，帮助我们更直观地理解优化过程。通过三维图，可以清晰地看到目标函数的局部极值和全局极值位置，以及不同区域的陡峭程度，这为选择合适的优化策略提供了直观的依据。 在优化过程中，我们还绘制了 **优化迭代的曲线图**，记录了每一次迭代中目标函数值的变化。这条曲线展示了算法如何逐步逼近最优解，并有助于分析算法的收敛速度和稳定性。通过观察迭代过程中的目标函数值变化，能够判断优化算法是否正常收敛，或者是否存在过早收敛或波动等问题。 为了验证我们实现的 **Nelder-Mead 算法** 的正确性和有效性，我们将优化结果与 **NumPy** 库中的优化算法进行对比。通过与标准的优化结果进行比较，我们能够评估自己实现的算法是否达到了预期的优化效果，并检查结果的准确性。 最后，实验还探讨了不同超参数（如反射系数 `alpha`、扩展系数 `gamma`、收缩系数 `rho` 和缩减系数 `sigma`）对优化过程的影响。通过调节这些超参数并观察不同设置下优化过程的表现，我们能够分析每个超参数如何影响优化的效率和结果。例如，某些超参数的较大值可能会加速收敛，但也可能导致收敛不稳定，而较小的超参数可能使得优化过程更加平稳，但速度较慢。通过这种对比分析，我们能够选择出适合特定问题的最优超参数组合，从而提高优化效果。 总结来说，本实验通过多方面的分析和对比，全面评估了 **Nelder-Mead 单纯形法** 在优化问题中的表现，提供了对该算法在实际应用中表现的深入理解。