高效探索学习解决组合图分区问题(基于强化学习的优化算法)

二叉树上的我收录于机器学习 python

2023-08-23 约 1770 字预计阅读 4 分钟

前言

老板下指示复现两篇文章，这是其中一篇

https://arxiv.org/pdf/2205.14105v1.pdf

文章的原理什么的已经大部分明白了但仍然有部分懂，故而做下记录，以备后续复现或深入了解

原始数据

ER40/BA40到ER500/BA500

https://ojs.aaai.org/index.php/AAAI/article/download/5723/5579

https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.74.47

分别命名为ER和BA数据集

ER800到ER10000

https://www.sciencedirect.com/science/article/abs/pii/S0952197612002175

实验的问题

最大割（Max-Cut）问题的目标是将一个给定的无向图中的节点分成两个不相交的集合，使得割（即连接两个集合的边）的数量尽可能多。换句话说，要找到一个划分，使得划分的边的数目最大化。

形式化地说，给定一个无向图 G = (V, E)，其中 V 表示节点的集合，E 表示边的集合，Max-Cut问题的目标是找到一个节点划分 (A, B)，其中 A 和 B 是不相交的子集，使得划分的边的数量尽可能多。数学上，目标可以表示为最大化以下函数：

maximize E(A, B) = {(u, v) ∈ E : u ∈ A 且 v ∈ B} 的大小。

优化思路

构建了一个新的算法 ECORD（具有递归解码的探索性组合优化），它将单个GNN预处理步骤与快速行动解码相结合，从而用简单的顶点观察和对正在进行的优化轨迹的学习表示来替代进一步的几何推理。

这里的翻转实际就是属于哪个子集，对于每个顶点，都提供以下信息：(i) 当前标签，(ii) 如果翻转该顶点会导致的切割值的立即变化（被称为“预览”）和 (iii) 自上次翻转节点以来的步数。

目标观察是当前状态和最佳观察状态之间切割值的（归一化）差异，以及当前状态中任何顶点的最大预览值。

ECORD的伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


对于每一批次的 episodes 做如下循环：
    从分布 D 中随机采样一批 BG 图 G(V, E)。
    使用图神经网络计算每个顶点的嵌入向量。

    对于每个 episode 中的时间步 t 做如下循环：
        计算用于反向传播的时间步数 k0。
        对于批次中的每个图 Gj 做如下循环：
            根据策略选择动作 a(t)：
                - 以概率 ε 随机选择动作 a(t)。
                - 以概率 1 - ε 使用 softmax(Qθ(s(t),·) / τ) 方法选择动作 a(t)。
            
            更新解决方案集合 S(t+1)：
                - 如果 a(t) 不在 S(t) 中，则将其加入到 S(t) 中。
                - 如果 a(t) 在 S(t) 中，则将其从 S(t) 中移除。

            将元组 m(t) = (s(t-k0), ..., s(t+1), a(t-k0), ..., a(t), r(t), d) 添加到经验回放内存 M 中。
            # 这个元组包含了状态、动作、奖励等信息，用于训练模型。

            如果 t 模除 fupd 等于 0，则进行如下操作：
                从经验回放内存 M 中随机采样一批经验 M(t)。
                使用 BPTT 方法从时间步 t 到 t - k0 进行反向传播，更新模型参数 θ。

                更新目标网络的参数 θ：
                θ ← θτupd + θ(1 - τupd)
            结束
        结束
    结束
结束

优化点

ECO-DQN在每个决策步骤都使用了昂贵的GNN，再加上推理过程中的探索轨迹，导致其扩展性甚至不如S2V-DQN，并且仅用了一些手工特征来表示先前的搜索轨迹。

ECORD通过使用初始GNN嵌入，然后使用循环单元来平衡图网络提供的信息与基于学习的轨迹表示之间的关系，弥补了这一缺点。

目录