1、路径重连的定义(Defination)

Path relinking 是一种集中搜索策略。

作为一种辅助求解组合优化问题启发式算法的手段，path relinking经常被用来同其他启发式算法或者元启发式算法进行组合，并且在求解速度和求解质量方面起到了重要作用。

2、路径重连的模板和机制(Templates and mechanics)

Path relinking被用来探寻组合优化问题中“优质解”的轨迹(trajectories)。

首先定义某个组合优化问题的求解空间 G = ( F , M ) G=(F,M) G=(F,M) ，求解空间中的节点集合表示为 F F F ，边集合表示为： G G G 。当且仅当 S ∈ F S \in F S∈F S 1 ∈ F S^1\in F S1∈F 并且 S ∈ N ( S 1 ) S\in N(S^1) S∈N(S1) S 1 ∈ N ( S ) S^1\in N(S) S1∈N(S) 时，认定边 ( S , S 1 ) ∈ M (S,S^1)\in M (S,S1)∈M，其中 S ∈ N ( S 1 ) S\in N(S^1) S∈N(S1) 和 S 1 ∈ N ( S ) S^1\in N(S) S1∈N(S) 分别表示节点 S S S 和 S 1 S^1 S1的邻域。

Path relinking通常对 F F F中的某两个解进行操作，一个是初始解 S i S^i Si ，另外一个是导向解 S g S^g Sg 。

为了搜寻更优的解，path relinking会搜寻一条或者多条路径和前两个解相关的解。在进行完路径重连算法之后，一般会进行local search来进一步提升解的质量。

3、有限邻域空间(Restricted Neignborhoods)

下面定义 S ∈ F S\in F S∈F 表示求解空间 G G G中连接初始解 S i S^i Si 和导向解 S g S^g Sg的任意解方案集合，在 S S S中，并不是所有的解都会被保留下来，只有和导向解 S g S^g Sg相似的解才会被加入到最终的解集合 中。定义 N ( S , S ∈ S g ) ∈ N ( S ) N(S,S\in S^g)\in N(S) N(S,S∈Sg)∈N(S)表示有限的邻域空间。

下面通过TSP的例子说明有限邻域空间的概念。

如上图所示，问题网络结构如上图(a)所示，当前解如上图(b)所示，导向解如上如(c )所示。(一般情况下，导向解目标函数值应该小于当前接解目标函数值，此处导向解的目标函数值19要大于当前解目标函数值17，下述会指出，在目标最小化问题求解时，反向路径重连算法这样处理可以添加一定的扰动因素，有助于跳出局部最优解)。

当前解的路径序列为：1-2-3-4-5；导向解的路径序列为：1-3-5-2-4。在出发地点1保持不变的情况下，当前解的邻域 包含下述6条路径(将除地点1之外的其他四个客户点进行两两互换)：1-3-2-4-5；1-4-3-2-5；1-5-3-4-2；1-2-4-3-5；1-2-5-4-3；1-2-3-5-4。上述邻域中，只有四条路径可以加入到有限邻域集合 中：1-3-2-4-5；1-2-5-4-3；1-4-3-2-5；1-2-3-5-4，因为这四条路径和导向解在相同位置访问了相同的客户点，有相似性。

当前解搜索到的四种限制邻域解如下图所示。

4、极小化问题前向路径重连模板(Forward Path-Relinking)

前向路径重连算法中，导向解 S g S^g Sg的目标函数值要不次于当前解 S i S^i Si的目标函数值。

前向路径重连的伪代码如下图所示。

① 其中1-3行表示当前解，当前最优解和当前最优解目标函数的初始化；

② 第4行判断条件表示若有限邻域集合中还有未探寻的邻域，则继续探寻；

③ 第5行表示计算当前选定的邻域解的目标函数值；

④ 6-8行表示若当前邻域解目标函数值优于最优解目标函数值，则将最优解和最优目标函数值进行替换。

⑤ 路径重连算法结束之后，第11行表示对路径重连获得的最优解进行local search局部搜索，看是否能够获得更优的解。最终将上述找到的最优解返回。

在这里插入图片描述

5、极小化问题反向路径重连模板(Backward Path-Relinking)

反向路径重连算法中，导向解 S g S^g Sg的目标函数值要不优于当前解 S i S^i Si的目标函数值。其余操作同上述图4.1中的伪代码相同。

正向路径重连、反向路径重连和混合(双向)路径重连算法的示意图如下图所示。

6、极小化问题双向路径重连模板(Mixed Path-Relinking)

结合正向路径重连算法和反向路径重连算法，首先进行正向路径重连算法，从当前解 S i S^i Si向导向解 S g S^g Sg( f ( S g ) ≤ f ( S i ) f(S^g)\leq f(S^i) f(Sg)≤f(Si))进行探索；正向路径重连执行一次之后，将当前解 S i S^i Si和导向解 S g S^g Sg进行互换，进行反向路径重连算法，从当前解 S i S^i Si向导向解 S g S^g Sg进行探索 ( f ( S i ) ≤ f ( S g ) f(S^i)\leq f(S^g) f(Si)≤f(Sg))。重复上述步骤，直到邻域解集合为空时结束路径重连算法。

双向路径重连算法执行示意如下图所示

双向路径重连算法伪代码如下图所示。

参考书籍（Reference）

[1] Optimization By GRASP

https://link.springer.com/book/10.1007/978-1-4939-6530-4