自适应对抗学习求解旅行商问题

熊文瑞，陶继平

1.厦门大学 航空航天学院，福建 厦门 361005

2.厦门大学 大数据智能分析与决策重点实验室，福建 厦门 361005

在一般意义下，优化指的是按照某些确定的约束条件进行策略的选择，在满足约束条件的情况下，寻求在某个优化准则下的极值。组合优化问题是一类在离散状态下求极值的优化问题。在日常生活中，特别是运作管理中，有许多组合优化问题。典型的组合优化问题有背包问题、指派问题、旅行商问题等。这些类问题与实际生产联系紧密，具有重要的研究意义。传统求解该类问题的方法可以分为精确算法和近似算法两大类。

常用的精确算法有动态规划、分支定界、枚举等。精确算法只适用于求解小规模问题，一旦问题规模扩大，该种方法难以在较短时间得到最优解，不适用于实际的生产。

近似算法是指在合理的计算时间找到尽可能接近最优解的方法。近似算法可以分为三类：第一类是基于数学规划的近似算法，该种方法以数学模型为基础，采用列生成、拉格朗日松弛等方法求解问题，该类方法的优点是可以通过松弛问题的最优解为原问题提供一个下界，通过算法运行给出的问题的近似解为原问题提供上界，上下界进行比较，可以衡量算法性能；第二类是常规启发式算法，即根据问题的特点，按照经验或者某种规则设计的，该种方法的优点是直观快速，但解的质量不一定好；第三类是基于智能优化的近似算法，智能算法是一种通用的算法框架，需要根据问题的特点对算法框架进行修改就可以直接应用于不同的问题。

基于数学规划的近似算法不具有通用性且设计较为复杂。启发式算法虽然简单，但也存在迁移性不强的问题，一旦问题结构发生变化，原始方法将不再具有优势，必须重新设计新的模型来进行求解。智能优化算法虽然更具通用性，但是和启发式算法都依赖于初始解的质量。传统方法对于每个实例的求解过程都是独立进行，两个算例的求解过程没有任何联系，算法没有充分挖掘并利用在对不同算例求解过程中所积累的经验。深度学习的出现，弥补了传统方法的不足，深度学习以数据为驱动力，挖掘潜在的数据特征[1]，可以自动地学习出有效的“启发式方法”，而不需要获取先验知识来进行启发式规则的设计。现有研究工作主要关注于对模型的改进，缺乏从实例的生成来解决训练模型的泛化性。

本文以TSP 问题为例，在端到端的学习模型框架下引入对抗的思想，提出生成器加判别器的对抗训练框架[2]来增强学习模型对于问题的泛化性。本文的贡献如下：

（1）由随机数据作为数据集训练所得到的模型鲁棒性较差，本文借鉴对抗攻击与对抗防御思想，基于对抗生成模型的框架，设计神经网络模型，使用求解器生成标签，并使用监督学习的方式来得到对抗样本。通过对预训练模型的攻击来验证对抗样本的效果，最终能够产生高质量的对抗样本。将生成器与判别器结合形成生成对抗框架，通过对抗训练最终得到在随机样本和对抗样本上都表现良好的判别器模型，实验成功验证了该思路的可行性。

（2）传统对抗训练没有评判判别器训练好坏程度的指标，只通过生成器模型和判别器模型固定次数的交替迭代来进行对抗训练，本文基于判别器的更新方式设计一种自检测更新机制，设置超参数，通过判别器的连续更新状态来判断是否进入生成对抗样本的模式，通过该训练方式所得到的模型能够有效地降低对抗样本的代价，避免每一步迭代过程中对抗样本训练欠拟合的状况。

1 相关工作

Sequence-to-sequence[3]模型是一类针对变长输入问题的端到端的学习模型。该模型根据输入的序列来得到不同的输出序列，被广泛用在机器翻译、自动应答等场景。由于上述模型的输出字典大小固定，不适用于解决不同输入长度对应的不同输出长度的问题，Vinyals等人提出新的模型架构PointerNetwork[4]解决了该问题，该模型基于sequence-to-sequence 模型，使用LSTM[5]模型作为RNN[6]的基本单元，并在此基础上改变attention机制[7]使其更适应于解决组合优化问题。该网络的提出首次将深度学习引入到组合优化问题的求解，开辟了一条有别于传统算法的研究思路。

