1、简介-Introduction

GRASP(Greedy Randomized Adaptive Searh Procedures)是一个用于求解组合优化问题的multi-start元启发式算法，每一次迭代都包含以下两个阶段：构造(construction)和局部搜索(local search)。在构造阶段会构建一个可行解，在局部搜索阶段会对可行解的邻域进行搜索直到找到局部最优解。

上述是基本GRASP的思路，可以采用下述几种方式对算法进行优化：Reactive GRASP，cost perturbation，bias function，memory and learning，path-relinking。同时，GRASP可以采用同步策略，使用多线程方法加快最优解寻优速度。

2、算法流程和概念引入

GRASP的整体流程如下图所示：

其中Max_Iteration表示最大的迭代次数，seed表示随机数种子，第5行代码表示若找到更好的解则对当前最优解进行更新。

下图是构造(construction)阶段流程的伪代码：

在贪婪构建解的过程中，伪代码第5行中需要构建有限候选集合-RCL，使用贪心函数来构建RCL，简答来说就是将某个没有加入到解中的元素添加当前解之中，衡量元素加入到解前后的变动成本，之后设置一个阈值或者数量限制，将变动成本(或总成本)最小的一些元素选入到RCL中。之后从RCL中随机选择一个元素来继续构建解方案，之后在下一次构建时再重新进行RCL的构建，直到所有的元素均在解方案之中。

下图是局部搜索(Local Search)阶段流程的伪代码：

局部搜索(LS)对构造的解Solution进行邻域N(Solution)的搜索，若找到优于Solution的解，则进行最优解的替换，直到找到局部最优解。

在使用邻域搜索时，使用的策略包括best-improving和first-improving两种，有相关研究发现使用first-improving在跳出局部最优解和求解时间方面比较有优势。

3、RCL的构建细节和技巧

GRASP算法比较重要的部分是每一次优化初始解的构建，一个好的初始输入可以使得LS搜索更加有效率，增加最优解找到的几率和缩短求解时间。而在解构造的过程中，RCL的构建和保留又是至关重要的一个环节。下面详细描述几种不同方式的RCL构建方式。

3.1 静态构建RCL

定义 c(e)表示加入一个元素  e到解之后的变动成本，RCL中包含拥有最优 c(e)的一定数量  p的所有的元素 e。通常的做法是依靠变动成本c(e)的质量来确定数量 p。下面引入一个阈值参数 α \alpha α来限定数量 p。规定可以加入到RCL中的元素必须满足下式：

c(e)∈[cmin,cmin+α(cmax−cmin)]

可以发现当参数 α = 0 \alpha = 0 α=0，RCL中只有一个最优元素，则构造过程变为一个完全贪婪构造；当 α = 1 \alpha = 1 α=1时，RCL包含所有可行的元素，则构造过程变为一个完全随机构造。所以依靠参数 α \alpha α便可以控制构造过程的随机性和贪婪性的比例。根据文献中的实践，参数 α \alpha α的取值为0.8时，可以得到较好的构造解。

3.2 基于均匀分布构建RCL

由于使用单一的参数 α \alpha α往往不能找到高质量的解，所以提出采用一系列不同的 α \alpha α值来增大随机性，扩大搜索的广度。首先定义

Ψ=α1,...,αm表示一系列参数 α \alpha α的可能取值，均匀分布的意思是这些不同取值的 α \alpha α被选到的概率均为  1/m。

3.3 非均匀离散分布构建RCL

和上述均匀分布类似，但不同取值的 α \alpha α被选到的概率基于实现分配，同时这些概率互不相同，下述是一种分配方式：

3.4 Reactive GRASP

在这种方式下，参数 α \alpha α的取值不是固定的，而是根据求解的结果进行动态自适应调整的。

同样令 Ψ=α1,...,αm表示参数 α \alpha α所有可能的取值，而选择每一个取值的概率初始化为pi=1/m，i=1,..,m。令 z^* 表示当前解的目标函数值，令  Ai表示使用每一个 α i \alpha_i αi所求得的目标函数值的平均值，初始化 A i A_i Ai的值为初始解的值。在每一次局部搜索结束之后，首先更新 Ai的值，之后计算 qi=z∗/Ai，for i=1,...,m，最后更新选择每一个 α i \alpha_i αi被选到的概率：pi=qi/∑j=1mqj。

4、Bias Function

在标准GRASP框架之中，构建完RCL集合之后，会从中随机选取一个元素来继续构建解方案，但是其实可以采取更加有效的方式，例如以一定概率首先选取更好的元素，来bias这个选择的过程。要应用Bias Function首先需要根据贪心函数求得的 c ( e ) c(e) c(e)给所有的元素 e e e一个等级 r ( e ) r(e) r(e)，之后可以采取的Bias Function有以下几种：

   random bias:bias(r)=1;

   linear bias:  bias(r)=1/r;

   log bias: bias(r)=log−1(r+1)

   exponential bias: bias(r)=e−r

   polynomial bias of order n:  bias(r)=r−n

利用上述某种规则计算出来所有元素的bias值之后，选择某个元素        e的概率计算如下所示：

5、Path Relinking

路径重连算法从一个或者多个精英解出发，通过对比精英解之间的共有特性来构建新的解，以求能够得到更好的解。在选定两个精英解初始解(initial solution)和导向解(guiding solution)之后，路径重连算法通过探索初始解的邻域，寻找这些邻域中和导向解有相似部分的邻域进行计算，最终判断是否能获得更优的解。路径重连详细内容够可以参见微博： 路径重连(Path Relinking)算法简介。

6、并行GRASP(parallelism)

采用多线程的编程方式来加快最优解的寻找速度，可以有以下两种方式来应用并行策略，一种为独立线程方式mtltiple-walk independent thread strategy，另一种为合作线程方式mtltiple-walk cooperative thread strategy。

6.1 mtltiple-walk independent thread strategy

这是一种比较容易实现的多线程求解方式，对于每个优化过程开一个独立的线程进行运算，开一个总的线程来记录最优解即可。这种方式由于不需要线程之间共享信息，所以比较容易设计和实现。在某个线程找到更优解之后，所有的线程都暂停求解，更新每一个线程中的最优解为当前找到的最优解。

6.2 mtltiple-walk cooperative thread strategy

这种多线程方式涉及到线程之间共享信息，所以操作会更加复杂。一种共享信息的方式是通过路径重连算法来实现。实现方式是：给所有的线程建立一个共享的精英解池，之后在每一个线程应用路径重连技术的时候，都会从共享精英解池中选取精英解和自己的当前解进行路径重连探索。