1. 简介
在本篇文章中，我们将探讨确定性优化方法与随机优化方法。重点在于理解这两类方法的异同，并通过具体算法示例说明它们的典型应用场景。
我们将先简要介绍优化方法的基本概念，接着分别深入讲解确定性与随机优化方法的核心原理与典型模型，最后通过对比表格总结两者的差异。
2. 计算中的优化
优化在计算机科学中应用广泛，常用于解决复杂问题并提升系统效率。我们通常通过建模问题和输入数据，使用合适的算法来求解最优解。
优化算法的目标是找到问题的最佳候选解，而这个过程依赖于目标函数的评估。目标函数会根据问题的特性与约束进行设计。
需要注意的是，不是所有优化算法都能保证找到全局最优解（global optima）。有些算法是精确的，能保证找到全局最优；另一些是非精确的，可能只能找到局部最优（local optima）。
没有一种优化算法是“万能”的，选择哪种方法取决于问题的复杂度、可用计算资源、时间限制以及是否必须找到全局最优解。
3. 确定性优化方法
确定性优化方法的目标是找到全局最优解，并提供理论保证。这类方法通过利用问题的特定结构来系统性地搜索最优解。
根据 Neumaier 的分类，确定性优化包括：
- Complete（完备）算法：理论上可以在无限时间内找到全局最优解，在有限时间内可找到满足精度要求的解。
- Rigorous（严格）算法：在有限时间内找到满足精度要求的全局最优解。
确定性优化适用于结构清晰、可利用数学性质进行求解的问题。但在面对黑盒问题或高度复杂、非线性的目标函数时，这类方法可能难以应对，因为搜索空间太大或结构太复杂。
3.1 确定性优化模型示例
以下是几种常见的确定性优化模型：
- **线性规划 (Linear Programming, LP)**：问题和目标函数均为线性。
- **非线性规划 (Nonlinear Programming, NLP)**：允许目标函数或约束为非线性。
- **整数规划 (Integer Programming, IP)**：变量必须为整数。
- 非凸非线性规划 (Non-convex Nonlinear Programming, NNLP)
- 混合整数非线性规划 (Mixed-Integer Nonlinear Programming, MINLP)
下图展示了这些模型之间的关系与适用问题类型：
实现确定性优化的典型方法包括：
✅ Branch-and-Bound（分支定界）
✅ Cutting Plane（割平面法）
✅ Outer Approximation（外逼近法）
✅ Interval Analysis（区间分析）
这些方法通常用于求解结构明确、可建模的问题，尤其适合凸优化问题。
4. 随机优化方法
随机优化的目标与确定性优化类似，也是寻找“好的解”，但其方法中引入了随机性。
因此，随机优化不能保证找到全局最优解，但在足够时间下，有概率找到全局最优解。时间越长，找到全局最优的概率越高；理论上，若执行时间为无限，找到全局最优的概率为100%。
但在实际应用中，我们通常只能接受一个足够好的解，而不必是全局最优。这种灵活性使得随机优化在很多实际场景中非常受欢迎。
4.1 启发式与元启发式算法
随机优化方法中，最常见的是启发式与元启发式算法。
- 启发式：针对特定问题设计的策略，不具备通用性。
- 元启发式：通用性强，可应用于多种问题。
常见的随机优化算法包括：
✅ 轨迹类方法：如 Tabu Search（禁忌搜索）
✅ 群体类方法：如
- 遗传算法 (Genetic Algorithms)
- 灰狼优化 (Grey-Wolf Optimization)
- 粒子群优化 (Particle Swarm Optimization)
- 蚁群算法 (Ant Colony Optimization)
- 人工蜂群算法 (Artificial Bee Colony)
下图总结了随机优化方法的分类：
这些算法通常用于解决大规模、复杂度高、搜索空间大的问题，特别适合实时性要求较高的场景。
5. 系统化对比总结
| 特性 | 确定性优化 | 随机优化 |
|---|---|---|
| 全局最优解 | ✅ 保证找到（理论） | ⚠️ 仅在无限时间下保证 |
| 可建模问题类型 | LP, IP, NLP, MINLP 等 | 任意模型均可 |
| 执行时间 | 对中大规模问题可能非常长 | ✅ 可控，根据需求调整 |
| 常见算法 | Branch-and-Bound, Cutting Plane 等 | Genetic Algorithm, PSO, GWO 等 |
6. 结论
本文我们系统地介绍了确定性优化与随机优化两类方法的核心思想、适用场景及典型算法。
- 如果你必须找到全局最优解，那么确定性优化是首选。
- 如果你更关注解的质量与执行效率之间的平衡，并且可以接受一个足够好的解，那么随机优化更为合适。
两者各有优势，选择时应根据问题类型、资源限制和实际需求进行权衡。在实际开发中，有时还会结合使用这两类方法以达到最佳效果。