使用监督学习在训练效率上较非监督学习有一定的优势，但是，对于大规模组合优化问题来说，获取标签的代价是昂贵的，而且所得到的模型质量取决于标签的质量。另外，这种监督学习模型的本质是对获取标签算法的一种拟合，因此在求解质量上有天然的上限。针对该局限性，Bello等人[8]提出使用强化学习的方法来训练PointerNetwork，使用类似asynchronous advantage actor-critic（A3C）[9]的强化学习训练框架，用采样解的代价（旅行长度）来对策略梯度进行无偏蒙特卡罗估计。该论文将TSP问题求解规模从50扩大到了100个点，同时避免了获取高质量实例标签的计算困难。Khalil等人[10]针对图组合优化问题的特点提出使用structure2vec[11]来进行图的嵌入，使用deep Q-learning[12]来学习一个图嵌入网络的贪婪策略，并在三种图组合优化问题（MVC，MAXCUT，TSP）上进行验证，取得了较启发式算法有竞争力的解。Kool等人[13]提出使用基于transformer[14]作为网络架构。基于架构优势，使用自注意力机制实现了数据的并行输入，改善了串行输入带来的效率低下的问题，同时使用一种类似自评价机制[15]的方法来提供强化学习的基线。该方法使TSP 问题在100 点的规模上得到了更近似于最优解的解，同时通过更改网络解码过程中的掩码机制和上下文来适配不同的问题，将该网络结构应用在其他几个组合优化问题上，体现了该方法在解决一些没有有效启发式算法问题上的灵活性。

2 对抗训练模型

本章基于TSP问题来定义对抗训练模型，TSP问题是一个NP-hard 的组合优化问题[16]。问题可以描述为，在二维平面上有一系列分散的坐标点，要求从某一个点出发，找到一条经过各二维坐标点一次后回到出发点的最短路径。定义一个问题实例S包含平面上的n个坐标点{(x1,y1),(x2,y2),…,(xn,yn)}，定义实例的解为π=(π1,π2,…,πn)，该解为坐标点的一个全排列。定义实例对应的最优路径长度为。

对抗网络主要由两部分组成，分别为生成器网络和判别器网络，生成器和判别器的优化目标各不相同。生成器用来生成对抗样本，生成的实例是对于判别器求解质量较差的实例。定义网络对实例S输出解为L(θ|S)，其中θ为网络参数。在评估解的优劣时，一般使用近似解和精确解的相对误差，也就是gap 值作为评判标准，gap值定义如式（1）：

判别器将对抗样本和随机样本混合进行训练，两个网络交替训练，判别器和生成器相互博弈，最终得到泛化性增强的判别器网络，对抗训练模型示意图如图1所示。

图1 对抗训练模型Fig.1 Adversarial training model

2.1 判别器模型

本文使用的判别器模型基于文献[13]。模型可分为两部分，编码器和解码器模型。编码器使用自注意力机制进行特征提取。解码器通过编码器所提取的信息来构造上下文信息，通过注意力机制用于每一步的解码，最后通过指针机制产生每个点被选择的概率分布，通过不同的采样机制来获得实例的一个解。

编码器部分基于transformer模型，核心部分采用三层多头自注意力机制，同时在每一层都加入残差连接[17]以及批规范化[18]，最后一层为全连接层网络。由于各个点的输入不存在类似NLP输入的顺序问题，所以相比于传统的transformer 模型，判别器网络省略了位置编码。编码器将TSP问题中的每个点进行编码，最终得到每个点关于整个实例图的高维表示，同时将所有的点嵌入加和求平均得到关于整张图的高维嵌入，所得到的高维表示称为图嵌入，编码器网络如图2所示。

图2 编码器网络图Fig.2 Encoder model

解码器采用逐步输出的方式，每一步需要根据上下文信息和每个点的嵌入信息来进行解码。解码过程首先使用多头自注意力机制来对上下文信息进行编码，解码过程中使用的上下文信息为解码器网络选择的第一个点的点嵌入矩阵、图嵌入矩阵，以及当前对应的前一个点的嵌入矩阵的拼接。在第一步解码过程中，由于第一个点还未被选择，所以前一个被选择的点也不存在，使用可学习的参数矩阵作为输入的占位符。得到上下文嵌入矩阵后，进行一次自注意力计算来完成上下文和各点嵌入矩阵的信息交换，然后使用指针机制[4]以及掩码机制生成每个点被选择的概率，掩码机制使得前面每一步被选中的点下次被选中的概率为0，所有点被选择的概率和为1。直到所有的点被选到形成实例的一个解，完成解码过程。解码器根据采样方式不同可以分为两种，一种是贪婪解码，也就是在解码过程中，每一步只选择概率最大的点。另一种方式是概率解码，也就是依据每一步解码过程中所产生的概率分布来进行点的选择。

