跳转到内容
本文内容

TSP问题QUBO&Ising建模选讲 ​

旅行商问题 ​

旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题:一个商品推销员要去若干个城市推销商品,从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。

QUBO建模 ​

变量定义 ​

给定一张有权重的连接图G(V,E),V是节点的集合,E是边的集合;

使用距离矩阵来表示G,当两点间不存在边时,其权重值为0;

令N=|V|,N表示节点的数量;

令xu,j=1代表点u在第j个点被访问,否则xu,j=0。

其中v∈0...N−1, j∈0...N−1。

建立约束条件 ​

首先,对于每一个u,只对应一个顺序j,则有:

∑j=0N−1xu,j=1,u∈0...N−1

其次,对于每一个顺序j,只对应一个点u,则有:

∑u=0N−1xu,j=1,j∈0...N−1

将以上两个约束写成QUBO形式,有:

A∑u=0N−1(∑j=0N−1xu,j−1)2+A∑j=0N−1(∑u=0N−1xu,j−1)2

对于(u,v)∉E,我们希望u、v不连续出现在位置j、j+1上,则有:

A∑(u,v)∉E(∑j=0N−2xu,jxv,j+1+xu,N−1xv,0)

QUBO模型构建 ​

如此,由以上的QUBO,可以构建一个遍历所有的点的路径的模型(又称哈密尔顿环):

HA=A∑u=0N−1(∑j=0N−1xu,j−1)2+A∑j=0N−1(∑u=0N−1xu,j−1)2+A∑(u,v)∉E(∑j=0N−2xu,jxv,j+1+xu,N−1xv,0)

然而对于旅行商问题,在此基础上想要获得上述路径中最短的一个。令wu,v为边(u,v)的权重,则有:

HB=B∑(u,v)∈Ewu,v(∑j=0N−2xu,jxv,j+1+xu,N−1xv,0)

将两个QUBO表达式相加,即可得到最终的优化模型:

H=HA+HB

优化目标是求H的最小值。

Ising建模 ​

本节基于TSP问题QUBO模型转换Ising建模。

变量定义 ​

给定一张有权重的连接图G(V,E),其中V是节点的集合,E是边的集合。

  • 使用自旋变量su,j∈{−1,1}表示节点u是否在第j个位置被访问:

    su,j={1点 u 在第 j 个位置被访问−1否则
  • N=|V|,表示节点的数量;

  • 当两点 (u,v) 间不存在边时,权重为0。

建立约束条件 ​

(a) 节点唯一性约束 ​

每个节点u必须唯一对应一个位置j,即:

∑j=0N−1su,j=2−N(∀u∈0,…,N−1)

转换为Ising模型的能量项:

H1=A∑u=0N−1(∑j=0N−11+su,j2−1)2

(b) 位置唯一性约束 ​

每个位置j必须唯一对应一个节点u,即:

∑u=0N−1su,j=2−N(∀j∈0,…,N−1)

转换为Ising模型的能量项:

H2=A∑j=0N−1(∑u=0N−11+su,j2−1)2

(c) 非相邻节点约束 ​

若 (u,v)∉E,则u和v不能连续出现在位置 j 和 j+1(含循环边界):

H3=A∑(u,v)∉E(∑j=0N−21+su,j2⋅1+sv,j+12+1+su,N−12⋅1+sv,02)

Ising模型构建 ​

总哈密顿量为约束项的加权和:

H=H1+H2+H3

展开后分为线性项、二次项 和 常数项:

(a) 线性项系数 hu,j ​

1)来自节点与位置唯一性约束:

hu,j=A2−A(N−1)4

2)来自非相邻节点约束:

hu,j=A4∑(u,v)∉E(δj,0δv,next(u)+δj,N−1δv,0)

其中δa,b为Kronecker delta函数,next(u) 表示与u相邻的位置。

(b) 二次项系数 J(u,j),(v,k) ​

1)来自节点唯一性约束:

J(u,j),(u,k)=A4(j≠k)

2)来自非相邻节点约束:

J(u,j),(v,j+1modN)=A4当 (u,v)∉E

(c) 常数项 ​

所有常数项合并为C,不影响优化结果。

最终Ising模型形式为:

H=∑u,jhu,jsu,j⏟线性项+∑u,j≠kJ(u,j),(u,k)su,jsu,k⏟节点内约束+∑(u,v)∉E∑j=0N−1J(u,j),(v,j+1modN)su,jsv,j+1modN⏟非相邻节点约束+C

参数说明 ​

(1)惩罚系数A:需足够大以确保约束优先满足(通常远大于目标函数的权重);

(2)变量范围:su,j∈{−1,1},总变量数为N2;

(3)循环边界:位置索引j+1modN表示路径的闭环。