贪心随机自适应搜索算法（GRASP）要点总结 PART 1 - 组合优化问题与元启发式算法
前言：
前几周被要求写一份GRASP的学习总结，虽然这个算法比较悠久（1989年），但是中文资料比较少，所以我就想说把这个学习总结翻译成中文，再用比较口语的方式表达，给需要的人参考。
一共有四个部分，
- Part 1 - 组合优化问题与元启发式算法
- Part 2 - GRASP要点
- Part 3 - GRASP的构造阶段
- Part 4 - GRASP的局部搜索阶段与总结
本文是第一部分，感兴趣的同学可以看我其他文章。
1. 背景介绍：组合优化问题
GRASP的出现是为了解决组合优化问题。因为，为了解决这些问题，例如旅行商问题（TSP），我们需要从一组有限的选项中找到最佳解决方案[1]。 而这种搜寻最佳方案的任务通常被认为是非常困难的，因为它们是离散的，复杂的（通常是NP-hard，存在非常多的可能组合）且受约束的[2]。
通常，我们并没有很多的时间，精力，来探究这一个个可能解。所以很多时候，我们最想要的是在一定时间范围内找到“还过得去“（却并不是最优）的解。所以，选择搜索算法我们必须权衡，
- 解的质量
- 获取解的时间
2. 方法
为解决组合优化问题，我们有以下方法，
- 精确方法（exact method）：确保能获得最优解，但是耗时长。例子有：枚举法（enumeration）
- 近似方法（approximate method）：并不能确保最优解，但是有参数能衡量与最优解的“差距”，耗时相对短。例子有：First-Fit, First-Fit-Decreasing…
- （元）启发性演算法：元启发式算法是设计用于查找，生成或选择启发式（部分搜索算法）的更高级别的过程或启发式方法，可以为优化问题提供足够好的解决方案，尤其是在信息不完整或不完善或计算能力有限的情况下 [ 5]。 与逼近方法不同，元启发法对获得的解与最佳解的接近程度没有任何限制[6]。例子有：遗传算法，GRASP....
- .....
3. 考虑因素
选择解决组合问题的方法类型涉及两个考虑因素[6]：
- 解决方案的成本或价值应为最优还是接近最优。
- 计算工作是否应该是最佳的。
与穷举枚举等精确方法相比，元启发式方法往往更为有效，因为大多数组合优化问题“难以解决且具有巨大的解空间”[6]。从实践的角度看，枚举虽然保证了最优，但在时间上并不有效和高效。使用元启发式方法可能是一个很好的权衡。换句话说，如果目标是平衡质量或速度，元启发式可能是一种理想的方法。
4. Bias
元启发式方法结合了一些偏见（biases），这些偏见引导他们只考虑搜索空间的一小部分[6]。因此，他们可以从战略地寻找好的解决方案，并表现出一定的智能水平。
下面是偏见（biases）的分类（下面我直接用英文bias吧，翻译成“偏见”感觉怪怪的）：
- 随机（random）或词典bias，其中选择的替代解是不做任何考虑的。
- 贪婪（greedy）或简单的体面（simple decent）的bias，其中选择的解是基于目标函数的。
- 记忆bias，当前选择解是基于之前选择的解的。
- 经验或目标bias，其中当前选择的解是基于以前的表现。
我们的主题GRASP（贪婪随机自适应搜索过程）是一种使用贪婪bias的元启发式算法[6]。
5. 引用
[1] E. G. Talbi, Metaheuristics: from design to implementation, Hoboken, New Jersey: John Wiley & Sons. , 2009. a
[2] K. Apt, Principles of constraint programming, Cambridge: Cambridge university press, 2003. a
[3] E. L. Lawler and D. E. Wood, “Branch-and-bound methods: A survey,” Operations research, vol. 14, no. 4, pp. 699-719, 1966. a
[4] M. Tawarmalani and N. V. Sahinidis, “A polyhedral branch-and-cut approach to global optimization,” Mathematical programming, vol. 103, no. 2, pp. 225-249, 2005. a
[5] L. Bianchi, M. Dorigo, L. M. Gambardella and W. J. Gutjahr, “A survey on metaheuristics for stochastic combinatorial optimization,” Natural Computing, vol. 8, no. 2, pp. 239-287, 2009. a
[6] T. A. Feo and M. G. Resende, “Greedy randomized adaptive search procedures,” Journal of global optimization, vol. 6, no. 2, pp. 109-133, 1995. a
文章被以下专栏收录
