solve

求解 QUBO（二次无约束二元优化）问题

自 R2023a 起

全页折叠

安装要求：此功能需要 MATLAB Support Package for Quantum Computing。

语法

result = solve(qprob)

result = solve(qprob,Algorithm=ts)

说明

result = solve(qprob) 使用默认 tabuSearch 算法搜索 qprob（一个 QUBO 问题）的解 result。

示例

result = solve(qprob,Algorithm=ts) 使用 ts 禁忌搜索算法进行搜索。当您要设置禁忌搜索对象 ts 的属性时，请使用此语法。

示例

全部折叠

创建和求解 QUBO 问题

为二次矩阵 Q、线性向量 c 和常数项 d 创建一个 QUBO 问题，其中

$\begin{matrix} Q = [\begin{matrix} 0 & - 1 & 2 \\ - 1 & 0 & 4 \\ 2 & 4 & 0 \end{matrix}] \\ c = [\begin{matrix} - 5 & 6 & - 4 \end{matrix}] \\ d = 12. \end{matrix}$

Q = [0 -1 2;...
    -1 0 4;...
    2 4 0];
c = [-5 6 -4];
d = 12;
qprob = qubo(Q,c,d)

qprob = 

  qubo with properties:

    QuadraticTerm: [3×3 double]
       LinearTerm: [-5 6 -4]
     ConstantTerm: 12
     NumVariables: 3

使用禁忌搜索算法求解问题。

result = solve(qprob)

result = 

  quboResult with properties:

                BestX: [3×1 double]
    BestFunctionValue: 7
      AlgorithmResult: [1×1 tabuSearchResult]

修改禁忌搜索

创建一个 QUBO 问题。

Q = [0 -1 2;...
    -1 0 4;...
    2 4 0];
c = [-5 6 -4];
d = 12;
qprob = qubo(Q,c,d)

qprob = 

  qubo with properties:

    QuadraticTerm: [3×3 double]
       LinearTerm: [-5 6 -4]
     ConstantTerm: 12
     NumVariables: 3

创建一个禁忌搜索对象，显示迭代次数，并将停止时间限制在 0.01 秒。

ts = tabuSearch(Display="iter",MaxStallTime=0.01);

使用禁忌搜索对象求解 QUBO 问题。

result = solve(qprob,Algorithm=ts)

Tabu call    Best fval   Stall time   Tabu iterations
        0           18            0           0
        1            7    0.0002593         309
        2            7      0.00109         301
        3            7     0.001731         301
        4            7     0.002031         301
        5            7      0.00232         301
        6            7     0.002605         301
        7            7     0.002885         301
        8            7     0.003163         301
        9            7     0.003446         301
       10            7     0.003772         301
       11            7     0.004054         301
       12            7      0.00433         301
       13            7     0.004611         301
       14            7     0.004888         301
       15            7     0.005163         301
       16            7     0.005438         301
       17            7     0.005719         301
       18            7     0.005992         301
       19            7     0.006266         301
       20            7     0.006544         301
       21            7      0.00682         301
       22            7     0.007104         301
       23            7     0.007385         301
       24            7     0.007669         301
       25            7     0.007949         301
       26            7     0.008411         301
       27            7     0.008699         301
       28            7     0.008978         301
       29            7     0.009257         301

Tabu call    Best fval   Stall time   Tabu iterations
       30            7     0.009549         301
       31            7     0.009894         301
       32            7      0.01013         301

TabuSearch stopped because MaxStallTime is exceeded.

result = 

  quboResult with properties:

                BestX: [3×1 double]
    BestFunctionValue: 7
      AlgorithmResult: [1×1 tabuSearchResult]

禁忌搜索是一种随机算法，因此您的结果可能会有所不同。

输入参数

全部折叠

`qprob` — QUBO 问题
`qubo` 对象

QUBO 问题，指定为 qubo 对象。使用 qubo 函数创建 qprob。

`ts` — 禁忌搜索算法
`tabuSearch` 对象

禁忌搜索算法，指定为 tabuSearch 对象。使用 tabuSearch 函数设置算法属性。

示例: 要使算法运行不超出 60 秒，请设置 ts = tabuSearch(MaxTime=60)，然后调用 solve(qprob,Algorithm=ts)。

输出参量

全部折叠

`result` — QUBO 问题的解
`quboResult` 对象

QUBO 问题的解，以 quboResult 对象形式返回。result 包含以下属性：

BestX - 对应于最小目标函数值的解点。
BestFunctionValue - 对应于 BestX 的目标函数值。通常，BestFunctionValue = evaluateObjective(qprob,BestX)。
AlgorithmResult - 结果的详细信息，以 tabuSearchResult 对象形式返回。

算法

禁忌搜索算法基于 Palubeckis [1]。从一个随机二元向量开始，软件通过将一些现有值从 1 切换到 0 或从 0 切换到 1，反复尝试寻找具有更低目标函数值的二元向量。软件尝试通过使用禁忌列表来避免循环或重复计算同一点。有关详细信息，请参阅Tabu Search Algorithm。

参考

[1] Palubeckis, G. Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem. Informatica (2006), 17(2), pp. 279–296. Available at https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3c323a1d41cd0e2ca1ddb27192e475ea73959e52.