1.元启发式算法

备注：

元启发式算法一般都结合/借助了一些“知识”bias，并不是盲目的进行搜索。

元启发式方法结合了一些biases，这些偏见引导他们只考虑搜索空间的一小部分[6]。因此，他们可以从战略地寻找好的解决方案，并表现出一定的智能水平。下面是biases的分类（掌握这种思维我觉得对于设计算法也很有帮助）：

随机（random）或词典bias，其中选择的替代解是不做任何考虑的。
贪婪（greedy）或简单的体面（simple decent）的bias，其中选择的解是基于目标函数的。
记忆bias，当前选择解是基于之前选择的解的。
经验或目标bias，其中当前选择的解是基于以前的表现。

2.GRASP

GRASP是针对组合优化问题的多起点元启发式方法，其中每个迭代基本上都包含两个阶段，即：

构造阶段construction
局部搜索阶段improvement

构造阶段构造了一个可接受的解。在局部搜索阶段，GRASP剖析这个解的邻域，更新解，直到解达到局部最优。

更直白的说，GRASP首先从问题的组成元素中构造一个解（在构造阶段），然后再“调整”这个解决方案（在局部搜索阶段）。

GRASP重复进行构建和局部搜索阶段，直到达到最大迭代次数，或找到预期的解。通常来说，最大迭代次数影响着解的质量。换句话说：总体而言，迭代次数越多，解的质量就越好。

它将把在这个过程中，获得的最好的解视为最终解。当我们需要在合理的时间内找到一个接近最优的解时（不要求全局最优），GRASP是有用的。

2.1伪代码

注意：第5行，是修复成可行解。因为一开始构造的解不一定可行。

第3行对应着构造阶段，第7行对应着改进阶段。只要有改进，就更新解。

2.2 构造阶段construction

通过多次迭代构造一个可行解，每次加入一个元素。

在每次迭代之前，初始化可行解S为空，并且初始化候选集C并对候选集的每一个元素进行评估，作为进入限制候选列表的依据。每次迭代从候选集中选部分元素构成限制候选列表RCL。每次从限制候选列表RCL中随机选择一个元素与可行解S进行合并，然后更新候选集的元素，同时对里面的每一个元素进行重新评估。

在逐个加入元素的过程中，体现了贪心，随机，自适应的特点，这也是算法名字的由来。为什么贪心，随机，自适应——可以看这篇。

简单写写我的理解：

贪婪反映在了其对限制候选列表（Restricted Candidate List -> RCL)的构建上（伪代码第2行到第5行），因为是按照价值增加的思想添加的。RCT的长度由参数 $\alpha$ 确定。α = 1，对应完全随机的过程，所有候选元素都可随机选；α = 0，对应完全贪心的过程，只能选取最优的候选元素。