4.2.1 基于无模型的强化学习方法
无模型方法在求解难解问题时主要关注于直接寻找最优策略，而不需要对环境进行建模，具体包括基于值函数估计的方法、基于策略估计的方法以及两者结合的 Actor-Critic 方法。
基于值函数估计的方法试图在与环境交互的过程中估计出每一
状态上每一动作对应的累积奖赏，从而得出最佳策略。典型的基于值函数估计的方法有 Q-learning 方法[62] 、Deep Q-Networks（DQN）方法[63] 和时序差分方法[64] 。近年来，基于值函数估计的方法在难解问题求解中得到了广泛应用。例如，Khalil 等人[65] 提出了一种结合 Q-learning 和图嵌入的框架，用于求解旅行商问题、最小顶点覆盖问题和最大割问题。给定问题实例图 G，该方法将图 G 作为输入，将部分解（图中部分节点的集合）作为状态 S，并将图中不属于当前状态 S 的一个节点作为动作 v。在每个时间步，智能体采取动作 v，并根据环境反馈的回报奖励 r 来更新 Q 值表，以估计状态 S 和动作 v 的 Q值。然后，根据 Q 值表选择具有最大收益的动作来进行决策。这种方法的核心思想是通过使用 Q-learning 算法和图嵌入技术，学习并优化状态和动作之间的 Q 值，从而指导求解难解问题的决策过程。Cappart等人[66] 设计了深度强化学习模型来确定与问题相关的决策图变量顺序，该模型可用于最大独立集问题和最大割问题。Bai 等人[67] 提出了一种图神经网络和深度Q-learning 相结合的检测最大公共子图的方法，该方法使用探索树在两个图中提取相应的子图，并通过 DQN进行训练以优化子图提取奖励。Song 等人[68] 提出了策略共同训练的元学习框架，该框架可以将强化学习和模仿学习作为子程序，从而改善单视图的学习模式。Barrett 等人[69] 提出了结合强化学习和深度图网络的探索性组合优化深度 Q 网络，该方法可以使智能体通过训练数据反馈不断改进解决方案。Liao 等人[70] 提出了一种深度强化学习方法来求解模拟环境中的全局路由问题，该方法使得智能体能够根据所提出的各种问题产生最优路由策略，并利用了深度强化学习的联合优化机制。Scavuzzo 等人[71] 提出了一种马尔可夫决策过程范式的泛化，为更一般的分支变量选择、强化学习算法和奖励函数提供了基础。 Qu 等人[72] 提出了一种新的基于强化学习的分支定界算法。该方法与离线强化学习类似，最初在演示数据上进行训练，以大规模加速学
习。随着训练效果的提高，智能体开始逐渐用学到的策略与环境交互。确定演示数据与自生成数据的混合比例是提升算法性能的关键。 Wang 等人[73] 提出了一种智能的深度强化学习算法来求解计算资源分配问题，该方法在 MEC 架构中引入基于 DQN 的 Software Defined Network（SDN）控制器。在 SDN 控制器中，智能体通过与 MEC 环境的持续交互可以采取行动并获得相应的奖励。He 等人[74] 开发了一个两阶段的框架来求解复杂调度问题，该方法将强化学习和传统运筹学算法结合在一起来求解调度问题。Jacobs 等人[75] 提出鲁棒优化来求解路径优化问题，该方法通过精确求解内部最小化问题来获得鲁棒解，并应用强化学习来学习外部问题的启发式方法。
相比基于值函数估计的方法，基于策略估计的方法不需要显式的估计每个状态或动作对应的 Q 值，而是直接输出下一步动作的概率，根据概率来选取动作。近年来，策略梯度、PPO 等基于策略估计的方法也逐渐应用于难解问题求解中。Tang 等人[76] 提出了一种混合整数规划求解器和强化学习相结合的切割平面选择方法，该方法将强化学习智能体作为整数规划算法框架中的子程序，动作则是增加新的切割平面，从而获得良好的收益。Yolcu 等人[77] 提出了一种图神经网络和强化学习相结合的随机局部搜索方法，该方法通过图神经网络计算变量选择启发式策略，并通过强化学习训练一套专门针对不同类别的启发式求解器，从而较好的求解布尔满足性问题。Ma 等人[78] 提出了一种图指针网络和分层强化学习相结合的方法来求解旅行商问题，该方法采用分层强化学习框架和 GPN 架构，有效的求解了带时间窗约束的旅行商问题。Nazari 等人[79] 提出一种使用强化学习求解车辆路径问题的端到端框架，该方法训练了一个单一的策略模型，仅通过观察奖励信号和遵循可行性规则，就能为类似规模的问题实例找到接近最优的解决方案。Deudon 等人[80] 将神经网络框架扩展到求解旅行商问题，该方法将城市坐标作为输入，使用强化学习训练神经网络，以
预测城市排列的分布。Kool 等人[81] 提出了一个基于注意力层的模型并使用强化学习来训练模型，从而求解旅行商问题。Bello 等人[82] 提出了一种循环神经网络和强化学习相结合的求解旅行商问题的方法。该方法在给定一组城市坐标的情况下，训练一个循环神经网络，并以负路径长度作为奖励信号，使用策略梯度方法优化循环神经网络的参数，从而预测不同城市排列的分布。Hu 等人[83] 提出了一种新的三维装箱问题，并将深度强化学习结合求解旅行商问题的方法实现对新型三维装箱问题的求解。Lu 等人[84] 提出一种迭代搜索的方法求解车辆路径规划问题。该方法在同一时间训练多个强化学习策略，并使用不同的状态输入特征。Sun 等人[85] 提出了一种搜索进化策略的网络，该网络策略使用强化学习并将变量选择过程建模为马尔可夫决策过程。
虽然基于值函数估计的方法和基于策略估计的方法在求解难解问题上获得了较好的效果，然而这些方法均存在明显的不足。基于值函数估计的方法不能直接得到动作值输出，难以扩展到连续动作空间上，并存在高偏差的问题。而基于策略估计函数估计的方法要对大量的轨迹进行采样，而每个轨迹之间的差异可能是巨大的，可能导致高方差和较大梯度噪声问题。为了解决高方差和高偏差之间的矛盾，基于值函数估计的方法和基于策略估计的方法被结合起来形成 Actor- Critic 方法。该方法构造一个全能型的智能体，既能直接输出策略，又能通过价值函数来实时评价当前策略的好坏。Emami 等人[86] 提出了 Sinkhorn 策略梯度算法（SPG），并为 SPG 算法引入的Actor-Critic神经网络架构，将状态空间的表示学习与 Sinkhorn 层解耦。Sinkhorn层产生置换矩阵的连续松弛，使 Actor-Critic 架构可以进行端到端的训练。Chen 等人[87] 提出了一种车辆路径规划的 NeuRewriter 策略。该策略分解为一个区域选择和一个规则选择模块，每个模块都由 Actor-Critic 方法训练的神经网络进行参数化。Malazgirt 等人[88] 提出
了一种 TauRieL 方法，该方法受 Actor-Critic 的启发，采用普通前馈网络来获得策略更新向量，并用该向量来改进生成策略的状态转移矩阵。Cappart 等人[89] 提出一种基于深度强化学习方法来求解约束规划问题，该方法将动态规划作为约束规划和深度强化学习之间的桥梁。 Gao 等人[90] 提出了一种学习局部搜索启发式算法的方法，通过行动者-评论家框架进行训练，迭代改进了车辆路径问题的求解方法。