假设我们有以下条件:
- 一组n维向量U（向量v = < x1,x2 … ,xn >）
- 约束n维向量c = < x1…xn >
- 权重n维向量w = < x1…xn >
- 整数S
我需要一个算法，从U中选择S个向量到集合R中，同时最小化函数cost(R)
cost(R) = sum(abs(c-sumVectors(R))*w)(sumVectors是一个函数，用于将所有向量相加，例如：sumVectors({< 1,2 >; < 3 ,4>}) = < 4,6 >，而sum(< 1, 2, 3 >)返回标量6)
解决方案不必是最优的。我只需要在预设时间内得到一个最佳猜测。
有什么好的起点吗？（最好是比遗传算法更快/更智能的方法）
回答：
这是一个优化问题。由于你不需要最优解，你可以尝试随机优化方法，例如爬山算法，你可以从一个随机解（R的一个随机子集）开始，然后查看邻近解集（通过添加或移除当前解的一个组成部分），寻找那些在成本函数方面更好的解。
为了获得更好的解，你还可以在爬山搜索中加入模拟退火。这个想法是在某些情况下，有必要先移动到一个更差的解，然后再到达一个更好的解。模拟退火效果更好，因为它允许在过程开始时移动到一个更差的解。随着过程的进行，算法越来越不容易允许移动到更差的解。
我在这里粘贴了一些解决你问题的爬山Python样本代码：https://gist.github.com/921f398d61ad351ac3d6
在我的样本代码中，R始终保存一个指向U的索引列表，我使用欧几里得距离来比较邻居之间的相似性。当然，你可以使用其他满足你需求的距离函数。还要注意，在代码中，我是动态获取邻居的。如果U中有大量向量，你可能需要缓存预计算的邻居，甚至考虑使用局部敏感哈希来避免O(n^2)的比较。模拟退火可以添加到上述代码中。
下面显示了一次随机运行的结果。
我只在U中使用了20个向量，S=10，这样我就可以将结果与最优解进行比较。爬山过程在第4步停止，因为在只替换一个k最近邻的情况下，没有更好的选择可以移动到。
我也进行了穷举搜索，遍历所有可能的组合。你可以看到，与穷举方法相比，爬山结果相当不错。只需4步就能得到相对较小的成本（尽管是局部最小值），而穷举搜索需要超过82K步才能超过它。
initial R [1, 3, 4, 5, 6, 11, 13, 14, 15, 17]hill-climbing cost at step 1: 91784hill-climbing cost at step 2: 89574hill-climbing cost at step 3: 88664hill-climbing cost at step 4: 88503exhaustive search cost at step 1: 94165exhaustive search cost at step 2: 93888exhaustive search cost at step 4: 93656exhaustive search cost at step 5: 93274exhaustive search cost at step 10: 92318exhaustive search cost at step 44: 92089exhaustive search cost at step 50: 91707exhaustive search cost at step 84: 91561exhaustive search cost at step 99: 91329exhaustive search cost at step 105: 90947exhaustive search cost at step 235: 90718exhaustive search cost at step 255: 90357exhaustive search cost at step 8657: 90271exhaustive search cost at step 8691: 90129exhaustive search cost at step 8694: 90048exhaustive search cost at step 19637: 90021exhaustive search cost at step 19733: 89854exhaustive search cost at step 19782: 89622exhaustive search cost at step 19802: 89261exhaustive search cost at step 20097: 89032exhaustive search cost at step 20131: 88890exhaustive search cost at step 20134: 88809exhaustive search cost at step 32122: 88804exhaustive search cost at step 32125: 88723exhaustive search cost at step 32156: 88581exhaustive search cost at step 69336: 88506exhaustive search cost at step 82628: 88420