【作者】 刘川；

【导师】 沈卫明；

【作者基本信息】 华中科技大学 ， 机械工程， 2023， 硕士

【摘要】 组合优化问题是学术界和工业界研究的热点问题,随着越来越多的数据被建模为图结构数据,图优化问题也引起了广泛关注。现阶段,图优化问题的求解方法主要是启发式算法,其能够在保证效率的前提下找到满意解。但该优势在处理大规模复杂结构的图问题中逐渐消失,因而研究者们尝试利用图神经网络在学习和处理图结构数据上的显著优势来解决图优化问题。本文针对三个典型节点分配问题,分别提出了相应的基于图神经网络的求解方法,并通过实验验证了所提方法的有效性和先进性。针对平衡图分割问题,本文提出了一个基于图神经网络的端到端的求解方法。首先,设计正则项编码约束条件,将该带有软约束的图优化问题转化为无约束的图优化问题,得到问题的损失函数。然后,建立一个两层的图神经网络来学习和优化节点分配矩阵,得到最终的优化结果。最后,将所提方法与先进的基准算法进行比较。实验结果表明所提方法能够生成准确且平衡的图分割方案,优于基准算法。逆图分割问题是图分割问题的逆问题,目前学术界还没有对该问题形成成体系的研究。本文首先分析逆图分割问题特点,并整理改进现有的能够用于求解该问题的启发式方法。在此基础上,提出一个基于图神经网络的两阶段求解方法。所提方法采用一个节点聚类网络对节点聚类,利用聚类结果构造结构化的初始解,再对初始解进行局部优化得到最终结果。最后,将所提方法与基准算法进行比较,验证了方法的有效性与先进性,并通过消融实验进一步探究了图的拓扑结构对逆图分割算法的影响。针对最大独立集问题,本文首先利用拉格朗日乘子法将该带有硬约束的图优化问题转化为一个无约束的图优化问题,得到问题的损失函数。接着,建立一个图神经网络对节点分配矩阵进行优化,并对优化后的矩阵进行离散化处理得到最终解。最后,将所提方法与先进的基准算法进行比较,验证了方法的有效性与先进性,并对设计的损失函数进行了可视化以进一步说明其有效性。文章最后对全文工作进行了总结,并对未来研究的发展方向进行了展望。更多还原

【Abstract】 Combinatorial optimization has shown its important role in science and industry.With more and more data being modeled as graph-structured data,graph optimization problems have attracted a large amount of attention.At present,the solutions of graph optimization problems are mainly obtained by heuristic algorithms,which can find satisfying solutions while maintaining efficiency.However,the advantages of heuristic algorithms gradually disappear in solving large-scale graphs with complex structures.Therefore,researchers tend to utilize the impressive power of graph neural networks in learning and processing graphstructured data to address graph optimization problems.In this paper,three optimization methods based on graph neural networks are proposed to address three typical node allocation problems.Experiment results illustrate the effectiveness and superiority of the proposed methods compared with the state-of-the-art baselines.To address the balanced graph partitioning problem,an end-to-end method based on graph neural networks is proposed.Firstly,a regularization term is designed to transform this soft constrained graph optimization problem into an unconstrained one,from which the loss function can be obtained.Then,a two-layer graph neural network is proposed to learn and optimize the node allocation matrix to get the final solution.Finally,the proposed method is compared with the state-of-the-art baselines.The experiment results show that the proposed method can generate accurate and balanced partitions,superior to the selected baselines.Inverse graph partitioning is the inverse problem of graph partitioning,however,there is no systematic research on this problem in the academia yet.In this paper,the characteristics of the inverse graph partitioning problem are analyzed,and the existing heuristic algorithms which can be used to address this problem are sorted out firstly.Then,a two-stage method based on graph neural networks is proposed.The proposed method uses a node clustering graph neural network to cluster nodes,constructs structured initial solutions based on the clustering results,and then optimizes the initial solutions using a local optimization algorithm to get the final solution.Finally,the proposed method is compared with the selected baselines to illustrate its effectiveness and superiority.In addition,ablation studies are designed to investigate the effect of the graph topology on the performance of the algorithms.As for the maximum independent set problem,the Lagrange multiplier method is utilized to transform this hard constrained graph optimization problem into an unconstrained one,where the loss function of this problem is obtained.After that,a two-layer graph neural network is proposed to lean and optimize the node allocation matrix,which is further discretized to get the final solution.Finally,the proposed method is compared with the stateof-the-art baselines to illustrate its effectiveness and superiority.Besides,the designed loss function is visualized to further show its effectiveness.At last,the whole work is summarized and the future research direction is prospected.更多还原