Attention,attention机制( 二 )

大多数在实际中看起来有意思的组合优化问题(后文都简略为COPs)很棘手，因为即使问题的规模大小只增加一点点，集合中的对象数量也会以极快的速度增加，这使穷举搜索显得不切实际。为了让问题更加直观明了，我们把关注点放在一个特定的问题上，即著名的旅行商问题(TSP) 。在这个问题中，假设有N座城市，销售人员必须访问所有的城市。
无论如何，在城际间旅行会产生一定的成本，而我们必须找到一条路线，使整个出行成本降到最低。例如，下图显示了行遍美国各州首府的最佳路线图：这个旅行商问题广泛存在于许多重要领域的应用，例如规划、交付服务、制造业、DNA测序以及其他许多方面。寻找更好的路径与解决财务等问题息息相关，这也促使科学界和企业投入大量物力财力来寻找更好的方法。
以K个城市为TSP例子构建一个旅游路线，在路径构建过程的每个阶段会删除一个城市，直到没有剩余的城市为止。在第一个阶段，有K个城市可供选择，在第二个阶段，有K-1个选项，接着是K-2个选项，以此类推。我们能够构建的潜在路径总数量是每个阶段所拥有选项数量的乘积，这个问题的复杂性为O(K!) 。然而，这种方法比较适用于数量较小的计算。
比方说，假设有5个城市，则潜在旅游路线的总数量为5!=120 。但是对于有7个城市的情况来说，这个计算结果会立增到5040，10个城市已经达到则是3628800，100的结果更是惊人地高达9.332622e 157，而这数量远远超过了宇宙中原子的数量。在现实生活中TSP的运用实例涉及到的是成千上万的城市数量运算，为了能在合理的时间(可能是几个小时)内解决问题，通常需要运用那些高度复杂的搜索算法和启发式算法，而这些算法是通过几十年下来的大量文献所开发形成的。
不幸的是，在实际应用中出现的许多COPs具有独特的细微差别和条件约束，它们阻止我们用最先进的解决方案来解决诸如TSP之类的已知问题，并且要求我们开发针对该问题的方法和启发式。这个过程可谓长路漫漫障碍重重，可能需要相关领域专家来检测特定问题组合，搜索空间中的某些结构。这些年来，由于深度学习在许多领域都取得了巨大的成功，让机器自主学习如何解决问题似乎有望在未来实现。
将算法的设计过程自动化，使其能够自发解决难以应对的COPs——这样不仅能节约大量财力和时间，也许还能生成比人工设计更加可行的解决方案（就像我们目前在AlphaGo等成果中所能看到的一样，它已经打败了人类过去通过数千年所取得的经验成就）。运用图例学习早在2016年，一篇名为《基于图表学习组合优化算法》的论文就对这个问题进行了早期尝试。
在这篇文章中，作者训练了一种叫structure2vec的图神经网络，针对几个有难度的COPs制定贪婪的构造解决方案，并获得了非常好的近似比值(生成成本与最优成本之比) 。它的基本思路是这样子的：用图谱来表示待解决的问题，然后让图神经网络依据图谱建立解决方案。在解决方案构建过程的每次迭代中，神经网络会观察当前的图表，并选择一个节点添加到解决方案中，然后根据该选择更新图表，接着重复这个过程，直到得到一个完整的解决方案。
论文作者们使用DQN算法来训练神经网络，并证明了习得模型在运用到比所受训练更复杂的问题实例时的泛化能力。这种模型甚至可以很好地泛化到1200个节点的实例中（同时在大约100节点的实例进行训练），同时还能在12秒内生成比商业求解程序用时一小时所求得的更佳解决方案。但是这个方法有一个很大的缺陷，就是他们会使用一个“辅助”方程来帮助图神经网络寻找更好解法。