VRP-TSP系列论文2 2023-06-17 组合优化 暂无评论 118 次阅读 LEARNING A LATENT SEARCH SPACE FOR ROUTING PROBLEMS USING VARIATIONAL AUTOENCODERS ICLR 2021  ## 解决问题：TSP、CVRP ## 前置知识：VAE、CVAE + VAE (Variational Auto Encoder)  目标：生成服从P(x)分布的数据， 训练集：x~P(x) 推断网络把x编码到隐空间中的隐变量Z，生成网络把隐空间中的隐变量Z还原成x', x'仍然服从分布P(x) 假设隐空间服从高斯分布，那我们从标准高斯分布采样一个Z输入生成网络，就是把一个高斯噪声输入生成网络，可以认为输出的x'会服从分布P(x) 基于这个假设以及一系列数学推理，训练VAE, Loss公式：  第一项的KL散度是用来保证隐变量 Z 的总体是服从单标准高斯分布的，后边一项是保证生成器可以很好的从隐变量还原到数据。 + CVAE (Conditional Variational Auto Encoder) CVAE中需要根据输入的条件来进行输出。 隐变量采样的时候，不再是从P(Z)=N( 0,1 ) 中直接采样，而是从P( Z | Y )=N( Z | u(Y), I ) 中进行采样 就是通过条件改变隐变量的均值，从而控制了隐变量采样的位置，控制最后的输出结果。 相应的Loss变成：  ## 本文方法 目的：通过CVAE训练一个生成网络$p_\theta$ , 能够以自回归的方式生成下一步解的概率分布，进而引导搜索得到解。    ### Trainning  就是按照CVAE的范式训练，自回归 ### Search  图 1b 显示了迭代搜索过程，其中解码器 p(s|l, z) 与任何无约束连续优化器一起使用来搜索问题实例 l 的解决方案。无约束连续优化器通过学习的潜在搜索空间来导航搜索。在每次迭代中，优化器都会输出一个向量 z 来描述潜在搜索空间中的一个点。解码器基于 z 生成解 s'，并将 s' 的目标函数值返回给优化器。通过有效的优化器和学习的搜索空间，可以找到 l 的高质量解决方案。  作者在实验中使用两种不同的无约束连续优化器（unconstrained continuous optimizer）：基本差分进化（DE）算法和随机搜索（RS）。 + CVAE-Opt-DE + Instead of generating one offspring solution at a time, we decode and evaluate a batch of solutions per iteration. + DE 算法在隐空间中维护了一个向量群体（a population of vectors），并通过交叉和变异改进这个向量群体。 + population size of 600，At each iteration of the DE algorithm, 600 offspring vectors are generated and decoded in one batch. (在 DE 算法的每次迭代中，一个batch生成和解码 600 个后代向量。) + 初始群体向量是从有界搜索空间中均匀随机采样的。为了确定边界，作者将 1,000 个单独的模型验证实例使用编码器编码为潜在空间中的点。然后选择边界，使 99% 的点坐标都在边界内。这确保了搜索在解码器已知的潜在搜索空间区域中运行，即使编码器的后验分布与标准高斯分布有很大不同。 + decoder贪婪地生成解决方案（即，在每一步中选择具有最高概率值的动作） + CVAE-Opt-RS + 隐变量z是从高斯分布中随机采样的，不是从一个有界空间中初始化并在每次迭代时通过交叉变异更新。 + 其它设定和CVAE-Opt-DE一致。 ## 训练 有监督训练 + 训练集： TSP: Concorde CVRP: LKH + 对称解： 一个解对应很多序列表示。 为了强制模型学习底层解决方案的表示而不是解决方案序列，我们训练模型为输入重现对称解决方案，而不是与输入完全相同的解决方案。训练期间使用的对称解决方案是为每个时期随机选择的。 也就是从很多序列表示中随机选择一个序列作为ground truth。 ## 实验 + 对比实验   + 泛化实验 在具有 100 个节点的实例上训练的模型来解决具有 95、105、125 和 150 个节点的实例  + 对称性的实验（SYMMETRY BREAKING）  + 超参$\beta$ 的实验（INFLUENCE OF β）  + 消融实验 把CVAE换成一个手工设计的解码模式（Genetic algorithms and random keys for sequencing and optimization.用于排序和优化的遗传算法和随机密钥）  ## 总结 作者的话：提出了 CVAE-Opt，一种使用变分自动编码器来学习路由问题解决方案到连续（潜在）搜索空间中的点的映射的方法。学习空间可以通过任何基本的无约束连续优化器来搜索。 有监督，规模小，对比方法少。实验做的挺多。 我对作者所说的无约束连续优化器其实不太明白。 --- DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems NeurIPS 2022  ## 解决问题： TSP、MIS ## 前置知识 ### Meta-Learning 元学习Meta Learning，含义为学会学习，即learn to learn。 meta-learning 想法的来源： 人类认识新的物体并不需要很多的样本作为支撑，这从某些角度说明人类在学习一个新任务的时候，比机器学习模型拥有更多的先验知识。 比如说，我小的时候知道了书本是方的，杯子是圆的，那么我不光知道了如何分类书本和杯子，我还同时建立了这么一个概念：“形状不同的物体很可能不是同一类物体”。同理我有很多其它的知识，比如”颜色不同，物体不同“。这些知识归结起来，可以认为是规定了我“如何去学习一个新知识”的方法。所以很多年以后我再看到鼠标和键盘的时候，我不需要见识特别多的键盘和鼠标，只要根据以往的经验，看看颜色，看看形状，我发现根据形状能很轻易地判断鼠标和键盘，于是我就很快知道了该如何区分这两者。 所以有的人就这么想：虽然我要做的这个数据集数据很少，但是我有很多其它大的数据集。如果模型可以先在其它大的数据集上学到这些有关“该如何学习新的知识”的先验知识，由此让模型先学会“如何快速学习一个新的知识”，然后用这些先验知识来更好更快地在我要做的小数据集上学习。 ### MAML (Model-Agnostic Meta-Learning) 已经被提出的元学习模型有很多，MAML属于learning good weight initializations的一类，MAML学习一个好的初始化权重，从而在新任务上实现fast adaptation >[Model-Agnostic Meta-Learning （MAML）模型介绍及算法详解 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/57864886) 我理解的范式：meta-learner + base-learner + base-learner是在目标数据集上被训练，并实际用于预测任务的真正的数学模型。 + meta-learner是给base-learner提供初始化参数，是用于learning to learn的 + gradient by gradient，它有两次梯度更新的过程 也就是分别更新base-learner和meta-learner，假设原模型也就是meta-learner是 $\theta a$ ，我们复制了它，得到base-learner $\theta b$。在 $\theta b$ 上，我们做了反向传播及更新参数，得到第一次梯度更新的结果 $\theta b$′ ，这是更新base-learner的梯度。接着，在 $\theta b$′上，我们将计算第二次梯度更新，此时需要先在 $\theta b$′上计算梯度，然后更新 $\theta a$ 的梯度，这是更新meta-learner的梯度。 + 最终目的是得到一个好的meta-learner，也就是一个好的初始化权重，可以在新任务上迅速收敛并完成fine-tune。 原论文的算法流程：  对应的强化学习流程：  ## 本文的方法 受 MAML 的启发，作者希望在一组问题实例上训练图神经网络 (GNN)，使其能够捕获所有实例的共同性质，并根据每个输入图的特征/结构有效地调整其分布参数以适应每个实例。 推理： + 主干网络是GCN，meta-learner和base-learner都是GCN，meta-learner以及训练好了，参数为 $\phi$ + 对于每个实例，meta-learner初始化base-learner为参数 $\phi$ ,即一个参数为 $\phi$ 的GCN，GCN输出是a continuous parameterization $\theta$ ,(感觉可以理解成heatmap ， $\theta_{i j}$ 正相关于i到j的概率) + 主动搜索，fine-tune，通过REINFORCE方法更新base-learner的参数为 $\phi^T$ + fine-tune后，GCN的参数为$\phi^T$ ，再输出新的continuous parameterization $\theta^T$ + 利用 $\theta^T$ 通过greedy search、beamsearch、MCTS等搜索策略搜索解。 训练： 目的是训练得到meta-learner，即参数为 $\phi$ 的GCN + 对于每个实例，meta-learner初始化base-learner为参数 $\phi$ ,即一个参数为 $\phi$ 的GCN，GCN输出是a continuous parameterization $\theta$ + 主动搜索，fine-tune，利用 $\theta$ Sample得到解，然后通过REINFORCE方法更新base-learner的参数为 $\phi^T$ + 更新后GCN的参数为$\phi^T$ ，再输出新的continuous parameterization $\theta^T$ + 利用 $\theta^T$ Sample得到解，计算梯度更新meta-learner的参数 $\phi$ 。     ## 训练 强化学习：REINFORCE ## 实验 + 对比实验  + 消融实验  (a) 为了研究元学习的有效性，我们考虑两个维度的消融：（i）有或没有内部梯度更新：在目标函数中是否使用 $f_\phi(Ks , As)$ 或 $θ^T_s$ ； (ii) 在推理阶段有或没有微调。 (b) 我们研究在训练和测试期间微调部件的效果。通常，我们使用的神经架构是附加了 MLP 的 GNN，其输出是连续参数化 θ。 我们考虑以下微调部分：（i）连续参数化（Cont.Param.）； (ii) MLP的参数； (iii) GNN的输出和MLP的参数； (iv) GNN 和 MLP 的参数。 (c) 我们还研究了训练过程中内部梯度更新步数 T 的影响。 (d) 为了研究 DIMES 的连续参数化对于 MCTS 的良好性能至关重要的地方，我们将其替换为以下热图：(i) 每个值都是从 Unif(0, 1) 独立采样的； (ii) 1/(ri + 1)，其中 ri ≥ 1 表示第 i 条边的长度在与其共享源节点的边中的排名。这可以被视为最近邻启发法的近似。我们还与 Att-GCN 热图进行比较 ## 总结 把元学习的范式MAML套用到CO问题 图神经网络，heatmap，主动搜索，强化学习（REINFORCE） 个人感觉上，不用元学习也可以吧，就是训练GCN生成heatmap，结合主动搜索fine-tune，再用beam search、MCTS等搜索。 作者为了定义这样一个元学习的问题和训练过程，定义公式套了一层又一层，看不明白，我好菜。 标签: 组合优化 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