第11章 GRASP greedy random adaptive search procedure

Greedy Randomized Adaptive Search procedure，贪婪随机自适应搜索（GRASP），是组合优化问题中的多起点元启发式算法，在算法的每次迭代中，主要由两个阶段组成：构造（construction）和局部搜索（ local search）。 构造（construction）阶段主要用于生成一个可行解，而后该初始可行解会被放进局部搜索进行邻域搜索，直到找到一个局部最优解为止。

• 搜索步骤

  • constraction：构造一个可行解（不可行，则将其修复为可行，若修复不了，则丢弃，生成新解）
  • local search：在领域中搜索直到达到局部最优

    相关概念

• greedy randomized

  • 定义：从可行元素中取出一部分较优的元素，随机从中选择一个
  • 适用场景：1）构造初始解；2）构造基于种群的元启发式算法（如遗传算法）的初始解；3）元启发式算法迭代过程中生成新解
• 邻域：由解经过一个算子得到，与往往只有几个元素不同。当时，时局部最优。
• 局部搜索：在邻域中搜索其他解，影响局部搜索性能的因素：1）邻域结构；2）邻域搜索方法；3）解评估速度4）初始解
• 限制邻域和候选列表：限制邻域可以缩小搜索范围，提高搜索效率。通过使用一些记忆结构可以提高候选列表的效率：1）aspiration plus, 2）elite candidate list, 3）successive filtering, 4）sequential fan candidate list, 5）bounded change candidate list。
• 强化和多样化（Intensification and Diversification ）：
  • 强化：在GRASP中，经常使用path-relinking
  • 多样化：通过扰动达到多样化，惩罚(penalty)和激励(incentive)使用的较多

• path-relinking：将一个[精英]解变换为另一个[精英]解，每次只变换一个元素，保留变换过程中的解，移动结束后，选择最好的解。

  GRASP模板

  
  候选列表（RCL）的长度是影响算法性能很重要的一个参数，控制RCL的长度有两种方式:

• 通过参数设定c(e)的取值范围，如伪代码2中的方式。当时相当于纯贪婪，当想当于纯随机，所以的值可以控制贪婪和随机的程度。

  • 固定的效果往往并不好，如使用固定值，推荐取值为。
  • 使的值变化有多种方式：1）每次迭代时，随机取一个0到1之间的值；2）根据迭代，自适应选择。有大量的文献，研究变化的模式对解的影响。
• 设定RCL的绝对长度：
  • random plus greedy: 前个元素使用随机选择方式，剩下的元素使用贪婪选择方式。
  • sample greedy:从中依次以贪婪的方式挑选个元素放入RCL中越小，越随机
    

GRASP with path-relinking

GRASP在每一次迭代时没有利用已经搜索过的信息，而path-relingking则记录了搜索路径，将两者结合，可以提高搜索效率。path-relinking主要用于后优化阶段(post-optimization phase：在两个精英解之间)和强化策略（intensification stategy，在局部搜索之后的局部最优解 与 精英解之间）。path-relinking主要有以下三个元素构成：（伪代码只是一个示意，不用拘泥于其中每个元素的选择方式）

• initial solution：1）经过局部搜素之后的局部最优解；2）任意精英解
• guiding solution：1）随机从精英解中选择一个；2）计算每个精英解与initial solution的差异，差异越大，被选择的概率越高；后者的搜索路径往往更长。
• 搜索策略：1)forward, 2)backward, 3)forward and backward, 4)mixed, 5)truncated(被截去的), 6)greedy randomized adaptive, and 7)evolutionary path-relinking
  • forward：initial solution为局部最优解，对局部最优解的邻域搜索的更彻底
  • backward：guiding solution为局部最优解，对精英解的邻域搜索的更彻底。
  • forward and backward：搜索两次（=forward+backward）
  • mixed：在每一个path-relinking procedure 中交换initial solution和guiding solution
  • truncated：可以嵌入前四种方法中，只搜索initial solution和guiding solution附近
  • 文献证明，解的质量
• 精英解更新方式：
  • 当精英解的个数少于时，直接插入；
  • 若当前解好于精英解中的解，则1）替换目标函数最差的精英解或，2）替换最相近的精英解

Tricks of the Trade

1. GRASP的优点有1）易实施，2）参数少
2. 大多数元启发式算法受益于好的初始解。复杂度低且优良的初始解可以1）检测问题结构；2）降低局部搜索的时间，提高搜索效率
3. 构造RCL时，使自适应变化，往往能获得质量更高，更多样的解
4. 局部搜索可以使用最优提升（best-improving）或第一提升(first-improving)策略，或二者的结合。最优提升指，彻底搜索邻域后，选择最好的解；第一提升指当找到比当前解好的解时，便停止搜索。两种策略可以获得相同质量的解，但是后者速度更快，前者可能导致过早收敛
5. 邻域的定义可以更灵活，很多元启发式算法利用多种邻域来提高解的质量和搜索速度
6. 使用合适的数据结构和算法可以极大的提高局部搜索效率
7. Path-relinking策略对于提高解的质量，降低求解计算时间，提高算法的鲁棒性的作用非常大，结合问题特征设计的Path-relinking的效果更明显
8. 元启发式算法包含共同的策略，如1）贪婪结构，2）局部搜索，3）随机化，4）候选列表，5）多领域，和6）path-relinking。从其他元启发算法借用一些策略，或互相结合可以提高算法的效率。
9. 最好的算法是根据问题特征设计的算法，我们应该根据问题灵活设计和选择策略。

   参考资料

• Resende M.G.C., Ribeiro C.C. (2014) GRASP: Greedy Randomized Adaptive Search Procedures. In: Burke E., Kendall G. (eds) Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/978-1-4614-6940-7_11
• 最新文献：http://twitter.com/graspheuristic
• 相关微信文章：https://mp.weixin.qq.com/s/i0CrJ1ecZTT19la87cu06Q【from程序猿声】
• github算法实现：https://github.com/Valdecy/Metaheuristic-Local_Search-GRASP【Python，求TSP问题】