求解组合优化问题的具有递归特征的无监督图神经网络

文章目录

  • ABSTRACT
  • 1 Introduction
  • 2 Related Work
  • 3 QRF-GNN方法
  • 4 数值实验
    • 4.1 MAX-CUT
    • 4.2 COLORING
  • 5 conclusion

ABSTRACT

  • 介绍了一种名为QRF-GNN的新型算法,有效解决具有二次无约束二进制优化(QUBO)表述的组合问题。依赖无监督学习,从最小化的QUBO放松导出的损失函数。
  • 该架构的关键组成部分是中间GNN预测的递归使用、并行卷积层以及将人工节点特征作为输入的组合。

1 Introduction

二次无约束二进制优化(QUBO)问题是最小化一个二次伪布尔多项式F(x)的问题:

2 Related Work

在Tönshoff等人的研究中,作者提出了RUN-CSP作为最大约束满足问题的一种循环无监督神经网络。该架构包括一组线性函数,为图中的所有变量节点和所有约束的边提供消息传递。在消息传递步骤之后,当前状态以及内部长期状态通过LSTM单元进行更新。基于输出,网络产生变量在搜索域中取特定值的概率。

Amizadeh等人提出了一种无监督GNN来解决SAT和CircuitSAT问题[Amizadeh et al., 2018]。他们使用问题的有向无环图表示,并训练模型以最小化人工损失函数,其最小值对应于具有更高满意度的解决方案。

Karalias和Loukas以稍微不同的方式应用了GNN[Karalias & Loukas, 2020]。它获得了对应于候选解的节点分布。该模型通过最小化概率惩罚函数进行训练,并使用顺序解码来获得离散解,降低其不可行的概率。

在Wang等人的研究中,作者引入了GNN-1N,将负面消息传递技术适应到无监督GNN中,用于解决图着色问题[Wang et al., 2023]。使用特定问题的QUBO公式的连续放松作为损失函数的建议是由Schuetz等人在他们的物理启发式GNN(PI-GNN)中提出的[Schuetz et al., 2022a]。PI-GNN的基础架构包括一个可训练的嵌入层,用于生成节点的输入特征,以及几个图卷积层(GCN或GraphSAGE)。在Schuetz等人的研究中,这个模型被应用于解决图着色问题。

3 QRF-GNN方法

节点之间交换消息使用的是消息传递协议,分为两个部分:消息累积和消息聚合。

消息累积:

节点 i 的特征向量由一个函数 ψ

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/414018.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【软件工程】软件生命周期(生存周期)

考点3 软件生命周期(生存周期) 一、定义 软件产品或软件系统从设计、投入使用到被淘汰的全过程。 二、3周期 题目 一、判断题 二、选择题

mac电脑里面的 磁盘分区,容器,宗卷,宗卷组的理解和使用

在mac电脑里面我们一般都是使用宗卷,他和我们常见的pc机器硬盘的分区是有区别的。 对于物理硬盘来说 不管是分区还是宗卷,他们都是逻辑上面的概念。 分区 mac电脑里面的分区 和 pc电脑中的分区差不多, 他们都是针对的物理硬盘,…

Linux系列之基础篇

文章目录 开篇明义基础篇实际操作篇高级篇Linux之JavaEELinux在哪些地方使用Linux应用领域 Linux入门基本介绍Linux和Unix关系 VM和Linux的安装基本说明安装VM17.5安装Centos7.6网络连接解释 虚拟机克隆虚拟机快照虚拟机迁移和删除安装vmtools设置共享文件夹 Linux目录结构 开篇…

144. 腾讯云Redis数据库

文章目录 一、Redis 的主要功能特性二、Redis 的典型应用场景三、Redis 的演进过程四、Redis 的架构设计五、Redis 的数据类型及操作命令六、腾讯云数据库 Redis七、总结 Redis 是一种由 C 语言开发的 NoSQL 数据库,以其高性能的键值对存储和多种应用场景而闻名。本…

计算机网络概述(协议层次与服务模型)

目录 1.协议层次 2.服务模型 1.协议层次 层次化方式实现复杂网络功能: 将网络复杂的功能分成明确的层次,每一层实现了其中一个或一组功能,功能中有其上层可以使用的功能:服务本层协议实体相互交互执行本层的协议动作&#xff0…

EXCEL文件如何批量加密,有什么方法

EXCEL文件的加密,通常在EXCEL软件上进行设置,它有打开密码与写保护密码,如果有多个文件的话,想通过一键设置的方法进行密码设置,那么它通常需要用到第三方软件进行批处理,因为EXCEL软件只能对当前打开的文件…

排序算法刷题笔记【牛客网】

