0

我真的很感激对这个实际问题的一些评论。

快速描述。 我有可变数量的链接，可用于构成给定的皮带宽度。问题是，每个链接有多少。选择标准：最好使用较长的项目。

例子。 假设我们要创建一个皮带宽度，W = 1024.0 其中一个模型具有以下链接长度：L = [34.0, 65.0, 96.0, 126.0]

问题是，每个链接有多少来制作宽度。

这是我尝试过的一些方法。

1.贪婪（选择最长的第一个以满足标准） c = [0,0,0,8] 其中c是每个项目的计数。这留下了 16.0 的差距，我什至无法容纳 1 个最小的项目。贪婪很容易，但并不好。

2. 选择循环 不太容易，我认为这是一个难题。我尝试了很多策略：填充小物品，然后依次移除它们以适应下一个尺寸。

3. 背包法 不太合适，因为这是基于给定数量的物品。

4. 子集和问题 这是背包的一个子类，但我无法让它工作。

5. 装箱问题 听起来很相似，但我无法将其应用于我的问题。

6.蛮力（随机选择） 奇怪的是，这个找到了很多完全匹配。我使用计数的简单多项式作为评级。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... 蛮力的解决方案之一是 [4, 0, 4, 4] 给出正好是 1024。问题是，这种方法通常会产生不同的选择，因此并不理想。

7.穷举搜索 不实用，因为选择太多。

8. 模拟退火 从蛮力的成功来看，这看起来是一个不错的选择。有人可以给我举一个简单的例子吗（请不要是另一个旅行推销员）。

9. 遗传和粒子群 不确定这些。

现在，我陷入困境和沮丧。是否有可用于此问题的直接算法？

4

1 回答 1

0

好吧，如果我理解正确的话，你需要选择 x1 个长度为 34 的对象，x2 个长度为 65 的对象，等等等等，这样所有这些对象的总和等于 W，但是有一个偏向较长的对象（在这种情况下，126.0 将是最受青睐的对象）。

我想你可以制作一个像这样的目标函数：

f(x1,x2,..,xn) = b1*x1*L1 + b2*x2*L2 + ... + bn*xn*Ln - p*(W - x1*L1 + x2*L2 + ... + xn*Ln)^2

其中 b1 到 bn 是对这些对象的偏差（正数是有利的，负数意味着对象是不受欢迎的），L1 到 Ln 是这些对象的长度，p 是不完全是 W 的惩罚（如果它必须完全W, p 是 inf。）

（我们也可以将其以矩阵形式表示为 f(X) = b^T*X*L - p*(W - I^T*X*L)^2，其中 b 和 L 是向量，X 是正方形x1, x2, ..., xn 的对角稀疏矩阵 I 是 1 的向量，T 是转置。）

所以目标然后它通过搜索整数 x1, x2, ..., xn 的 n 元组集来最大化 f。

好的，现在我想我明白了这个问题。:)

这是某种整数规划问题，但我不认为它完全符合二次整数规划问题。也许其他人知道它是什么。

在我的研究中，我一直在研究和试验模拟退火。它通常可以很容易地解决这些类型的离散优化问题。对于这个问题，您可能只使用线性或对数温度表。

但是，如果您只有几个对象，并且不打算进行大规模扩展，那么蛮力可能就可以了。但如果你要对成百上千的物体进行此操作，那么遗传算法、粒子群或模拟退火可能是聪明的想法。据我所知，实际上不可能先验地知道哪种优化启发式方法效果最好（例如，在令人满意的时间范围内找到所需精度的结果）。

我对其他解决方案的了解不够多，无法提供评论。

于 2011-12-21T08:57:43.447 回答