2.2 生成器模型

生成器使用的是多层感知机网络，神经网络的前两部分都包含一个全连接层、批规范化层、ReLU激活函数层，最后一部分为一个全连接层，生成2 维的坐标点信息。设置生成器的输入为100维的随机噪声，第一层全连接网络的节点数设置为256个，第二层全连接神经网络的节点设置为128 个，最后一层节点数设置为两个。随机生成的噪声信息在经过生成器后生成坐标集为{(x1,y1),…,(xi,yi),…,(xn,yn)} ，通过min-max 归一化生成的新的点坐标集为，新坐标点分别为：

将坐标分别在两个维度进行归一化以匹配判别器的原始输入。

2.3 训练方法

对抗神经网络包含两部分，一部分是判别器网络，一部分是生成器网络，需要分别进行训练。对于判别器，使用的是基于策略的强化学习的方法来训练。给定一个实例S，判别器网络在每一步解码中给出每个点被选择的概率，依据概率采样可以获得一个有效解π|s，定义损失函数为L(θ|S)=EPθ(π|s)[L(π)]，L(π)为TSP 问题旅行长度的期望值。在训练判别器时，训练样本为生成器所生成对抗样本和随机样本的混合数据。固定生成器的参数，使用带有基线的强化学习梯度估计器通过梯度下降的方法更新网络参数，梯度估计如式（4）[19]：

对于基准值的选择，使用一个评判网络，结构与主网络相同，这种训练方法类似于自评判机制。在训练判别器前需要生成一份评估数据集，同时在评判网络上通过贪婪解码的方式生成评估数据集的解。重新生成训练数据集，训练数据集为随机样本和生成器所产生的对抗样本，评判网络对训练数据使用贪婪解码的方式为主网络提供基准值。主网络根据上述强化学习梯度估计更新网络，评判网络此时不需要进行更新。更新主网络后，需要在主网络上采用贪婪解码的方式来得到评估数据集的解，根据评估数据集在主网络和评判网络的解通过配对T检验（α=5%）来判断主网络是否得到一定程度的改善，判定主网络得到改善后，则将当前主网络参数复制到评判网络。每次参数复制后都会重新生成评估数据集以防止过拟合。

传统的对抗学习一般在固定次数的判别器更新后切换到生成器网络进行训练，这种训练方法不能对判别器的训练现状进行一个大概的评估，导致生成器和判别器难以训练至收敛，训练过程损失函数曲线震荡严重。基于自评价基线的特殊性，当同一份验证数据在判别器主网络上的训练难以继续优化，判别器参数将无法更新到自评价网络，可判定判别器网络对于对抗样本有了一定的学习能力，基于是否达到此状态来判断是否应该切换至生成器网络来进行更新。

网络首先从判别器开始训练，根据以上介绍的强化学习方法进行训练。设置超参数为n，当判别器主网络连续n步没有更新参数到基准网络时，跳转到生成器网络的训练阶段，开始一个回合的生成器训练，训练结束后继续跳转到判别器训练。

在训练生成器时，需要固定判别器的参数。高维噪声信号输入生成器后输出未经处理的坐标信息，将生成器生成的数据标准化后，使用Gurobi求解器求取对抗样本实例的解作为训练生成器的标签，将得到的对抗样本混合到随机样本中送入判别器网络，判别器网络此时使用的解码方式为贪婪解码，得到的每个实例i的解为Li(π)，每个实例对应的求解标签为y^i，使用监督学习的方法来训练神经网络。定义损失函数L(θ|S)，使用梯度下降的方法来优化损失函数。经过判别器初始预热训练后，求解实例的gap值远小于1，可以将1作为目标值，因此损失函数可以定义为式（5）：

在训练生成器时，判别器的解码模式为贪婪解码。当对抗样本gap 值上升趋于平缓且判别器网络对解的质量提升也趋于平缓时，结束对抗训练。

3 实验

3.1 实验设置

3.1.1 数据集及评价指标

本文使用的数据用例包含随机生成的用例和随机噪声通过生成器所生成的对抗用例，随机生成用例是分布在正方形区域[0，1]2区间的均匀分布用例，而通过生成器所生成的对抗用例通过数据标准化来归一化到[0，1]2区间。

