端到端组合优化

Memory-efficient Transformer-based network model for TravelingSalesman Problem

Hua Yang, Minghao Zhao, Lei Yuan, Yang Yu, Zhenhua Li, and Ming Gu. "Memory-efficient Transformer-based network model for Traveling Salesman Problem.", Neural Networks 161 (2023): 589-597.

模型在解决 中存在局限性：

计算复杂度是二次的， 中的操作导致时间和空间的复杂度为 。（ 是输入序列的长度）

内存需求过高，导致内存不足。

强化学习中马尔可夫决策过程的变量为：状态， 为当前已访问的节点的有序序列。动作， 为下一个访问的节点。奖励，。转移，从当前为访问过的节点集合中选择一个点，加入到已访问的节点集合中。策略， 为一个神经网络， 是网络的可训练权值。

Tspformer architecture

中的 被定义为： ， 是序列长度， 是头的个数， 是嵌入维度。（实验中 ）

其中主要的注意力来自于点积值，可以对查询数据进行采样，从而使得矩阵乘法运算的数据减少。

采样 的个数为 ， 是一个微调参数，。采样 表示为 。

用矩阵乘法来求 和 的兼容性： 取概率最高的前 个值为 ，即为值最大的前 个值。然后根据 对数据查询进行采样，得到 。

再次计算 和 的兼容性： 屏蔽访问过的节点后，计算注意力值： 这里 都是可学习的矩阵。这里假定线性投影的隐藏维度都一样大，。（实验中 ）

Encoder 的 和 的 的区别只有将 换为了 。

Decoder 的 去掉了 的 中的第一个组件，即 。用自回归来每一次预测节点，用贪婪搜索和束搜索来改善解空间。

Model training with reinforcement learning

损失函数： 用随机梯度下降和策略梯度方法来优化参数，用 算法来计算梯度的更新： 用贪婪算法来作为 。

为了构造 和单次采样，用蒙特卡洛抽样来采样 ：

Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer

Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. "Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer.", Conference on Neural Information Processing Systems abs/2110.02544 (2021): 11096-11107.