遗传算法和动态规划哪种方法更适合解决经典的0-1背包问题？

Question

遗传算法和动态规划哪种方法更适合解决经典的0-1背包问题？

algorithmdynamicgeneticknapsack-problem

7

假设我有以下问题：

背包容量= 2000万
物品数量= 500
每个物品的重量是介于100到2000万之间的随机数
每个物品的利润是介于1到10之间的随机数

那么对于我的问题，哪种方法最好？遗传算法还是动态规划？

请给我一个简单的解释，因为我是新手...

- hanx

重量和利润是整数吗？ - Bernhard Barker

是的，它们是整数。 - hanx

4个回答

3

动态规划可以在时间复杂度为 O(numItems * knapsackCapacity) 和空间复杂度为 O(knapsackCapacity) 的情况下运行。这意味着，对于您的需求，您将有：

大约 20.000.000 x 500 = 10.000.000.000 次操作 - 根据您的计算机性能，可能只需要几个小时;
由于一个物品的利润最多为 10，并且您最多只能拥有 500 个物品，这意味着您的最大理论利润不能超过 10 x 500 = 5000。这可以用 2 字节（一个 short 类型）表示。因此，您还需要 2 x 20.000.000 / 1024 / 1024 ~= 38 MB 的内存来存储 DP 数组。同样，需要的内存并不算太多。

其他人已经提到了各自的优缺点。遗传算法会更快完成，但 DP 解决方案也应该可以在几个小时内完成，并给出精确答案。

个人而言，如果等待几个小时得到解决方案不是问题，我会选择 DP。

注意：这里是空间复杂度为 O(knapsackCapacity) 的 DP：

dp[i] = maximum profit obtainable for weight i
for i = 1 to numItems do
  for j = knapsackCapacity down to items[i].weight do
    dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].profit)

- IVlad

0

没有“最佳”方法，每种方法都有其优缺点。
在这种情况下，权衡的是找到的解的最优性 - 遗传算法并不能保证找到最佳解决方案。
以及计算解决方案所需的时间/空间 - 使用动态规划将节省一些冗余计算，但您仍然必须至少计算所有可能的组合一次才能找到最佳解决方案（或者甚至任何解决方案）。

- yurib

0

首先，您需要将动态规划视为一种确切的算法，它可以保证答案是最优解。另一方面，GA是一种启发式算法，通常会收敛到局部最优解。

对于背包问题，有一个伪线性（O（容量*物品数量））的动态规划解决方案，如果它们是整数，则可行。在您的情况下，您需要约1e10个操作和内存。这对于单台计算机来说是可行的。因此，如果找到最优解对您很重要，并且您有足够的时间（大约几个小时），则可以使用动态规划方法。否则，您可能更喜欢使用启发式算法，例如GA。

- iampat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

动态规划 (DP)：

精确算法-找到全局最优解
运行时间长
使用大量内存
非常容易实现

遗传算法 (GA)：

估计算法-不一定能找到全局最优解
运行时间短
内存使用取决于个体数量，但通常是可管理的
解的质量取决于选择有效的表示方法+让其运行足够长时间
相对简单易实现，设计决策可能会更加复杂，特别是如果您没有足够的遗传算法经验

爬山算法：

估计算法-不一定能找到全局最优解。比 GA 更容易陷入局部最优解，尽管有减少发生这种情况的方法
运行时间短
内存使用非常低
非常容易实现

DP (或任何 NP 完全问题的精确算法) 通常只适用于相对较小的问题，或者找到全局最优解是最重要的事情。

有两种 DP 的方法：（有一个相当简单的优化，只需存储 2 行，我的内存使用分析建立在这种优化被使用的假设上）

Have a matrix of items x weight, with cell value being the maximum value

Matrix size = 500 x 20 000 000

Running time = O(500 * 20 000 000) = O(10 000 000 000)

Memory = max 10 * 500 -> 5 000 -> short = 2 bytes -> 2 * 20 000 000 * 2 = 80 000 000 < 80 MB

Explanation: A[i,j] below represents the best (highest) value obtainable from any subset of the elements 1 to i with weight less than or equal to j. The update rule below means - find the best value between either not including the current element (thus the weight and value stays the same) or including it (so lookup the optimal value for (the current weight minus the current item's weight) and add the value of the current item to it). Then just return the A[500, 20000000], which represents the highest value obtainable from any subset of all elements with a maximum weight of the knapsack size.

Algorithm:
```
A[0, 0..20000000] = 0
for i = 1:500
for x = 0:20000000
  A[i, x] = max(A[i-1, x], value(i) + A[i-1, x-weight(i)])
// ignore value(i) + A[i-1, x-weight(i)] when weight(i) > x
return A[500, 20000000]
```
Have a matrix of items x value, with cell value being the minimum weight

Matrix size = 500 x 10*500

Running time = O(500 * 10*500) = O(2 500 000)

Memory = max 20 000 000 -> int = 4 bytes -> 2 * 500 * 4 = 4 000 < 4 KB

Explanation: A[i,j] below represents the lowest weight obtainable from any subset of the elements 1 to i with value equal to j. The update rule below means - find the best value between either not including the current element (thus the weight and value stays the same) or including it (so lookup the optimal value for (the current value minus the current item's value) and add the weight of the current item to it). The value at any cell is the exact weight of a subset to produce that value, so we need to look through all the cells A[500, x], which represents minimum weight subsets of elements for any value x.

Algorithm:
```
A[0, 0] = 0
A[0, 1..5000] = ∞
for i = 1:500
for x = 0:5000
  A[i, x] = min(A[i-1, x], weight(i) + A[i-1, x-value(i)])
// interpret A[i-1, x-value(i)] as 0 when value(i) > x
return largest x that A[500, x] <= 20000000
```

所以，是的，这些复杂性基本上说明了问题，你需要等待几个小时才能得到第一种方式，但只需要几秒钟就可以得到第二种方式，而且在内存使用方面也有类似的差异（尽管80 MB仍然是微不足道的）（请注意，这远非规则，每种情况都需要进行分析）。