Greedy Randomized Adaptive Search 算法超详细解析，附代码实现TSP问题求解
GRASP（贪婪随机自适应搜索）
介绍
- 在算法的每次迭代中，主要由两个阶段组成：构造（construction）和局部搜索（ local search）
- 构造（construction）阶段主要用于生成一个可行解，而后该初始可行解会被放进局部搜索进行邻域搜索，直到找到一个局部最优解为止
整体框架
伪代码
GRASP伪代码
- Greedy_Randomized_Construction：在贪心的基础上，加入一定的随机因素，构造初始可行解。
- Local Search：对上面构造的初始可行解进行邻域搜索，直到找到一个局部最优解。
贪婪随机构造伪代码
- 一开始解是一个空集。
- 初始化候选元素的集合，这里候选元素是指能放进Solution的元素（也就是目前Solution里面没有的），比如１，２，３……。
- 对候选集合的每个元素进行评估，计算将元素x放入Solution会导致目标函数f改变量△x。
- 根据△x对各个元素排序，选取部分较好的候选元素组成RCL表（贪心性体现在这里）。
- 随机在RCL中选取一个元素放进Solution。（算法的随机性）
- 更新候选元素集合，然后对每个元素进行重新评估计算△值。（算法的自适应性体现在这里）
α参数主要是控制RCL的长度
- 当α=0时，纯贪心，只能选取最优的候选元素。
- 当α=1时，纯随机，所有候选元素都可随机选。
