- 站点信息
- 问题反馈
- 邮箱：[email protected]
- 吐槽一下
关注微信
©2020-2025 ioDraw All rights reserved,
Privacy Policy
<>有约束优化问题
第一篇文章讲述了，怎么从二次多项式获得QUBO，获得QUBO后，量子退火法就可以直接给你最优解（没有特殊说明的话，所有的变量都是0或1）。其实，实际问题一般都是有约束的，比如上篇的例题加上约束条件后。
这种带约束的优化问题，我们要求出满足约束条件下的令H值最小的，（x1,x2）的组合。没有约束的情况，（x1,x2）的组合和H的取值如下表，最优解为（x1,x2）=（0,1）：
从上面的表中可以看到，因为需要满足约束条件，最优解变为（x1,x2）=（0,0）。这道例题变量比较少，可以很快找到满足约束条件的最优解。
其实，正常有约束的优化问题会变换成下面的形式，然后求解。
其中惩罚函数g()就是从约束条件获得。怎么把约束条件转化为惩罚函数呢？答案就是，把约束条件转化为对应的**【哈密顿算符(Hamiltonian) 】**
<>约束条件转换为【哈密顿算符H】
我们可以这么想，如果有一个二次多项式，让它取最小值的解，刚好是某个【哈密顿算符H】的最小值（H=0）的解。以上面的约束条件为例：
x 1 ⩾ x 2 x1 \geqslant x2 x1⩾x2
那么满足约束条件的（x1, x2）有[ (0, 0), (1, 0), (1, 1)
]三个组合。逆向思维，这三个组合会是哪个【哈密顿算符H】的最小值的解呢？有兴趣的读者可以自己想一想，这里我直接给出答案。
上面H=0的解，就是满足约束条件的，（x1, x2）=[ (0, 0), (1, 0), (1, 1) ]。对应的QUBO矩阵就是。
这时候带有惩罚函数项的新的H变为：
很多读者到这里，就会有疑问，每次都要把二次多项式写成QUBO矩阵的话，很麻烦。能不能直接输入二项式呢？答案是，可以的。
<>Pyqubo：自动把二次多项式转换为QUBO
# neal是模拟退火的库 import neal # pyqubo 可以使用Binary定义变量，Constarint定义约束 from pyqubo
import Binary, Constraint x1, x2 = Binary('x1'), Binary('x2') # M是约束强度 M = 5.0
#定义哈密顿算符H H = 3 * x1**2 - 2 * x2**2 + M * Constraint((x2 - x1*x2), label=
'x1>=x2') model = H.compile() # 无视offset就行了，QUBO用来做模拟退火的输入 qubo, offset = model.
to_qubo() sampler = neal.SimulatedAnnealingSampler() raw_solution = sampler.
sample_qubo(qubo) raw_solution.first.sample >>> {'x1': 0, 'x2': 0}
我们可以看到，最后的结果是（x1, x2）=（0, 0）。确实是最优解。但是M值（就是前面公式里的 λ \lambda λ）如果太小，可能得不到最优解。
<>常见条件约束对应的H
前任栽树，后人乘凉，常见的约束条件对应的H如下表所示：
本文介绍了，如何添加约束条件到目标函数中，下篇讲一个经典的旅行商最短路径问题如何建模，求解。