留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于图网络的集群运动预测研究

王瑞 崔佳梅 张越 郑文

王瑞, 崔佳梅, 张越, 郑文. 基于图网络的集群运动预测研究[J]. 电子科技大学学报, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
引用本文: 王瑞, 崔佳梅, 张越, 郑文. 基于图网络的集群运动预测研究[J]. 电子科技大学学报, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
WANG Rui, CUI Jiamei, ZHANG Yue, ZHENG Wen. Research on Collective Movement Prediction Based on Graph Network[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
Citation: WANG Rui, CUI Jiamei, ZHANG Yue, ZHENG Wen. Research on Collective Movement Prediction Based on Graph Network[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107

基于图网络的集群运动预测研究

doi: 10.12178/1001-0548.2021107
基金项目: 国家自然科学基金(11702289);国家重点研发计划“科技助力经济2020专项”;山西省关键核心技术和共性技术研发攻关专项(2020XXX013)
详细信息
    作者简介:

    王瑞(1997-),女,主要从事复杂性科学与人工智能方面的研究

    通讯作者: 郑文,E-mail:zhengwen@tyut.edu.cn
  • 中图分类号: TP391

Research on Collective Movement Prediction Based on Graph Network

图(8)
计量
  • 文章访问数:  4436
  • HTML全文浏览量:  1422
  • PDF下载量:  70
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-04-16
  • 修回日期:  2021-07-01
  • 网络出版日期:  2021-09-28
  • 刊出日期:  2021-09-28

基于图网络的集群运动预测研究

doi: 10.12178/1001-0548.2021107
    基金项目:  国家自然科学基金(11702289);国家重点研发计划“科技助力经济2020专项”;山西省关键核心技术和共性技术研发攻关专项(2020XXX013)
    作者简介:

    王瑞(1997-),女,主要从事复杂性科学与人工智能方面的研究

    通讯作者: 郑文,E-mail:zhengwen@tyut.edu.cn
  • 中图分类号: TP391

摘要: 集群动力学是软物质领域的研究热点和前沿视角,集群运动的同步机制存在着丰富的潜在规律和应用价值。该文构建了一种基于加权集群动力学的图网络模型,该模型从粒子的位置、运动方向特征以及邻居的影响中学习集群运动的演化机制,可以实现对集群运动过程的长期预测。实验结果表明,图网络模型可以对集群运动过程中的序参量进行预测,涵盖不同的噪声和视野半径,预测效果较好。模型构建后,无需进行复杂的动力学模拟和计算,就可以得到不同条件参数下集群运动系统序参量的值,从而快速量化集群运动的同步程度,节省时间成本,对集群的智能控制具有重要意义。

English Abstract

王瑞, 崔佳梅, 张越, 郑文. 基于图网络的集群运动预测研究[J]. 电子科技大学学报, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
引用本文: 王瑞, 崔佳梅, 张越, 郑文. 基于图网络的集群运动预测研究[J]. 电子科技大学学报, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
WANG Rui, CUI Jiamei, ZHANG Yue, ZHENG Wen. Research on Collective Movement Prediction Based on Graph Network[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
Citation: WANG Rui, CUI Jiamei, ZHANG Yue, ZHENG Wen. Research on Collective Movement Prediction Based on Graph Network[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(5): 768-773. doi: 10.12178/1001-0548.2021107
  • 集群行为在生活中普遍存在,如鸟群、鱼群、兽群和蜂群等发生的自然集群现象[1-2],小到各种微粒子、大到星际天体都时时刻刻处在各自的集群中运动[3-4],人类的生活居住、社会活动和经济生产领域也在空间上表现出一定的集群变化[5]。集群系统由大量活性物质组成,这些活性物质可以从周围环境吸收能量,并以某种方式转化为机械能,获得自我推进的能力,因此平衡热力学定律不再适用于此类问题[6]。1995年,文献[7]从统计力学的角度提出一种能简单有效地模拟集群运动的模型(VM)。在该模型中,个体通过考虑邻居的影响和环境中的扰动因素进行更新,使其整体呈现出复杂的行为。这一模型引发了广泛的研究兴趣,许多学者提出了相关的改进模型或其他模型,使其更加贴近现实且具有更好的性能。

    VM模型中的个体具有全局视野、速率始终保持不变、不考虑实际大小且邻居地位平等的特性。考虑到现实世界中的大部分生物的视野角度是有限的,文献[8-9]在二维情况下、文献[10]在三维情况下提出有限视野角下的集群运动模型。考虑到实际生活中集群中的个体会依据周围环境调整自己的行进速度,文献[11-12]提出了个体速率优化的模型,个体根据其邻居的行为同时调整其方向和速度。考虑到实际情况中的个体是具有半径的,运动过程中可能会发生碰撞,文献[13]提出了避免个体碰撞的集群运动模型,通过引入排斥力去自适应地调节个体的运动速率。集群系统中个体之间相互作用形成非均质化的网络结构,其中度大的节点往往会对集群演化产生相对重要的影响,文献[14]提出以度为权的模型,引入权重对邻居数目不同的个体进行区分,与标准的VM模型相比,加权机制有效地提高了系统的收敛效率。尽管传统的数学建模方法具有解释性,但迄今为止对复杂系统的应用仍然依赖于各种先验假设。

    数据驱动建模作为一种从观测数据中发现状态变量或其时间演化之间关系的方法,已经成为系统分析的强大工具,活性物质的集群行为也开始借助这种工具进行研究。文献[15]用深度神经网络建立了单体的等级交互模型,从而实现集群运动的智能控制。文献[16]用强化学习方法来确定鱼群在水流中的最佳适应性行动策略,以达到响应流动介导相互作用的目的。文献[17]用深度强化学习的方法来捕捉鱼群和涡流场之间的双向作用,为集群在复杂的非定常流场和旋涡流场提供导航算法。文献[18]提出了一种基于未来状态最大化(future state maximization, FSM)的内在激励集体运动形式,并在模拟轨迹上训练了多层神经网络来模拟FSM算法。然而,集群系统中个体的相互作用形成一个动态网络,传统的机器学习方法在解决上述问题时并没有充分利用网络的拓扑结构。2018年DeepMind联合谷歌大脑、MIT等机构提出图网络算法[19],这是一类基于深度学习的处理图域信息的方法,将端到端学习与归纳推理相结合,根据一些函数对图的节点、边和全局属性进行更新,在一些复杂系统和物理模型的预测和分析中已成功应用。文献[20]利用隐藏在粒子局部邻域中的结构,用图网络实现玻璃系统动力学的迁移率预测,文献[21]将距离加权图网络应用于典型的粒子重建任务,以提高性能和减少任务的执行时间,如聚类重构和粒子识别。文献[22]引入传播网络来处理可观察场景,信号可以在成对交互之外进行传播,不仅在前向仿真中优于当前可学习的物理引擎,而且在各种控制任务上也取得了优异的性能。

    本文将以度为权的Vicsek模型作为研究集群运动的对象,首先结合图论的基本知识和集群运动的工作机制将模拟数据处理为图结构数据,接着构建基于加权集群动力学的图网络模型,通过编码器自动进行特征提取,解码器将输出特征解析为原始信号,图网络模块实现点、边、全局属性的更新。该模型能够对自驱动集群运动演化过程中的序参量进行预测,涵盖不同的环境噪声以及个体权重,具有强大的预测能力和泛化能力。

    • 图网络是在拓扑空间内按图结构进行关系推理的函数集合。图网络框架的基本计算单元是一个“图到图”的GN(graph network)模块,即以图作为输入,在图结构上进行计算,返回结果也是一个图。图的结构如图1所示,实体为图中的节点,关系为图中的边,全局属性表示系统层面的属性。

      图  1  图的结构

      图表示为一个三元组$G = (u,V,E)$。其中$u$是全局属性,在集群运动中$u$代表系统中粒子的合速度。$V = {\left\{ {{v_i}} \right\}_{i = 1:{N^v}}}$是节点属性集合,集合规模为${N^v}$${v_i}$代表第$i$个节点的属性,在集群运动中$V$表示每个个体的位置、速度和方向等特征。$E =\{ ( {e_k},{r_k}, $$ {s_k})\}_{k = 1:{N^e}}$是边的集合,集合规模为${N^e}$,其中${e_k}$表示第$ k $条边的属性,${r_k}$是边的接收节点,${s_k}$是边的发送节点。集群运动中,$E$表示个体之间存在的影响。

      一个GN块包含3个更新函数$\varPhi$及3个聚合函数$\rho $,相应公式如下:

      $$ e_k' = {\varPhi ^e}({e_k},{v_{{r_k}}},{v_{{s_k}}},u) $$ (1)
      $$ v_i' = {\varPhi ^v}({\bar e'}_i,{v_i},u) $$ (2)
      $$ {u'} = {\varPhi ^u}({\bar e'},{\bar v'},u) $$ (3)
      $$ \bar e_i' = {\rho ^{e \to v}}(E_i') $$ (4)
      $$ {\bar e'} = {\rho ^{e \to u}}({E'}) $$ (5)
      $$ {\bar v'} = {\rho ^{v \to u}}({V'}) $$ (6)

      更新函数${\varPhi ^e}$对图中所有的边进行更新,使用自身属性、相应接收和发送节点的属性和全局属性来计算更新每条边。${\varPhi ^v}$对图中所有节点进行更新,使用自身的属性、连接到它的所有边和全局属性计算更新每个节点。${\varPhi ^u}$在一次计算中仅更新一次,作为全局的更新。聚合函数$\rho $每次输入一个集合,对集合中的信息进行规约。

      GN块的输入是图的3个组成部分:$E$$V$$u$。算法共分3步完成:

      1) 使用更新函数${\varPhi ^e}$更新每一条边,计算${e'}_k$

      2) 使用聚合函数${\rho ^{e \to v}}$循环聚合每个节点所相连的边$E_i' = {\left\{ {\left( {e_k',{r_k},{s_k}} \right)} \right\}_{{r_k} = i,k = 1:{N^e}}}$,生成${\bar e'}_i$;并使用${\varPhi ^v}$更新每个节点的属性,计算出${v_i}'$

      3) 使用聚合函数${\rho ^{e \to u}}$${\rho ^{v \to u}}$对更新后的节点集合${V'}$和边的集合${E'}$进行聚合,生成相应的信息${\bar e'}$${\bar v'}$,然后使用${\varPhi ^u}$对全局进行更新。函数最后返回的就是更新后的${E'}$${V'}$${{{u}}'}$

      计算步骤如图2所示。

      图  2  完整的GN块

      构建图网络框架最关键的是将GN块组合起来得到复杂的结构。由于GN块的输出和输入都是图,因此内部结构不同的GN块也可以方便地组合。不同的GN块组合起来能够复用内部函数,就像展开的RNN一样,并且在合并输入图和隐藏状态时,可采用像LSTM或者GRU一样的门控机制,而不是简单的合并。图网络组合GN块的形式如图3所示。

      图  3  GN块的组合

      两个GN块的合并方式为${G'} = {\rm{G}}{{\rm{N}}_2}\left( {{\rm{G}}{{\rm{N}}_1}(G)} \right)$,即一个图$G$经过${\rm{G}}{{\rm{N}}_1}$运算的输出作为${\rm{G}}{{\rm{N}}_2}$的输入。组合结构能实现复杂的运算,且参数可以共享。

    • 标准的Vicsek模型定义了自驱动集群中个体运动方向和位置的更新规则[7],在集群运动形成的动态网络中,每个节点的影响范围是一致的,但度大的节点能影响更多的个体,从而对集群演化产生较大的影响,因此应赋予更大的权重。

      通过引入与邻居个数相关的权重,并给出方向改变的表达式,得到以度为权的集群动力学模型,计算式为[14]

      $$ {\theta _i}\left( {t + 1} \right) = {\tan ^{ - 1}}\left\lceil {\frac{{\displaystyle\sum\limits_{j \in {\varGamma _i}(t)} {{\gamma _j}(t)\sin {\theta _j}} }}{{\displaystyle\sum\limits_{j \in {\varGamma _i}(t)} {{\gamma _j}(t)\cos {\theta _j}} }}} \right\rceil + \Delta \theta $$ (7)

      式中,${\gamma _j}(t)$表示个体$ i $的第$ j $个邻居在$ t $时刻的权重,计算公式为:

      $$ {\gamma _j}(t) = \frac{{{n_j}(t)}}{{\displaystyle\sum\limits_{k \in {\varGamma _i}(t)} {{n_k}(t)} }} $$ (8)

      式中,${n_j}(t)$代表$ t $时刻个体$i$的第$j$个邻居的邻居个数;${\varGamma _i}(t)$$t$时刻个体$i$的邻居集合。

      集群中所有个体的同步程度可用序参量${v_a}$来度量:

      $$ {v_a} = \frac{1}{{{{N}{v}}}}\left| {\sum\limits_{i = 1}^N {{v_i}} } \right| $$ (9)

      集群系统的收敛时间是指系统中的${v_a}$首次大于或等于某规定的阈值时,系统运行的时间步。

      本文将以度为权的集群动力学模型作为研究对象,选取同步程度和收敛时间作为收敛效率的评价指标,利用python设计迭代程序,模拟N=300个粒子在$ L\times L $的二维平面上的自驱动集群运动。其中设置粒子的速率v=0.03,密度$\rho $=12(L=5)。为了训练不同度下的模型,设置视野半径R分别为0.7、0.8、1.0、1.5、2.0、2.5、3.0来生成数据。为了训练不同噪声下的模型,设置噪声$\eta $分别为0.1、1.5、2.5、3.5、5来生成数据。在每种情况下,生成100组独立的数据作为网络的训练集,并对数据进行增强,同时生成100组独立的数据作为测试集,以便对模型进行评估。在每组数据中,采用了不同的粒子初始位置和初始运动角度来模拟自驱动群集运动,得到每次迭代后的粒子位置和运动角度,并计算出迭代后系统的${v_a}$,迭代次数是由系统的收敛时间决定的。

    • 本文构建基于加权集群动力学的图网络模型,如图4所示。首先将原始的模拟数据转换为图结构的数据,对于每个数据集项,将N个粒子的位置和运动角度作为图的节点属性。集群中视野半径内的粒子会相互影响,故将距离小于视野半径的粒子通过边连接,并且距离作为边的属性。每次迭代后的${v_a}$为全局特征。

      图  4  不同噪声下序参量随时间变化的预测

      在图网络模块前加入了编码器,将输入压缩为潜在空间表示,进行输入信息的重要特征提取,该方法提高了模型的训练速度和准确率。图网络模块中使用3个多层感知机作为更新函数,独立地输入图的节点、边缘和全局特征,接着执行消息传递,递归地更新图的边、节点和全局。首先根据已有的图的信息实现对每条边的更新;其次对每个节点所相连的边进行聚合,更新节点;最后对所有的边和节点进行聚合,实现对全局的更新。最终解码器将潜在空间表征重构为输出,将生成的嵌入解码为预测的${v_a}$,通过随机梯度下降回归到目标${v_a}$

    • 选取视野半径R=1来预测不同噪声下序参量${v_a}$随时间的变化。从图5可以看出,在密度固定的情况下,图网络模型在不同噪声下对序参量的预测效果很好。噪声较小($\eta $=0.1)时,序参量${v_a}$在集群演化初期的预测精度较低,随着整个集群趋于稳定,图网络模型对${v_a}$的预测越来越准确,这是由于不同的模拟情况在演化初期差异较大,而在稳定阶段具有相同的规律,即${v_a}$趋近于1。${v_a}$从0变化到1,代表集群运动从无序到有序,所有粒子从初始的随机运动到最后朝着一个方向运动。噪声较高($\eta $=3.5)时,${v_a}$在集群演化初期的预测精度同样较低,而稳定阶段的预测精度虽然有所提升,但相较于低噪声的情况会有所降低,这是因为处于噪声较高环境中的集群最终并不会达到同步状态,当集群演化到稳定阶段时,不同的模拟情况之间有一定的差异,规律性较弱。

      图  5  不同噪声下序参量随时间变化的预测

      从整体来看,本文的模型可以在不同噪声条件下对各种时间尺度的序参量做出较为准确的预测,以评估集群在演化过程中的一致程度。

      进一步,使用图网络模型预测稳定状态时的序参量随噪声的变化,以研究噪声对集群演化的影响。通过控制密度变量,使用涵盖不同噪声的数据对图网络模型进行训练,来预测集群的序参量${v_a}$。从图6可以看出,无论是低噪声还是高噪声,图网络模型都有非常好的预测效果。结果表明,噪声对集群演化有显著的影响。当环境中没有噪声或噪声极小时,集群中的所有粒子最终会朝着一个方向运动,整个集群呈现出同步状态,随着环境中扰动的增加,集群运动的同步程度呈现逐渐减小的趋势。

      图  6  序参量随噪声变化的预测

    • 当视野半径改变时,由式(8)可知,个体的度和权重也会随之改变。为了研究度对自驱动粒子系统演化的影响,在密度、噪声固定的情况下(L=5, $\eta $=0.1),设置不同的视野半径,来观察系统的演化情况。从图7的主图中可以看出,视野半径越大,系统的收敛时间越短,并且当半径小于1时,收敛时间随着半径的增加急速下降,当半径大于1时,收敛时间下降比较平缓。取其中3个比较有代表性的半径值,观察${v_a}$在其环境中的变化情况,从图7的子图中可以看出,视野半径越大,系统收敛越快。

      图  7  视野半径与收敛时间的关系

      为了证明本文构建的图网络模型具有强大的预测能力,在不同的视野半径下验证模型对序参量预测的准确性。控制系统的其他变量,将系统保持在低噪声($\eta $=0.1)、高密度(L=5)的状态。从图8中可以看出图网络模型对不同视野半径下的序参量都能作出很好的预测。视野半径不同,粒子的度不同,权重会随之发生改变。当视野半径较小时,周围粒子对目标粒子的影响较小,目标粒子和周围粒子趋于同步的时间较长,系统收敛较慢。当视野半径较大时,邻居粒子对目标粒子的影响也会增大,粒子运动方向会在短时间内与邻居粒子趋于一致,系统收敛加快。由此可见,视野半径越小,系统趋于一致的速度越慢,其混乱程度越高,使得图网络模型的预测精度略有降低。

      图  8  不同视野半径下序参量随时间变化的预测

    • 本文将以度为权的集群动力学作为研究对象,提出一种基于加权集群动力学的图网络模型,该模型可以很好地实现对加权集群运动演化过程的长期预测。首先在特定噪声下预测不同时间尺度的序参量,以及在不同噪声情况下预测集群稳定后的序参量,表明模型在不同的噪音水平下表现较好。为了证明本文构建的图网络模型具有强大的预测能力,本文进一步研究视野半径改变对预测的影响,结果表明模型在不同的个体权重下能够实现较为准确的预测。

      本文构建的模型具有强大的泛化能力,对大量数据进行训练和学习后,无需通过复杂且耗时的动力学模拟过程,便可以快速预测集群演化过程中的一致性变化以及集群稳定后的同步程度,节约时间成本。

参考文献 (22)

目录

    /

    返回文章
    返回