Graph Partitioning as Quadratic Unconstrained Binary Optimization (QUBO) on Spiking Neuromorphic Hardware
Graph Partitioning as Quadratic Unconstrained Binary Optimization (QUBO) on Spiking Neuromorphic Hardware
复制标题
图分区作为尖峰神经形态硬件上的二次无约束二元优化 (QUBO)
DOI：
10.1145/3354265.3354269
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Mniszewski
中科院分区：
文献类型：
--
作者：
S. Mniszewski
在这项工作中，图分区（GP）的探索使用二次无约束二进制优化（QUBO）的IBM TrueNorth尖峰神经形态架构。GP将一个图分割成大小相似的部分，同时最小化部分之间的切割边的数量。GP的经典方法依赖于几何学和近似算法。GP QUBO公式的灵感来自于以前使用D-Wave量子退火机的工作。这种方法不限于图算法，但适用于解决一系列NP难优化问题。一个经典的伪模拟退火元启发式算法被用来解决QUBO。描述了使用尖峰框架在IBM TrueNorth上的实现。收敛的高能量的解决方案的结果被证明是“足够好”或最佳的分割成2部分的图。
In this work, graph partitioning (GP) is explored using quadratic unconstrained binary optimization (QUBO) on the IBM TrueNorth spiking neuromorphic architecture. GP splits a graph into similar-sized parts while minimizing the number of cut edges between parts. Classical approaches to GP rely on heuristics and approximation algorithms. The GP QUBO formulation was inspired by previous work using the D-Wave quantum annealer. This approach is not limited to graph algorithms, but is applicable to solving a spectrum of NP-hard optimization problems. A classical pseudo simulated annealing metaheuristic is used to solve the QUBO. Implementation on the IBM TrueNorth using a spiking framework is described. Results as converged high-energy solutions are shown to be "good enough" or optimal for partitioning a graph into 2 parts.