排序算法刷题笔记【牛客网】 排序算法刷题记录,来自牛客网,主要是有些题目会去搜一下相关知识,这里就用来做笔记,类似错题本了。 会持续更新…… 8.28,一编,3题 其实就是把45前面的排好了,然后…

watchdog: BUG: soft lockup

故障现象: 故障原因: 不知道。 解决办法: 由12个改成2个;然后重新开机虚拟机, 临时解决了。

Kaggle克隆github项目+文件操作+Kaggle常见操作问题解决方案——一文搞定,以openpose姿态估计项目为例

文章目录 前言一、Kaggle克隆仓库1、克隆项目2、查看目录 二、安装依赖三、文件的上传、复制、转移操作1.上传.pth文件到input目录2、将权重文件从input目录转移到工作目录 三、修改工作目录里的文件内容1、修改demo_camera.py内容 四、运行! 前言 想跑一些深度学习…

使用Blender云渲染的好处是什么?

​Blender是一款功能强大的开源3D创作软件,用于包括建模、动画、仿真、渲染、合成和视频编辑在内的多种应用。然而,Blender的渲染过程有时可能非常耗费资源,特别是处理复杂的3D场景时。作为CG行业不可或缺的一部分,云渲染通过使用…

Excel下拉框多选

记录一下学会一个新的知识! 两种方式 第一种方式:先在表格里写好需要的值,再在数据关联里面直接引入。 1.新建excel表格,输入下拉框需要的值。 2.点击——数据>有效性 3.选择——序列 4.数据来源——框住刚才写好的数据——…

实现一个命令行解释器

1、初始化命令行解释器 在计算机系统中,操作系统内核是一个很大得到软件模块,用户不能直接去使用。因此计算机提供一个外壳shell,用户能够通过这个外壳执行各种应用程序,从而完成操作系统各种功能。 shell:命令解释器…

51单片机——LED点阵屏

1、点阵屏简介 LED点阵屏由若干个独立的LED组成,LED以矩阵的形式排列,以灯珠亮灭来显示文字、图片、视频等。LED点阵屏广泛应用于各种公共场合,如汽车报站器、广告屏以及公告牌等 LED点阵屏分类 按颜色:单色、双色、全彩 …

【202408最新】Anaconda+VSCode+CUDA+Pytorch安装配置保姆级教程

最近新换了电脑,又开始从头配置代码环境,到处看教程真的一个头两个大,干脆自己整理了一下,方便以后一站式重装。也提供给大家参考。 1.Anaconda下载安装 Anaconda和Python是替代品(也不是),下…

浅析WebRTC技术在智慧园区视频管理场景中的应用

随着科技的飞速发展,智慧园区作为城市智慧化的重要组成部分,正逐步成为现代化管理的重要方向。智慧园区的建设不仅涉及硬件设施的智能化升级,还离不开高效的视频管理和实时通信技术。在这一背景下,WebRTC(Web Real-Tim…

兴业证券基于Apache DolphinScheduler的应用实践

文 / 兴业证券股份有限公司 刘洋 石良生 柳君 李致琪 本文来源于网络,如有侵权,请联系删除 任务调度平台,扮演着自动执行预设任务的重要角色,是业务开展过程中不可或缺的一环。随着业务规模的不断扩展,兴业证券每日…

【JavaWeb】Http请求与响应

文章目录 Http 请求与响应一、Http 请求格式1、请求行2、请求头3、请求体(post请求才有) 二、HttpServletRequest1、获取 请求行 信息2、获取 请求头 信息3、获取 请求参数 信息 三、Http 响应格式1、响应行2、响应头3、响应体(正文&#xff…

杨辉三角

题目 给定一个非负整数 numRows&#xff0c;生成杨辉三角的前 numRows 行。 在杨辉三角中&#xff0c;每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1] ]参考答案 class Solution { public:vector<vector<int>…

Centos 下载和 VM 虚拟机安装

1. Centos 下载 阿里云下载地址 centos-7.9.2009-isos-x86_64安装包下载_开源镜像站-阿里云 2. VM 中创建 Centos 虚拟机 2.1 先打开 VM 虚拟机&#xff0c;点击首页的创建新的虚拟机 2.2 选择自定义&#xff0c;然后点击下一步。 2.3 这里默认就好&#xff0c;继续选择下一…

JavaWeb学习——Maven高级使用学习

一、分模块设计与开发 1、分模块设计原因 Maven 的分模块设计主要有以下几个原因&#xff1a; 1. 模块化管理&#xff1a;在大型项目中&#xff0c;代码量通常会非常大&#xff0c;如果将所有的代码都放在一个模块中&#xff0c;会使得项目结构复杂&#xff0c;不利于代码的管…