3

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

一个“自然的”简约的表述可能是：

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

目标函数是确定性的，但求解成本很高。如果我不考虑二元变量，Scipy 的差分进化算法结果证明是解决我的问题的有用方法（收敛速度比盆地跳跃更快）。

已经有一些关于在基于差分进化的最小化问题中包含整数变量的证据。建议的方法将 y2,y3 变成连续变量 x2,x3 \in [0,1]，然后修改目标函数如下：

(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 的）中。

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

4

2 回答 2

1

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

于 2022-02-02T03:06:41.697 回答
1

我很想知道如何将二进制变量集成到连续差分进化算法中

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

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

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

尽管这两种变量类型都不是为二进制制作的，但它们都可以同样支持它。平均而言，GridVar需要较少的函数评估，因为它使用的浮点数比ChoiceVar.

于 2021-12-12T03:26:58.660 回答