1

我无法解决包括从集合中选择项目的问题。

我有一个项目集合，每个项目都有三个特征，比如 X、Y 和 Z，它们有一个 double 值

我有几个目标：

1) 达到所选项目的所有 X 值之和的特定下限。

2) 达到所选项目的所有 Y 值之和的特定下限。

3) 达到所选项目的所有 Z 值的平均值的特定下限。

4）尽量减少仍满足上述要求的项目的选择。

我不确定要尝试哪种类型的优化算法，任何正确方向的指针都将不胜感激。如果可能的话，我想以某种方式优先考虑我的目标并使我的界限像“软”一样，即使它们不能同时满足，仍然会返回一个“接近”的选择。

4

3 回答 3

1

您的问题可以用混合整数问题建模。如果你的集合不是太大（比如几百个值），我会使用这个模型，因为在标准 lp 文件中编写它比对启发式编程和参数化更容易。

您可以将此问题交给混合整数问题求解器：

  • 硬币或（免费），
  • Cplex（商业和广阔，除非你是学者），
  • 古罗比（商业），
  • GLPK（免费，但速度慢）...

我在下面用伪数学语言写了两个模型（注意这不是 LP 格式）。

硬边界

让 N 是您的对象的集合，X_min 和 Y_min 是您需要达到的下限，ZZ 是 Z 值的平均下限。我使用一个二进制变量 s_i，如果对象 i 被选中，它的值为 1，否则为 0。确切的问题可以写成：

Minimize sum_{i in N} s_i
Subject to:
      sum_{i in N} X_i s_i >= X_min
      sum_{i in N} Y_i s_i >= Y_min
      sum_{i in N} (Z_i - ZZ) s_i >= 0
      foreach i in N, s_i in {0, 1}

多目标

请注意，正如 Andreas 的回答所述，还有其他方法可以做到这一点。这是一种更容易（在我看来）确定目标优先级和“放松”问题的方法，您可以使用上面的线性求解器。

您添加三个松弛变量 dX、dY、dZ 和三个（正）权重系数 wX、wY、wZ。变量 dX、dY 和 dZ 将代表违反约束，而“权重”代表您对违反约束的重视程度。

然后你可以把问题写成：

Minimize sum_{i in N} s_i + wX dX + wY dY + wZ dZ
Subject to:
      dX >= sum_{i in N} X_i s_i - X_min
      dY >= sum_{i in N} Y_i s_i - Y_min
      dZ >= sum_{i in N} (Z_i - ZZ) s_i
      foreach i in N, s_i in {0, 1}
      dX, dY, dZ >= 0

然后，您可以对 wX、wY 和 wZ 进行参数化，以便确定目标的优先级：例如，对于较大的权重值，模型将返回“硬绑定”解决方案（如果存在）；那么，与另一个相比，具有较高权重的约束“不太可能”被违反（当然，它并不完全那么简单，只是给出一个想法）。

于 2012-12-08T13:47:28.267 回答
1

这听起来像，例如，模拟退火

http://en.wikipedia.org/wiki/Simulated_annealing

可以很好地解决这个问题。

只需使用合适的软化目标函数（即，对您拥有的 4 个目标中的每一个进行惩罚），然后开始退火。

一些术语：这绝对不是线性编程，因为您的变量是二进制变量（即，是否包含此项）。

如果您的目标函数足够好，您可以使用贪心算法来真正快速地获得合理的结果

于 2012-12-07T19:27:51.857 回答
1

您描述的问题类似于背包问题。在背包问题中，您有一定尺寸的特定袋子和特定尺寸且具有特定价值的物品。然后，您希望在不超过大小的情况下最大化该值。

但是，您的问题有点不同。我会将其表述为最小化 X、Y 和 Z 值的总和以及最小化项目的数量，并对代表下限的 X、Y 和 Z 施加约束。通过这个定义，您可以看到您的问题实际上是多目标的（我假设其中一些目标是相互冲突的，例如最小化具有可行空间的项目）。您必须编写的函数称为适应度函数，用于计算某个选择的质量。要处理约束，您可以使用作为适应度返回的惩罚，或者如果您可以在算法中处理约束，请指定约束违反的程度。

我会使用启发式方法来解决这个问题。为此，我们需要选择问题解决方案的表示（数据结构）。

就像在背包中一样，您可以选择二进制表示。这意味着对于每个项目，您的二进制向量中都有一个维度，如果包含则为 1，如果不包含则为 0。向量的长度等于项目的数量。

至于求解器，存在许多用于这种表示的元启发式算法。但最接近的选择可能是在考虑二进制编码的情况下开发的遗传算法。如果您想以多目标方式解决问题，我会选择 NSGA-II 或 SPEA2 作为算法。如果您以加权和方法或通过其他方式将您的目标组合成单个值，那么 John Holland 定义的标准遗传算法就足够了。多目标算法的优势在于它们探索所有非支配解决方案的帕累托前沿，例如导致 X 较大但 Y 和 Z 不及其他解决方案（例如 X、Y 和 Z 最小）的解决方案，但项目的数量更高。

已经提到的模拟退火算法是解决此类问题的另一种元启发式算法。但是，目前尚无法判断哪个会更好。然而，当您事先不知道适应值的范围时，模拟退火有点难以配置，因为您需要一个初始温度和适合该范围的冷却计划。

您还可以采用更简单的构造启发式方法，例如以贪婪的方式工作（例如，始终采用 X、Y 和 Z 最大的项目，该项目要么刚好低于或达到边界。但我认为元启发式会找到更好的解决方案。

于 2012-12-08T08:44:25.683 回答