通过 scipy 微分进化最小化的二元变量

Question

我有一个非线性最小化问题，它将连续变量和二元变量的组合作为输入。将其视为网络流量问题，阀门可以控制吞吐量，泵可以改变方向。

“自然”的极简主义表述可以是：

arg( min( f(x1,y2,y3) )) s.t.
    x1 \in [0,1] //a continuous variable
    y2,y3 \in {0,1}  //two binary variables

objective 函数是确定性的，但求解起来代价高昂。如果我不考虑二元变量，Scipy 的差分进化算法对我的问题来说是一种有用的解决方法（收敛速度比 basin hopping 更快）。

已经有一些可用的证据with regard to the inclusion of integer variables in a differential evolution-based minimization problem。建议的方法将 y2,y3 变成连续变量 x2,x3 \in [0,1]，然后修改 objective 函数如下：

(i) f(x1, round(x2), round(x3))

(ii) f(x1,x2,x3) + K( (x2-round(x2))^2 + (x3-round(x3))^2 )
     with K a tuning parameter

第三种可能是天真的方法是将二进制变量组合成单个连续变量 z \in [0,1]，从而减少优化变量的数量。

例如，

if z<0.25: y2=y3=0
elif z<0.5: y2=1, y3=0
elif z<0.75: y2=0, y3=1
else: y2=y3=1.

应该首选以上哪一项，为什么？我很想知道二进制变量如何以智能方式集成到连续差分进化算法（例如 Scipy's）中。

PS。我知道有一些可用的文献提出了专用的混合整数进化算法。现在，我想留在 Scipy。

Answer 1

I'd be very curious to hear how binary variables can be integrated in a continuous differential evolution algorithm

wrapdisc 是一个瘦包装程序包，可让您使用各种 scipy.optimize 优化器优化二进制变量和浮点数。它的自述文件中有一个用法示例。有了它，您根本不必调整 objective 函数。

从 v2.0.0 开始，它有两种可能的二进制编码：

ChoiceVar：这使用one-hot max编码。两个浮点数用来表示二进制变量。
GridVar：这使用四舍五入。一个浮点数用来表示二进制变量。

虽然这两种变量类型都不是为二进制设计的，但它们都可以同样支持它。平均而言，GridVar 需要更少的函数求值，因为它使用的浮点数比 ChoiceVar.

少一个

Answer 2

当 scipy 1.9 发布时，differential_evolution 函数将获得一个 integrality 参数，允许用户指示哪些参数应被视为整数。对于二进制选择，可以使用 (0,1) 的边界作为整数参数。

通过 scipy 微分进化最小化的二元变量

Binary variables for minimization by scipy differential evolution

python

scipy

nonlinear-optimization

mixed-integer-programming

differential-evolution