基于图方法的GED问题与RNA分子分类研究

### 基于图方法的GED问题与RNA分子分类研究 #### 1. 图编辑距离（GED）问题中的VPLS启发式算法 在解决图编辑距离（GED）问题时，VPLS（Variable Partitioning Local Search）启发式算法是一种有效的方法。 ##### 1.1 目标函数与约束条件 目标函数旨在最小化顶点和边分配的成本，其公式为： \[ \begin{align*} &\min_{x,y} \sum_{i\in V} \sum_{k\in V'} (c_v(i, k) - c_v(i, \epsilon) - c_v(\epsilon, k)) \cdot x_{i,k}\\ &+ \sum_{(i,j)\in E} \sum_{(k,l)\in E'} (c_e(ij, kl) - c_e(ij, \epsilon) - c_e(\epsilon, kl)) \cdot y_{ij,kl} + \gamma \end{align*} \] 其中，\(\gamma\) 是一个补偿常数，其表达式为： \[ \gamma = \sum_{i\in V} c_v(i, \epsilon) + \sum_{k\in V'} c_v(\epsilon, k) + \sum_{(i,j)\in E} c_e(ij, \epsilon) + \sum_{(k,l)\in E'} c_e(\epsilon, kl) \] 该目标函数通过用替换成本减去插入和删除成本来最小化分配成本。 F3 有三组约束条件： - \(\sum_{k\in V'} x_{i,k} \leq 1, \forall i \in V\)：确保每个顶点最多只能与一个顶点匹配。 - \(\sum_{i\in V} x_{i,k} \leq 1, \forall k \in V'\)：同样是为了保证顶点匹配的唯一性。 - \(\sum_{(i,j)\in E} \sum_{(k,l)\in E'\cup E'} y_{ij,kl} \leq d_{i,k} \times x_{i,k}, \forall i \in V, \forall k \in V'\)，其中 \(d_{i,k} = \min(\text{degree}(i), \text{degree}(k))\)：保证两个顶点对之间的边匹配得以保留。 ##### 1.2 VPLS启发式算法的主要特征 VPLS 是一种将混合整数线性规划（MILP）求解器嵌入启发式算法的元启发式方法。它主要通过在 MILP 公式的解空间中进行邻域探索来解决优化问题。启动 VPLS 启发式算法需要两个要素：MILP 公式和 MILP 求解器。 其主要步骤如下： 1. **计算可行解**：首先计算一个可行解 \(\overline{X}\)。 2. **定义邻域**：假设存在一个“特殊”二进制变量的分区 \(S \subseteq B\)，基于此定义邻域 \(N(\overline{X}, S)\)： \[ N(\overline{X}, S) = \{X_B | x_j = \overline{x}_j, \forall j \notin S\} \] 该邻域包含了所有与当前解 \(\overline{X}_B\) 中非 \(S\) 子集的二进制变量值相同的解，而 \(S\) 子集中的变量保持自由。 3. **搜索邻域**：调用求解器来解决受限的 MILP 公式，寻找邻域 \(N(\overline{X}, S)\) 中的最优解。如果求解器返回最优性证明，则新解就是该邻域中的最优解；若受限公式较难求解，求解器可强制停止并返回目前找到的最佳解。 4. **更新当前解**：用新解更新当前解 \(\overline{X}\)。 这个过程会重复进行，直到满足定义的停止准则。 ##### 1.3 VPLS 用于 GED 问题 为了使 VPLS 适用于 GED 问题，选择 F3 作为主要公式。在实现 VPLS 时，一个关键问题是如何定义集合 \(S\)。为了确保邻域包含高质量和多样化的解，需要仔细选择 \(S\) 中的变量。具体步骤如下： 1. **定义球体**：基于输入图 \(G\) 和半径 \(\delta\) 定义球体列表。对于图 \(G\) 中的每个顶点 \(i\)，球体 \(S_i\) 包含所有与 \(i\) 的距离最多为 \(\delta\) 条边的顶点。可以使用 Dijkstra 算法来计算两个顶点之间的最短路径。 2. **计算球体成本**：根据初始解 \(x_0\) 计算每个球体 \(S_i\) 的成本，公式为： \[ c_S = \sum_{\forall i\in S} c(i \to \text{assign}(i)) + \sum_{\forall (i,j)\in (S \times S )\cap E} c