使用 Mystic 优化编译硬约束

Question

我正在编写约束整数优化，但在制定约束时遇到了问题。以下是我的优化总结：（调度是我自己的函数，returns 一个单一的 int 值）

Objective：最小值 (1500 * x1) + (625 * x2) +(100 * x3)

约束条件：

时间表(x1,x2,x3) >=480
x2 > x1
x2 > x3

界限： (5<= x1 <=50), (5<= x2 <=100), (1<= x3 <=20)

由于约束 1 使用函数，因此不能以符号方式编写，因此将硬约束分组以放入 diffev2 的最佳方法是什么？

下面是对此的粗略尝试。我遇到的另一个小问题是边界被破坏（值为负），所以如果我的边界有任何危险信号，请务必说明。对 Mystic 也很陌生，所以不要担心用简单的术语解释事情。

import mystic as ms
import mystic.symbolic as msym
import numpy as np

def objective(x): 
    rounded = np.around(x)
    integer= rounded.astype(int)
    x1,x2,x3 = integer
    return (1500 * x1) + (625 * x2) +(100 * x3)


bounds = [(5,50),(5,100),(1,20)]


def constraint1(x):
    rounded = np.around(x)
    integer= rounded.astype(int)
    x1,x2,x3 = integer
    return 240-schedule(x1,x2,x3)

eqns = '''
x2 > x1     
x2 > x3

'''
cons = msym.generate_constraint(msym.generate_solvers(msym.simplify(eqns)))

constraint = ms.constraints.and_(cons, constraint1) #I know this is wrong but I want to join them

from mystic.solvers import diffev2
from mystic.monitors import VerboseMonitor
mon = VerboseMonitor(10)

result = diffev2(objective,x0=bounds, bounds=bounds, constraints=constraint, npop=50, gtol=200, \
                  disp=False, full_output=True, itermon=mon)

Answer 1

我会像这样稍微重写它...

Objective: 最小 (1500 * x0) + (625 * x1) + (100 * x2)

约束条件：时间表（x0，x1，x2）> = 480 x1 > x0 x1 > x2 x0, x1, x2 是整数

界限： (5 <= x0 <=50), (5 <= x1 <=100), (1 <= x2 <=20)

在这里，我们将在函数中定义 schedule，以及 bounds 和 objective。

>>> import mystic as my
>>> import mystic.symbolic as ms
>>> import numpy as np
>>>
>>> def objective(x):
...     x0,x1,x2 = x
...     return (1500 * x0) + (625 * x1) + (100 * x2)
...
>>> bounds = [(5,50),(5,100),(1,20)]
>>>
>>> def schedule(x0,x1,x2):
...     return x0 * x1 - x2 * x2
...

然后我们开始构建约束。约束函数总是 x' = constraints(x)（即它们采用参数向量，return 参数向量）。因此，我们这里有两个特殊情况：(1) 符号方程，我们将为其构建 x' = cons(x)，以及对 schedule 输出的约束——这需要一些迂回逻辑来构造。

>>> eqns = '''
... x1 > x0
... x2 < x1
... '''
>>>
>>> ints = np.round
>>> and_ = my.constraints.and_
>>> cons = ms.generate_constraint(ms.generate_solvers(ms.simplify(eqns)), join=and_)
>>>
>>> cons([1,2,3])
[1, 2, 1.999999999999997]
>>> cons([5,5,1])
[5, 5.000000000000006, 1]
>>>

请注意，我已经重写了符号约束，每次在左侧都有一个不同的变量。这是因为不使用 and_，构建的约束将只使用最后一个。因此，使用 and_ 强制优化为运行以便两者都得到尊重。我通过不重复使用左侧的变量来使其更容易解决。最后，我检查约束是否按预期工作。

另请注意，我还没有使用整数约束。当我们将所有约束放在一起时，我们可以应用它。

要对输出应用约束，我们首先构建一个惩罚，然后将其转换为约束。它效率不高，因为它再次需要内部优化。

>>> def penalty1(x):
...     x0,x1,x2 = x
...     return 480 - schedule(x0,x1,x2)
...
>>> @my.penalty.linear_inequality(penalty1)
... def penalty(x):
...     return 0.0
...
>>> lb,ub = zip(*bounds)
>>> c = my.constraints.as_constraint(penalty, lower_bounds=lb, upper_bounds=ub, nvars=3)
>>> c([5,5,1])
[13.126545665004528, 44.97820356778645, 1.0138152329128338]
>>> schedule(*_)
589.3806217359323
>>> c([50,50,10])
[50.0, 50.0, 10.0]
>>> schedule(*_)
2400.0
>>>

然后我们将它们放在一起，再次使用 and_。

>>> constraint = and_(c, cons, ints)
>>>
>>> constraint([5,5,1])
[23.0, 30.0, 2.0]
>>> c(_)
[23.0, 30.0, 2.0]
>>> cons(_)
[23.0, 30.0, 2.0]
>>> objective(_)
53450

最后，我们解决。

>>> from mystic.solvers import diffev2
>>> from mystic.monitors import VerboseMonitor
>>> mon = VerboseMonitor(10)
>>>
>>> result = diffev2(objective,x0=bounds, bounds=bounds, constraints=constraint, npop=50, gtol=100, disp=False, full_output=True, itermon=mon)
Generation 0 has ChiSquare: 43850.000000
Generation 10 has ChiSquare: 42725.000000
Generation 20 has ChiSquare: 42725.000000
Generation 30 has ChiSquare: 42725.000000
Generation 40 has ChiSquare: 42725.000000
Generation 50 has ChiSquare: 42725.000000
Generation 60 has ChiSquare: 42725.000000
Generation 70 has ChiSquare: 42725.000000
Generation 80 has ChiSquare: 42725.000000
Generation 90 has ChiSquare: 42725.000000
Generation 100 has ChiSquare: 42725.000000
STOP("ChangeOverGeneration with {'tolerance': 0.005, 'generations': 100}")
>>> result[0]
array([13., 37.,  1.])
>>> result[1]
42725.0

再次使用不同的求解器...

>>> from mystic.solvers import fmin
>>> mon = VerboseMonitor(10)
>>> result = fmin(objective, x0=[13,37,1], bounds=bounds, constraints=constraint, ftol=1e-6, disp=False, full_output=True, itermon=mon)
Generation 0 has ChiSquare: 42725.000000
Generation 10 has ChiSquare: 42725.000000
Generation 20 has ChiSquare: 42725.000000
STOP("CandidateRelativeTolerance with {'xtol': 0.0001, 'ftol': 1e-06}")

您会注意到，优化器找到的值比我们仅通过应用约束开始的值更好，但搜索不多。在严格受限的空间中，通常会立即找到解决方案。您将需要进行更多调查，看看这是否确实是全局最小值。

使用 Mystic 优化编译硬约束

Compiling hard constraints with Mystic optimisation

python

optimization

mystic