这两天刚好看到这个算法，然后就写一写吧。贪心随机自适应搜索虽然算是一个比较简单的启发式，但是效果也非常不错的。

01 概述

Greedy Randomized Adaptive Search，贪婪随机自适应搜索（GRAS），是组合优化问题中的多起点元启发式算法。

在算法的每次迭代中，主要由两个阶段组成：构造（construction）和局部搜索（ local search）。

构造（construction）阶段主要用于生成一个可行解，而后该初始可行解会被放进局部搜索进行邻域搜索，直到找到一个局部最优解为止。

02 整体框架

如上面所说，其实整一个算法的框架相对于其他算法来说还算比较简单明了，大家可以先看以下整体的伪代码：

(GRAS伪代码)

GRAS主要由两部分组成：

1) Greedy_Randomized_Construction：在贪心的基础上，加入一定的随机因素，构造初始可行解。

2) Local Search：对上面构造的初始可行解进行邻域搜索，直到找到一个局部最优解。

然后再多说两句：

Repair是什么鬼？有时候由于随机因素的加入，Greedy_Randomized_Construction阶段生成的解不一定都是可行解，所以为了保证下一步的Local Search能继续进行，加入repair算子，对解进行修复，保证其可行。

不是说自适应（Adaptive）吗？我怎么没看到Adaptive 的过程？
别急，这个后面具体举例的时候会详细讲到。

03 举个例子说明

为了大家能更加深入理解该算法，我们举一个简单的例子来为大家详细讲解算法的流程。

假如有一个有限的集合E = {1, 2, 3, ……, n}。可行解的集合，（我知道你们想问是什么，由E的所有子集作为元素构成的集合。）目标函数，求目标函数的最小值以及对应的解。

好了，相信大家都看懂上面的问题了（看不懂也别问我，摊手）。对于上述问题，我们来一步一个脚印用GRAS来求解之，来，跟紧小编的脚步……

强调了很多次，GRAS由两部分组成：Greedy_Randomized_Construction和Local Search，所以，在求解具体问题的时候，完成这两部分的设计，然后按照第二节所示的框架搭起来就可以。

3.1 Greedy_Randomized_Construction

这里还是老规矩，先上伪代码给大家看看，然后我们再进行讲解，毕竟对于算法来说，伪代码的作用不言而喻。

Greedy_Randomized_Construction

第1行，一开始解是一个空集。

第2行，初始化候选元素的集合，这里候选元素是指能放进Solution的元素（也就是目前Solution里面没有的），比如１，２，３……。

第3行，对候选集合的每个元素进行评估，计算将元素x放入Solution会导致目标函数f改变量delta_x。

第5行，根据delta_x对各个元素排序，选取部分较好的候选元素组成RCL表（贪心性体现在这里）。

第6行，随机在RCL中选取一个元素放进Solution。（算法的随机性）

第8、9行，更新候选元素集合，然后对每个元素进行重新评估计算delta值。（算法的自适应性体现在这里）

相信经过上面如此详细的介绍，大家都懂了吧！