由网友(爱还逝。)分享简介：假设我们有：n维向量集U（向量v =＆LT; X1，X2，...，XN>）约束n维向量c =＆LT; X1 ... XN> n维权重w的矢量=＆LT; X1 ... XN> 整数s 我需要的算法，将选择美的载体为集R同时最大限度地降低运行成本（R）i need algorithm that would selec...

假设我们有：

n维向量集U（向量v =＆LT; X1，X2，...，XN>） 约束n维向量c =＆LT; X1 ... XN> n维权重w的矢量=＆LT; X1 ... XN> 整数s

我需要的算法，将选择美的载体为集R同时最大限度地降低运行成本（R）

i need algorithm that would select S vectors from U into set R while minimizing function cost(R)

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

（sumVectors是一个函数，总结所有的载体，像这样： sumVectors（{＆LT; 1,2取代; 3; 4＆GT;}）=＆LT; 4,6＆GT; ，而总和（小于1，2，3＆GT;）返回标6）

将溶液不必是最佳的。我只需要得到一个最好的猜测，我可以在preSET时间得到的。

The solution does not have to be optimal. I just need to get a best guess i can get in preset time.

任何想法从哪里开始？ （preferably东西更快/比遗传算法更聪明）

Any idea where to start? (Preferably something faster/smarter than genetic algorithms)

推荐答案

这是一个优化问题。因为你并不需要的最佳解决方案，您可以尝试随机优化的方法，例如，< A HREF =htt​​p://en.wikipedia.org/wiki/Hill_climbing相对=nofollow>爬山，在其中您开始用随机的（R的随机子集），并期待在组相邻的解决方案（添加或删除的当前解决方案的一个组成部分），用于那些与相应的成本函数的更好。

This is an optimization problem. Since you don't need the optimal solution, you can try the stochastic optimization method, e.g., Hill Climbing, in which you start with a random solution (a random subset of R) and look at the set of neighboring solutions (adding or removing one of the components of current solution) for those that are better with respective of the cost function.

要获得更好的解决方案，你也可以添加模拟退火到爬山的搜索。我们的想法是，在某些情况下，有必要移动到一个更差溶液中，然后后到达一个更好的。模拟退火效果更好，因为它允许一个移动为靠近该过程的一开始就更糟溶液。该算法变得不太可能允许一个更差溶液作为处理的推移。

To get better solution, you can also add Simulated Annealing to your hill climbing search. The idea is that in some cases, it's necessary to move to a worse solution and then arrive at a better one later. Simulated Annealing works better because it allows a move for a worse solution near the beginning of the process. The algorithm becomes less likely to allow a worse solution as the process goes on.

我粘贴一些样品爬坡蟒蛇code到这里解决您的问题： https://gist.github.com/921f398d61ad351ac3d6

I paste some sample hill climbing python code to solve your problem here: https://gist.github.com/921f398d61ad351ac3d6

在我的例子code， 研究 始终保持索引列表进入 U的 ，然后我用欧氏距离比较相似邻居之间。当然，你可以使用其他距离的功能，满足自己的需要。还要注意在code，我在飞行中获得的邻居。如果你有载体的一个大型游泳池 U ，你可能想缓存pre计算的邻居甚至可以考虑本地敏感散列为了避免 为O（n ^ 2） 对比。模拟退火可以加入到上述code。

In my sample code, R always holds a list of the index into U, and I use euclidean distance to compare the similarity between neighbors. Certainly you can use other distance functions that satisfy your own needs. Also note in the code, I am getting neighbors on the fly. If you have a large pool of vectors in U, you might want to cache the pre-computed neighbors or even consider locality sensitive hashing to avoid O(n^2) comparison. Simulated Annealing can be added onto the above code.

单随机运行的结果如下图所示。

The result of one random run is shown below.

我在 U 取值 = 10，这样我就可以将结果与最佳的解决方案进行比较。 在爬坡过程中停止在当没有更好的选择移动到与替换只有一个K-近邻第4步。

I use only 20 vectors in U, S=10, so that I can compare the result with an optimal solution. The hill climbing process stops at the 4th step when there is no better choice to move to with replacing only one k-nearest-neighbors.

我也用它迭代所有可能的组合穷举搜索运行。你可以看到，与穷举方法相比，爬山结果是pretty的好。只需4个步骤，以获得较小的代价（局部最小虽然）这需要穷尽搜索超过82K的步骤来战胜它。

I also run with an exhaustive search which iterates all possible combinations. You can see that the hill-climbing result is pretty good compared with the exhaustive approach. It takes only 4 steps to get the relatively small cost (a local minimum though) which takes the exhaustive search more than 82K steps to beat it.

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