有約束優(yōu)化問題
第一篇文章講述了，怎么從二次多項(xiàng)式獲得QUBO，獲得QUBO后，量子退火法就可以直接給你最優(yōu)解（沒有特殊說明的話，所有的變量都是0或1）。其實(shí)，實(shí)際問題一般都是有約束的，比如上篇的例題加上約束條件后。
這種帶約束的優(yōu)化問題，我們要求出滿足約束條件下的令H值最小的，（x1,x2）的組合。沒有約束的情況，（x1,x2）的組合和H的取值如下表，最優(yōu)解為（x1,x2）=（0,1）：
從上面的表中可以看到，因?yàn)樾枰獫M足約束條件，最優(yōu)解變?yōu)椋▁1,x2）=（0,0）。這道例題變量比較少，可以很快找到滿足約束條件的最優(yōu)解。
其實(shí)，正常有約束的優(yōu)化問題會(huì)變換成下面的形式，然后求解。
其中懲罰函數(shù)g()就是從約束條件獲得。怎么把約束條件轉(zhuǎn)化為懲罰函數(shù)呢？答案就是，把約束條件轉(zhuǎn)化為對(duì)應(yīng)的**【哈密頓算符(Hamiltonian) 】**
約束條件轉(zhuǎn)換為【哈密頓算符H】
我們可以這么想，如果有一個(gè)二次多項(xiàng)式，讓它取最小值的解，剛好是某個(gè)【哈密頓算符H】的最小值（H=0）的解。以上面的約束條件為例：
x
1
?
x
2
x1 \geqslant x2
x1?x2
那么滿足約束條件的（x1, x2）有[ (0, 0), (1, 0), (1, 1) ]三個(gè)組合。逆向思維，這三個(gè)組合會(huì)是哪個(gè)【哈密頓算符H】的最小值的解呢？有興趣的讀者可以自己想一想，這里我直接給出答案。
上面H=0的解，就是滿足約束條件的，（x1, x2）=[ (0, 0), (1, 0), (1, 1) ]。對(duì)應(yīng)的QUBO矩陣就是。
這時(shí)候帶有懲罰函數(shù)項(xiàng)的新的H變?yōu)椋?br>
很多讀者到這里，就會(huì)有疑問，每次都要把二次多項(xiàng)式寫成QUBO矩陣的話，很麻煩。能不能直接輸入二項(xiàng)式呢？答案是，可以的。
Pyqubo：自動(dòng)把二次多項(xiàng)式轉(zhuǎn)換為QUBO
# neal是模擬退火的庫
import neal
# pyqubo 可以使用Binary定義變量，Constarint定義約束
from pyqubo import Binary, Constraint
x1, x2 = Binary('x1'), Binary('x2')
# M是約束強(qiáng)度
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}
我們可以看到，最后的結(jié)果是（x1, x2）=（0, 0）。確實(shí)是最優(yōu)解。但是M值（就是前面公式里的 λ \lambda λ）如果太小，可能得不到最優(yōu)解。文章來源：http://www.zghlxwxcb.cn/news/detail-413254.html
常見條件約束對(duì)應(yīng)的H
前任栽樹，后人乘涼，常見的約束條件對(duì)應(yīng)的H如下表所示：
本文介紹了，如何添加約束條件到目標(biāo)函數(shù)中，下篇講一個(gè)經(jīng)典的旅行商最短路徑問題如何建模，求解。文章來源地址http://www.zghlxwxcb.cn/news/detail-413254.html
到了這里，關(guān)于量子退火算法入門（2）：有約束優(yōu)化問題的QUBO怎么求？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
