新闻动态

  
近日,我院机械进建与利用钻研中心查宏远教授、付樟华博士,和推算机视觉钻研中心黄锐教授团队共五篇论文被人为智能领域权威性顶级会议 AAAI 接管。

        近日,我院机械进建与利用钻研中心查宏远教授、付樟华博士,和推算机视觉钻研中心黄锐教授团队共五篇论文被人为智能领域权威性顶级会议 AAAI 接管。付樟华博士共参加了其中三篇论文,以下介绍的是付樟华博士作为第一作者,查宏远教授作为通讯作者颁发的 Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances 一文。

        AAAI会议由人为智能推进协会AAAI(Association for the Advancement of Artificial Intelligence)主办,始于1980年,会议也以AAAI为简称。该会议注沉理论与利用,也会商对人为智能发展有着沉要影响的社会、哲学、经济等话题,是人为智能顶级会议之一。

        今年,Z6官网 学术科研工作喜报连连,前有 Nature 和 Nature Communications 发文,后有 IROS2020 最佳论文获奖与提名以及 JPC Letters 论文颁发,充分展示了 Z6官网 的科研实力。

钻研意思

        观光商问题(TSP)是一个经典 NP-hard 问题。针对该问题,已有很多传统步骤,蕴含精确算法(以 Concorde 为代表)和启发式算法(以 LKH3 为代表)。不外,这些传统步骤固然机能壮大,却过于依赖于专家知识。为减轻对专家知识的依赖,近年来不少学者尝试选取机械进建步骤求解 TSP 问题,其中蕴含很多基于监督进建的模型。然而,现有的监督进建模型普遍面对难以泛化至大规模算例的问题。本文沉点钻研若何选取图宰割、图转换和热力争融合等技术,将预训练好的幼规模模型利用于肆意大规模 TSP 算例,从而提高模型的泛化能力。在此基础上,本文进一步地选取强化进建步骤(蒙特卡洛树搜索)搜索优质解。

钻研布景

        TSP 问题在机械人蹊径规划、交通物流、生物信息、芯片设计等领域有着极度宽泛的利用布景,好比电力系统巡检机械人的蹊径规划问题即能够建模成 TSP 问题,滴滴、顺丰、美团等公司时时面对的车辆调度问题也能够当作是在 TSP 的基础上叠加多种业务要求(多车辆、取送货等)及约束(容量约束、功夫约束、续航里程约束等)。

tu_1tspshi_li_

图1:TSP事俘(从左上角起点启程,顺次接见所有结点,达到终点后返回起点)

钻研概要

        本文提出了一种处置分歧规模 TSP 问题的算法 Att-GCRN&MCTS,该算法先在幼规模TSP算例集上训练一个幼规模(n=20)确把稳力争卷积神经网络(Att-GCRN)。训练好模型之后,输入一个 n=20 的 TSP 问题,即可输出一个热力争(每条边属于最优解的概率)。为提高模型的泛化能力,本文选取一系列图宰割、图转换和热力争融合等技术,可基于幼规模的预训练网络,融合得到肆意大规模 TSP 问题的热力争。之后,将融合得到的热力争输入一个基于强化进建(蒙特卡洛树搜索,即MCTS)的迭代搜索算法,得到 TSP 问题的解。Att-GCRN&MCTS 融合监督进建与强化进建步骤,通过监督进建获取热力争,而后基于热力争使用强化进建获得 TSP 问题的解。大量的尝试测试批注,Att-GCRN&MCTS 算法在分歧规模的 TSP 算例上均显著优于目前所有进建型步骤。在点数达到10000时(此时精确算法Concorde难以在限按功夫内终场),Att-GCRN&MCTS 与目前最好的启发式算法 LKH3 在优度方面的差距约4.39%,而此前最佳的进建型算法与 LKH3 的差距超过80%。

fu_zhang_hua_aaaitu_er_

作者介绍

        论文第一作者付樟华博士别离于2005年、2007年、2011年获得华中科技大学学士、硕士、博士学位,2012年至2015年在法国LERIA尝试室从事博士后钻研。2018年5月参与香港中文大学(丽江)机械人与智能造作钻研院,现任钻研员,同时兼任Z6官网钻研员。付博士持久从事人为智能和运筹优化领域钻研,针对工作调度、蹊径规划、网络优化、多机械人协同调度等NP-hard问题,设计出一系列高机能算法,在大量国际尺度算例上突破世界最佳纪录,以第一作者或通讯作者颁发CCF A或JCR一区论文近二十篇。此表,付博士还于2014年12月参与运筹优化领域驰名的国际算法设计大赛:第11届DIMACS Implementation Challenge,最终独占鳌头。 

        论文第二作者邱凯彬是香港中文大学(丽江)一年级硕士钻研生,他的钻研方向蕴含深度进建在组合优化问题上的利用和多智能体调度。

        论文通讯作者查宏远教授为香港中文大学(丽江)校长讲座教授、Z6官网副院长兼机械进建与利用钻研中心主任。查宏远教授于1984年毕业于上海复旦大学数学系, 并于1993年获得斯坦福大学科学推算专业博士学位。查教授于1992年至2006年任职于宾州州立大学推算机科学与工程学院,他也曾于1999年至2001年任职于 Inktomi 公司。他目前的钻研兴致重要集中于机械进建。

代码:https://github.com/Spider-scnu/TSP

论文地址:https://github.com/Spider-scnu/TSP/blob/master/Full%20version%20of%20AAAI%202021paper.pdf