一、旅行商问题(Traveling Salesman Problem)介绍
旅行商问题描述如下：假设有若干个城市，且任何两个城市之间的距离是确定的，现有一个旅行商人要拜访这些城市，要求旅行商从某城市出发，必须经过每个城市，且每个城市只能拜访一次，最后要回到出发的城市，问如何确定一条路线使路径长度最短。
详细介绍见blog：LocalSearch之爬山算法
二、构建算法（Constructive Algorithms）简介
由于启发式算法所使用的基础技术的不同，可将其分为构建性方法和局部搜索法。
2.1 构建算法与Local Search的区别
构建算法是从一个空解开始，通过迭代逐步将解决方案组件添加到最初为空的解决方案中，直到构建出一个完整的解决方案。局部搜索算法是从某个随机生成的初始解开始，通过局部变化反复尝试改进当前解，直到满足某种标准时停止改进，得到最终解[1]。
两者都可用来解决较复杂的组合优化问题，构建启发式一般用于快速生成初始解，后续可用局部搜索算法做进一步改进。
2.2 构建算法的特点
构建性算法以增量方式构建组合优化问题的解决方案，该算法要一步一步地添加解决方案组件，无需回溯，直到生成完整的解决方案。
其中组件的添加顺序可以是随机的，也可以采用某种启发式规则，比如较常用的贪婪构造启发式，所以构建算法有时也叫做贪婪算法（Greedy Algorithm），主要思想是在每个构造步骤中添加一个解决方案组件，而且该组件具有由评估函数估计出的最大效益。
构建算法最大的优点是简单直观，只需逐一分配所有决策变量的值，并在每一步做出最佳决策；但缺点是该方法太看重短期利益，缺乏全局观及长远考虑，因为在每一个单独的步骤中所做出的最优决策并不是总能够组合成一个总体最优的解决方案，纯粹的贪婪容易使问题陷入局部最优的局面。
三、GRASP算法简介
3.1什么是GRASP算法
GRASP (Greedy Randomized Adaptive Search Procedures)是一个用于求解组合优化问题的多起点（multi-start）元启发式算法，每一次迭代都包含以下两个阶段：构造(Construction)和局部搜索(Local Search)。在构造阶段会构建一个可行解，在局部搜索阶段会对可行解的邻域进行搜索直到找到局部最优解[2]。
1、GRASP伪代码解释
·GRASP的整体流程伪代码如下图所示：
图3-1 GRASP伪代码
其中Max_Iterations表示最大的迭代次数，seed表示随机数种子。
伪代码基本流程如下：
⑴读取输入信息和数据；
⑵到达最大迭代次数之前做以下步骤；
⑶迭代之前先贪心随机构造一个初始解；
⑷然后判断可不可行；
⑸若不可行，则进入Repair函数进行修正；
⑹构建阶段结束；
⑺对可行解进行局部搜索；
⑻局部搜索过程中若找到更好的解则对当前最优解进行更新；
⑼局部搜索阶段结束；
⑽返回值为当前最优解。
·下图是构建(Construction)阶段流程的伪代码：
图3-2 构建阶段伪代码
在每次迭代之前，初始化解S为空集，初始化候选集并对候选集的每一个元素进行评估，作为进入限制候选列表的依据。每次迭代从候选集中选部分元素构成限制候选列表RCL，并且每次从RCL中随机选择一个元素与可行解S进行合并，然后更新候选集的元素，同时对候选集里面的每一个元素进行重新评估。
·下图是局部搜索(Local Search)阶段流程的伪代码：
图3-3 局部搜索阶段伪代码
局部搜索(Local Search)对构建的解Solution进行邻域N(Solution)的搜索，若找到优于Solution的解，则进行最优解的替换，直到找到局部最优解。
2、RCL（Restricted Candidate List）的构建
初始解的构建阶段是GRASP算法中比较重要的部分，一个好的初始解输入可以在增加局部搜索阶段找到最优解的几率的同时缩短求解时间，而在初始解构建的过程中，RCL（限制候选列表）的构建又是不可或缺的一环。
下图是展开RCL构建过程的伪代码：
图3-4 RCL构建伪代码
伪代码第4-7行表示RCL的构建过程，即将某个未加入到解中的元素e插入到正在构造的部分解中，并衡量元素e加入到解前后的变动成本C(e)，之后设置一个阈值参数
来限制元素数量p，RCL就是由具有最佳变动成本的一定数量p的元素e组成。最后从RCL中随机选择一个元素来继续构建解决方案，而且在下一次构建时要重新对限制候选列表RCL进行元素更新，直到所有的元素均在最终解决方案之中。
而且每一个可以加入到限制候选列表RCL中的元素e必须满足下式：
其中α∈[0,1]，可知当α=0时，RCL中只有一个元素，则构建过程变得完全贪婪；当α=1时，RCL包含所有可行元素，则构建过程变得完全随机。所以参数α的取值对控制构建过程的贪婪程度有很大影响。
3、Reactive GRASP (α值的确定)
在Reactive GRASP这种方式下，参数α的取值不是固定的，而是根据求解的结果进行动态自适应调整的。
首先定义ψ={α1,...,αm}表示参数α所有可能的取值，而每一个取值的初始选择概率相同，均为pi=1/m,i=1,...,m；设z*为当前解的目标函数值，Ai表示使用每一个α值迭代运行历史以来所得的目标函数求解质量的平均值，在每一次局部搜索结束之后，首先更新Ai的值，并计算适应度qi=z*/Ai，基于更新后的概率值，可以采用轮盘赌等方法选择出下次迭代过程使用的α值。
当在某一参数α值下得到的qi值比较大时，表明该参数值α更适合用来解决当前的问题，后续迭代过程中该α值被选中的概率也会有所增加。
3.3 GRASP的扩展
（1）过滤策略常用于加速GRASP算法的迭代：过滤后则不必对构造得到的所有解进行局部搜索，可以仅对未访问的有潜力的解进行局部搜索。
（2）GRASP算法与VNS结合使用：因为GRASP算法的随机性基本在构建阶段，VNS算法的随机性基本在局部搜索阶段，二者互补。
（3）GRASP算法与GA结合使用：GRASP构造阶段的贪婪随机策略可用于生成GA的初始种群。
3.4 GRASP算法的优缺点
1、GRASP算法的优点
（1）结构简单，易于实行
（2）若存在已构建的贪婪算法，则很容易延伸出GRASP算法
（3）可以用于解决大型优化问题
2、GRASP算法的缺点
（1）容易陷入局部最优
（2）容易多次找到重复的解
四、用GRASP算法解决TSP问题
4.1 matlab代码实现（代码见文末链接）
图4-1为GRASP算法的主循环，分别对应构造初始解、对初始解进行局部搜索、解的更新三个部分。
图4-1 主循环代码
图4-2为构造初始解的局部函数Greedy_Randomized_Construction，及其与伪代码间的对应。
图4-2 构造初始解部分代码
图4-3为评估候选列表的局部函数evaluateCL
图4-3 评估候选列表部分代码
图4-4为Reactive GRASP方式下，采用轮盘赌方式选择参数α的代码，图4-5为参数集初始化部分代码。
图4-4 参数选择代码
图4-5 参数集初始化代码
4.2 实验结果展示
对TSP问题中的Berlin8算例进行分析，参数设定最大迭代次数MaxIter=1、不改进迭代次数noIter=50、参数alpha=0.5、局部搜索算子选择2opt、选择策略为bestImprove，为保证结果可复现，采用函数rng确定随机种子。得到结果如图4-6所示。
图4-6 实验结果
从实验结果中可看出GRASP算法过程。
首先为初始解的构造过程，起初当前解为空时，CL和RCL均有8个元素，随机选中点4；基于当前解4及其阈值限制，构建的受限候选列表（RCL）只有四个元素，随机选中6，当前解变为4，6；按相同步骤直至候选列表（CL）为空，得到完整的初始解。初始解目标值为3472。
接着利用VND对初始解进行局部搜索，VND后目标值为2898。
因参数设置MaxIter=1为1次迭代，则循环结束，得到本次迭代的最优解。
GRASP通过Multi-Start进行迭代搜索，由于GRASP在构建过程存在贪婪随机性，因此多次迭代，每次迭代的构建的初始解不同，结合局部搜索可一定程度跳出局部最优解。但GRASP对历史迭代过程没有记忆性，是该算法的一个不足之处。Reactive、PathRelinking等策略可一定程度弥补单纯GRASP的不足。
4.3 不同参数下的实验结果对比
对TSP问题中的Berlin8算例进行分析，参数设定局部搜索算子选择2opt、选择策略为bestImprove。
不同迭代次数下，改变参数alpha得到不同实验结果如图4-7。Alpha=0时初始解的构建完全贪婪，alpha=1时初始解的构建完全随机，可知较少迭代次数内，完全贪婪得到的结果较好，完全随机得到的结果较差。若将最大迭代次数设为100次，不改进迭代次数设为30次，则alpha=0和1均能得到2551目标值。
图4-7 实验结果对比
Reactive GRASP方式下，设置概率集alphaset为[0.1:0.1:0.9]，对Berlin8和Berlin52算例分别进行测试，改变参数最大迭代次数和不改进迭代次数，得到结果如图4-8。非首次迭代时，基于历史该alpha取值的平均求解质量赋值概率，每次迭代以轮盘赌方式选择alpha值。
图4-8 实验结果对比
五、小结
本文介绍了GRASP（贪婪随机自适应搜索算法）的基本原理，并结合实例，在Matlab中运用GRASP解决TSP问题，展示了限制候选集的选择概率对于实验结果的影响。
【囿于作者的学术水平，本文的诸多表述或许不够严谨，用途仅限于优化算法入门者的非正式学术交流，不足之处还望各位读者指正。】
参考文献
[1] M. G. C. Resende and C. C. Ribeiro (2003) Greedy randomized adaptive search procedures. In F. Glover and G.
[2]Macro Dorigo and Thomas Stutzle. Ant Colony Optimization .2004.
相关资料
作者：丁子千 刘梦迪
校对：朱燕燕