本文将实验分为两个对照组，一组是通过随机样本充分训练的预训练模型，一组是初始化后，通过对抗训练机制训练的对抗训练模型。本文将从对抗样本和随机样本分别在对抗模型和预训练模型的表现来验证训练效果。为了验证生成器可以有效生成对抗样本，需要通过对抗训练生成对于预训练模型gap 值较大的对抗样本。验证生成器有效后，再通过对抗训练机制来训练初始化的模型，使用预训练模型上所得到的对抗样本、随机样本以及对抗训练中产生对抗样本的gap 值来检验对抗训练模型。

3.1.2 实验环境

硬件环境为NVIDIA GeForce GTX1080 显卡，16 GB 运行内存，英特尔i7-7700 处理器。软件环境为Windows10系统，Tensorflow2.0，Pytorch0.4.1开发环境。

3.2 实验参数设置

由于求解器求解速度限制，本文对于20规模的TSP问题，每回合处理5 000个实例，每一批次包含500个实例。对于50 规模的TSP 问题，每回合处理3 000 个实例，每一批次包含300 个实例，判别器网络的学习速率设置为η1=10-4，生成器的学习速率设置为η1=10-3，同时生成器学习速率衰减值设置为0.96。

3.3 对抗样本验证

为了验证生成器网络能够生成有效对抗样本，分别在20 规模和50 规模的TSP 问题上进行验证，判别器使用的是基于文献[13]中的预训练模型。固定判别器参数，生成器网络使用监督学习的方式来获取gap值更大的对抗样本，训练每一回合的批次大小和每一批次包含实例数量与上面设置相同，生成器采用Adam优化器来进行优化。训练完毕后，对生成器进行验证，验证规模为500个对抗例，训练过程如图3。

图3 生成器训练过程图Fig.3 Training process of generator

可以观察到，通过监督学习的方式不断更新生成器网络，最终得到了对于原预训练判别器结果较差的解的实例，实验证明生成器网络能够生成有效的对抗样本，训练最终结果如表1所示。

表1 生成器验证结果Table 1 Result of generator training

3.4 对抗训练实验

对抗训练阶段，不使用预训练模型，初始化判别器和生成器的参数，首先进行判别器的训练，采用的是上述基于策略梯度的强化学习的方法。设置判别器和生成器的跳转机制：设置TSP问题规模为20时，当判别器连续30个epoch没有将主网络参数更新到基准网络时，将自动切换到生成器网络进行训练；当规模为50时，则设置为40个epoch。生成器网络的回合数独立计数，生成器的学习速率的衰减依据生成器的训练回合数，不与判别器使用相同的回合计数。每次生成器更新完成后将生成新的混合评估数据，同时在判别器评判网络上进行贪婪解码，为后续主网络更新到评判网络提供评判标准，训练过程如图4、图5所示。

图4 20维TSP对抗训练过程图Fig.4 Adversarial training process of TSP（N=20）

图5 50维TSP对抗训练过程图Fig.5 Adversarial training process of TSP（N=50）

对抗训练后，分别对随机样本、生成器所产生的对抗样本进行测试。可以观察到，随机样本和对抗样本最终能在对抗训练模型上取得较好的结果。同时通过预训练模型生成的对抗样本同样在对抗模型上有较好的结果，证明通过对抗训练，判别器在一定范围上泛化能力增强。对抗训练后的训练结果如表2所示，对抗训练模型与预训练模对对抗样本及随机样本的改善程度如表3所示。可以观察到在20规模和50规模上对抗模型对对抗样本有一定改善程度，尤其在20 规模上改善效果较为明显，同时对随机样本的结果有一定削弱，改善效果要好于削弱效果，模型在原来的基础上得到平衡。

表2 对抗训练结果Table 2 Result of adversarial training

表3 预训练模型对抗样本在对抗模型上的表现Table 3 Performce of adversarial model in adversarial samples of pre-trained model

4 结语

本文提出针对组合优化问题的对抗学习框架，通过加入生成器模型，样本生成的丰富度得到提升，进一步增强了网络的泛化性能。在原预训练模型上表现较差的对抗样本，通过对抗训练后，解的质量得到较大的提升。同时针对原判别器模型训练方式引入一种自适应切换判别器和生成器训练的方式，使对抗样本能够得到充分的拟合，同时对抗训练后的模型对于原分布的gap值影响较小，最终整体上提升了原训练网络的泛化性能。

在未来工作中，将问题扩大到更大规模具有重要的实际意义。由于生成对抗样本过程中求解标签对问题规模的限制，通过不使用标签的方法来得到对抗样本也会是接下来的重点研究方向。