TSP问题QUBO&Ising建模选讲

旅行商问题

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

QUBO建模

变量定义

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

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

令$N=|V|$，$N$表示节点的数量；

令$x_{u,j}=1$代表点$u$在第$j$个点被访问，否则$x_{u,j}=0$。

其中$v\in 0...N-1$, $j\in 0...N-1$。

建立约束条件

首先，对于每一个$u$，只对应一个顺序$j$，则有：

$$\sum _{j=0}^{N-1}{x}_{u,j}=1,u\in 0...N-1$$

其次，对于每一个顺序$j$，只对应一个点$u$，则有：

$$\sum _{u=0}^{N-1}{x}_{u,j}=1,j\in 0...N-1$$

将以上两个约束写成QUBO形式，有：

$$A\sum _{u=0}^{N-1}(\sum _{j=0}^{N-1}{x}_{u,j}-1{)}^2+A\sum _{j=0}^{N-1}(\sum _{u=0}^{N-1}{x}_{u,j}-1{)}^2$$

对于$(u,v)\notin E$，我们希望$u$、$v$不连续出现在位置$j$、$j+1$上，则有：

$$A\sum _{(u,v)\notin E}(\sum _{j=0}^{N-2}{x}_{u,j}{x}_{v,j+1}+x_{u,N-1}{x}_{v,0})$$

QUBO模型构建

如此，由以上的QUBO，可以构建一个遍历所有的点的路径的模型（又称哈密尔顿环）：

$$H_A=A\sum _{u=0}^{N-1}(\sum _{j=0}^{N-1}{x}_{u,j}-1{)}^2+A\sum _{j=0}^{N-1}(\sum _{u=0}^{N-1}{x}_{u,j}-1{)}^2+A\sum _{(u,v)\notin E}(\sum _{j=0}^{N-2}{x}_{u,j}{x}_{v,j+1}+x_{u,N-1}{x}_{v,0})$$

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

$$H_B=B\sum _{(u,v)\in E}{w}_{u,v}(\sum _{j=0}^{N-2}{x}_{u,j}{x}_{v,j+1}+x_{u,N-1}{x}_{v,0})$$

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

$$H=H_A+H_B$$

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

Ising建模

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

变量定义

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

• 使用自旋变量$s_{u,j}\in \{-1,1\}$表示节点$u$是否在第$j$个位置被访问：

  $$s_{u,j}=\{\begin{array}{ll}1& \text{点 }u\text{ 在第 }j\text{ 个位置被访问}\\ -1& \text{否则}\end{array}$$

• $N=|V|$，表示节点的数量；

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

建立约束条件

(a) 节点唯一性约束

每个节点$u$必须唯一对应一个位置$j$，即：

$$\sum _{j=0}^{N-1}{s}_{u,j}=2-N(\mathrm{\forall }u\in 0,\dots ,N-1)$$

转换为Ising模型的能量项：

$$H_1=A\sum _{u=0}^{N-1}{(\sum _{j=0}^{N-1}\frac{1+s_{u,j}}{2}-1)}^2$$

(b) 位置唯一性约束

每个位置$j$必须唯一对应一个节点$u$，即：

$$\sum _{u=0}^{N-1}{s}_{u,j}=2-N(\mathrm{\forall }j\in 0,\dots ,N-1)$$

转换为Ising模型的能量项：

$$H_2=A\sum _{j=0}^{N-1}{(\sum _{u=0}^{N-1}\frac{1+s_{u,j}}{2}-1)}^2$$

(c) 非相邻节点约束

若 $(u,v)\notin E$，则$u$和$v$不能连续出现在位置 $j$ 和 $j+1$（含循环边界）：

$$H_3=A\sum _{(u,v)\notin E}(\sum _{j=0}^{N-2}\frac{1+s_{u,j}}{2}\cdot \frac{1+s_{v,j+1}}{2}+\frac{1+s_{u,N-1}}{2}\cdot \frac{1+s_{v,0}}{2})$$

Ising模型构建

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

$$H=H_1+H_2+H_3$$

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

(a) 线性项系数 $h_{u,j}$

1）来自节点与位置唯一性约束：

$$h_{u,j}=\frac{A}{2}-\frac{A(N-1)}{4}$$

2）来自非相邻节点约束：

$$h_{u,j}=\frac{A}{4}\sum _{(u,v)\notin E}({\delta }_{j,0}{\delta }_{v,\text{next}(u)}+{\delta }_{j,N-1}{\delta }_{v,0})$$

其中${\delta }_{a,b}$为Kronecker delta函数，$\text{next}(u)$ 表示与$u$相邻的位置。

(b) 二次项系数 $J_{(u,j),(v,k)}$

1）来自节点唯一性约束：

$$J_{(u,j),(u,k)}=\frac{A}{4}(j\ne k)$$

2）来自非相邻节点约束：

$$J_{(u,j),(v,j+1\mathrm{mod}N)}=\frac{A}{4}\text{当 }(u,v)\notin E$$

(c) 常数项

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

最终Ising模型形式为：

$$H=\underset{\text{线性项}}{\underbrace{\sum _{u,j}{h}_{u,j}{s}_{u,j}}}+\underset{\text{节点内约束}}{\underbrace{\sum _{u,j\ne k}{J}_{(u,j),(u,k)}{s}_{u,j}{s}_{u,k}}}+\underset{\text{非相邻节点约束}}{\underbrace{\sum _{(u,v)\notin E}\sum _{j=0}^{N-1}{J}_{(u,j),(v,j+1\mathrm{mod}N)}{s}_{u,j}{s}_{v,j+1\mathrm{mod}N}}}+C$$

参数说明

（1）惩罚系数$A$：需足够大以确保约束优先满足（通常远大于目标函数的权重）；

（2）变量范围：$s_{u,j}\in \{-1,1\}$，总变量数为$N^2$；

（3）循环边界：位置索引$j+1\mathrm{mod}N$表示路径的闭环。