4

假设我们有：

  • 集合 U 的 n 维向量（向量 v = < x1,x2 ... ,xn >）
  • 约束 n 维向量 c = < x1...xn >
  • n 维权重向量 w = < x1...xn >
  • 整数 S

我需要从 U 中选择 S 向量到集合 R 中同时最小化函数成本（R）的算法

cost(R) = sum(abs(c-sumVectors(R))*w)

（sumVectors 是一个对所有向量求和的函数，如下所示：sumVectors({< 1,2 >; < 3 ,4>}) = < 4,6 >whilesum(< 1, 2, 3 >)返回标量 6）

解决方案不必是最优的。我只需要在预设时间内得到一个最好的猜测。

知道从哪里开始吗？（最好比遗传算法更快/更智能）

4

3 回答 3

4

这是一个优化问题。由于您不需要最佳解决方案，您可以尝试随机优化方法，例如Hill Climbing，其中您从随机解决方案（R 的随机子集）开始并查看相邻解决方案的集合（添加或删除当前解决方案的组成部分之一）对于那些具有各自成本函数更好的组件。

为了获得更好的解决方案，您还可以将模拟退火添加到您的爬山搜索中。这个想法是，在某些情况下，有必要转向一个更糟糕的解决方案，然后再找到一个更好的解决方案。模拟退火效果更好，因为它允许在工艺开始时采用更差的解决方案。随着过程的进行，该算法不太可能允许更差的解决方案。

我在这里粘贴了一些示例爬山 python 代码来解决您的问题： https ://gist.github.com/921f398d61ad351ac3d6

在我的示例代码中，R总是包含一个索引列表U，我使用欧几里得距离来比较邻居之间的相似性。当然，您可以使用其他满足您自己需求的距离函数。还要在代码中注意，我正在快速找到邻居。如果您在 中有大量向量U，您可能需要缓存预先计算的邻居，甚至考虑使用局部敏感散列以避免O(n^2)比较。可以将模拟退火添加到上述代码中。

一次随机运行的结果如下所示。

我只使用了 20 个向量U，S=10，这样我就可以将结果与最优解进行比较。当没有更好的选择时，爬山过程在第 4 步停止，只替换一个 k 最近邻。

我还进行了详尽的搜索，迭代了所有可能的组合。可以看到，与穷举法相比，爬山的结果相当不错。只需 4 步即可获得相对较小的成本（尽管是局部最小值），这需要超过 82K 步的详尽搜索才能击败它。

initial R [1, 3, 4, 5, 6, 11, 13, 14, 15, 17]
hill-climbing cost at step      1: 91784
hill-climbing cost at step      2: 89574
hill-climbing cost at step      3: 88664
hill-climbing cost at step      4: 88503
exhaustive search cost at step      1: 94165
exhaustive search cost at step      2: 93888
exhaustive search cost at step      4: 93656
exhaustive search cost at step      5: 93274
exhaustive search cost at step     10: 92318
exhaustive search cost at step     44: 92089
exhaustive search cost at step     50: 91707
exhaustive search cost at step     84: 91561
exhaustive search cost at step     99: 91329
exhaustive search cost at step    105: 90947
exhaustive search cost at step    235: 90718
exhaustive search cost at step    255: 90357
exhaustive search cost at step   8657: 90271
exhaustive search cost at step   8691: 90129
exhaustive search cost at step   8694: 90048
exhaustive search cost at step  19637: 90021
exhaustive search cost at step  19733: 89854
exhaustive search cost at step  19782: 89622
exhaustive search cost at step  19802: 89261
exhaustive search cost at step  20097: 89032
exhaustive search cost at step  20131: 88890
exhaustive search cost at step  20134: 88809
exhaustive search cost at step  32122: 88804
exhaustive search cost at step  32125: 88723
exhaustive search cost at step  32156: 88581
exhaustive search cost at step  69336: 88506
exhaustive search cost at step  82628: 88420
于 2012-10-18T21:37:51.680 回答
3

您将需要检查所有可能的集合 R 和最小化的成本。如果您在每次添加时以逐步最小化成本的方式选择向量，您可能找不到具有最低成本的集合。如果向量集 U 非常大并且计算速度太慢，您可能会被迫使用逐步方法。

于 2012-10-18T11:38:50.750 回答
1

您的问题本质上是一个组合优化问题。这些很难解决，但我可以提供一些建议。它们基于您无法探索所有组合的想法，因此您只能在贪婪的最佳解决方案附近进行探索。

有一种非常通用的方法叫做beam-search，它是一种启发式方法，它本质上修改了最佳优先搜索以使用有限的内存（波束宽度）。它依赖于这样一个概念，即对于任何给定的部分解决方案，您可以计算与向集合中添加一些新成员相关的分数，以及当前集合的分数（因为您有一个很好的目标函数）。这个想法是，然后您从空集开始，并为堆栈上的每个状态不断选择 n 个最佳下一个状态，然后当所有状态都展开时，您丢弃堆栈上除了 n 个最佳状态之外的所有状态并重复。这将为您提供 n 个可能的解决方案，并且您可以选择得分最高的。

但是，这可能行不通，因为您的目标函数的细节会使这个选择向量立即接近约束，然后（经过一些步骤，具体取决于您的成本向量和分量向量的相对比例）寻找小向量以减少差异。如果是这样，您可以使用此方法的解决方案来初始化随机游走/模拟退火策略（将允许您从集合中随机添加或删除），以寻找接近您通过光束搜索获得的解决方案的更好解决方案。

于 2012-10-18T13:39:33.157 回答