元启发式算法手记三 GRASP

元启发式（Metaheuristics）算法是当前大数据领域最前沿的解决实际最困难问题的一系列算法框架，针对NP-Hard组合优化问题，用元启发式搜索往往可以得到相当不错的结果。本系列内容将持续更新所有具有代表性的元启发式算法，一方面是个人学习笔记，另一方面是为了填补中文圈准确资料稀少的问题。因为学习源头为英文，部分名词的翻译并不精准，仅以个人喜好进行名词翻译，如果有别的地方不同的翻译方法，请以英文为准。

本文为系列三，主要介绍the greedy randomized adaptive search procedure (GRASP) 贪婪随机自适应搜索程序。

大概意思

GRASP大概是1989第一次被提出，其特殊的地方在于，贪婪和随机的两个特性都可以被很好地适应。当贪婪的算法容易陷入局部最优解，光随机又很难收敛。于是就有了这个结合体。

GRASP要点

GRASP和其他算法的区别在于，GRASP一般会存在两个步骤，一个是构建阶段（construction），一个是局部搜索。

构建阶段主要是以启发算法建立一个随机或部分随机的可行解，然后再在第二阶段里进行了对构建好的空间进行的局部搜索达到最优解。

GRASP的ground set

在构建解的时候，有一个ground set的概念，它的意思是，这是一个“可能的部分解”，再配合incremental cost，意思是增加的cost，当在ground set里添加元素时，需要计算这个cost的变化情况。

还有一个概念是RCL(restricted candidate list)，它是一堆ground set的待选列表，都是在之前的迭代中还不错的解，用来对当前的解进行扩充。

迭代的过程中，要对RCL进行不断地更新和衡量。

随机和贪婪体现在哪里

本算法的构建阶段并不保障产生的解都是可行解， 所以后续还有可能要修复解。而对RCL的控制是通过一个alpha参数。简单的说，当alpha为1时，所生产出来的RCL都是全随机的，此时的解不太科学，但足够多样性；当alpha为0时，生产出来的RCL都是贪婪的，此时的解也不太科学，但足够局部最优。

所以我们会选一个兼顾多样性和局部最优的alpha值，这也是本算法的精妙所在。

变种GRASP

变种主要是在变alpha，比如说reactive Grasp，alpha在执行过程中慢慢发生变化。

看代码

https://github.com/54chen/grasp_latinsquare

本代码用GRASP完成了拉丁方阵的自动补全，其中增量消费函数定义为每行每列的重复数量及空数量。输入一个残缺方阵，算法将自动找出最可能的拉丁方阵。这是一个NP-Hard问题。

对代码进行解读（英文）的视频点这里 -> https://youtu.be/EqOFhoaGd00

引用 https://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure