当前位置
主页 > 新闻中心 > 公司新闻 >
“旅行商问题”太棘手?用图神经网络寻找最优解
2021-12-17 01:56
本文摘要:全文共3438字,预计学习时长7分钟或更长为什么优化如此重要?从几百万年前人类生命起源开始,为了提升生活质量,提高在地球上的生存技术,人类使用睿智的脑壳举行了一次次的科技创新和发现。从火(药)到车轮,从电力到量子力学,我们对于世界及周遭事物庞大性的明白水平已经到了难以仅凭直觉去判断的水平。如今,飞机、汽车、汽船、卫星以及用于其他目的复合结构的设计师们,极大地依赖于运用算法来提升其能力,而这种提升方式往往微妙到人们自身永远无法实现。

hth华体会

全文共3438字,预计学习时长7分钟或更长为什么优化如此重要?从几百万年前人类生命起源开始,为了提升生活质量,提高在地球上的生存技术,人类使用睿智的脑壳举行了一次次的科技创新和发现。从火(药)到车轮,从电力到量子力学,我们对于世界及周遭事物庞大性的明白水平已经到了难以仅凭直觉去判断的水平。如今,飞机、汽车、汽船、卫星以及用于其他目的复合结构的设计师们,极大地依赖于运用算法来提升其能力,而这种提升方式往往微妙到人们自身永远无法实现。除了设计,优化在日常生活中也饰演着至关重要的角色,好比网络路由(互联网和移动终端)、物流、广告投放、社交网络甚至是医药信息。

未来,随着科技水平的不停革新与庞大化,解决大规模难题的能力将会迎来更高需求,同时,我们也需要在算法优化上有所突破。组合优化的问题广义上来说,组合优化问题即是解决从有限工具荟萃中寻找“最佳”工具的问题。

这个语境中的“最佳”是由给定的评价函数来权衡的,该函数将工具映射到某个分数或成本,其目的是找到成本最低的工具。大多数在实际中看起来有意思的组合优化问题(后文都简略为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秒内生成比商业求解法式用时一小时所求得的更佳解决方案。可是这个方法有一个很大的缺陷,就是他们会使用一个“辅助”方程来资助图神经网络寻找更好解法。这个辅助方程是人为设计用于解决特定问题的,而这恰恰是我们想要制止的。

这种基于图例的展现方式很是容易明白,因为许多组合优化问题可以自然而然地以这种方式出现出来,就如下面这个TSP图例所展示的一样:图中的每个节点代表每个都会,节点边缘包罗了城际间的距离,如果不思量边缘属性,类似的图形也能够构建起来(如果我们出于某种原因不思量距离因素在内的话)。近年来,基于图形的神经网络模型(无关乎是否具备架构知识)以令人难以置信的速度盛行开来。尤其令人瞩目的是自然语言处置惩罚领域,它所使用的Transformer架构模型已经成为业内众多任务处置惩罚的最先进技术。

有许多优秀的文章详细地解释了Transformer 架构,所以本文不再深入剖析,而是做一个简述。Transformer架构是由谷歌研究人员在一篇题为“Attention Is All You Need”的论文中所先容的。

在这篇著名的论文中,Transformer架构被用于处置惩罚NLP中所面临的序列难题。差别之处在于,我们可以向递归神经网络,如是非影象网络(LSTM),直观输入一系列的输入向量,而Transformer架构中只能以一系列工具的形式输入,且必须接纳特殊的方式来让它瞥见“序列”的排列顺序。这个Transformer是由一个多头自注意力子层和一个完全毗连的子层所组成的。

它与图谱的关系在注意力层变得显着起来,而这个注意力层实际上是输入“节点”间的一种信息通报机制。每一个节点都市视察其他节点,同时定向那些对于它们自己看起来更“有意义”的节点。这与在图谱注意力机制(Graph Attention Network)中运行的历程很是相似。

实际上,如果使用一个掩码来阻止单个节点向不相邻的节点通报信息,我们将会获得一个等价的历程。学习如何在没有人类知识的情况下解决问题 在论文《注意!学习解决路由问题》中,作者们实验解决了几个涉及图解路由署理的组合优化难题,包罗我们现在熟悉的旅行商问题。

将输入数据视为一个图,并将其投入一个经由调整的Transformer构架并在构架中嵌入了图的节点,然后依次选择添加到路由的节点直到完成构建一个完整的路由为止。将输入数据视为图形是一个比向其提供节点序列更为“正确”的方法,因为只要它们的坐标稳定,就能够消除对所输入都会顺序的依赖性。这意味着,差别于上述的节点序列法,无论我们如何改变输入都会的排列,给定图神经网络的输出值都将保持稳定。在论文所提及的构架中,图谱是由Transformer 编码器嵌入的,它在为所有的节点生成嵌入层的同时也为全图生成单个嵌入向量。

为了生成解决方案,每次给予一个特殊的上下文向量时都市给出一个单独的解码器网络,这个网络由图嵌入、最后一个和第一个都会以及未会见都会的嵌入组成,并会输出一个未会见都会的概率漫衍,然后采样生成下一个将要会见的都会。这个解码器会按顺序生成要会见的都会直到整个行程竣事,然后凭据旅程的长度给予反馈。文中使用了一种名为REINFORCE的强化学习算法来训练模型,这是一种基于计谋梯度的算法。其版本所使用的伪代码如下图所示:文中使用一个滚轮网络来确切评估实例的难度,并定期使用计谋网络的参数来更新这个滚轮网络。

这种方法在解决几个难题上取得了不错的成效,性能上逾越了前文所提到的其他方法。只管如此,作者们仍在拥有至多100个节点的小型例子上训练和评估模型。虽然这些效果很有希望,但这些例子与现实生活中其他情况相比,犹如小巫见大巫。

扩展到大型问题最近,一篇题为《通过深度强化学习在大型图上学习启发式算法》的论文中向解决现实世界那般规模巨细的问题迈出了重要一步。在文中,作者训练了一个图卷积网络来解决诸如最小极点笼罩(MVC)和最大笼罩问题(MCP)这样的大型实例问题。针对这些问题,他们接纳一种盛行的贪心算法来训练神经网络举行嵌入图并预测每一阶段需要选择的下一个节点,在此之后使用DQN算法对其举行进一步的训练。他们在含有数百万个节点的图上测评了其方法,并取得了比当前尺度算法更优异快速的效果。

虽然他们确实通过使用动手搭建的启发式来资助训练模型,但在未来,这种方式可能会消除这种约束,并从白板状态学会解决庞大难题。总之,在无边的搜索领域中,寻找架构是强化学习的一个重要且实用的研究偏向。许多品评强化学习的人声称,到现在为止,这项技术仅被用于解决游戏和简朴的操作问题,想要将其应用到解决现实问题中还很有很长的路要走。留言 点赞 关注我们一起分享AI学习与生长的干货接待关注全平台AI垂类自媒体 “读芯术”。


本文关键词:华体会体育,“,旅行商问题,”,太,棘手,用图,神经网络

本文来源:华体会体育-www.zcdkj.com

联系方式

电话:067-534628942

传真:0480-307581252

邮箱:admin@zcdkj.com

地址:江苏省扬州市祁门县化复大楼1467号