遗传算法和动态规划之间解决经典0-1背包的最佳方法是什么？ [英] Which is the best method between Genetic Algorithm and Dynamic Programming to solve classic 0-1 knapsack?

问题描述

比方说我有这样的问题：

Let's say I have problem like this:

• 背包容量= 2000万


• 数量项目数= 500


• 每个项目的权重是100到2000万之间的随机数


• 每个项目的利润是1到10之间的随机数

• Knapsack capacity = 20 million
• Number of item = 500
• Weight of each item is random number between 100 to 20 million
• Profit of each item is random number between 1 to 10

那么哪个是解决我的问题的最佳方法？ GA还是动态编程？

So which is the best method for my problem? GA or Dynamic Programming?

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

Please give me a simple explanation, as I'm newbie in this..

推荐答案

动态编程（DP）：

• 精确算法-查找全局最佳解决方案


• 运行时间长


• 使用大量内存


• 非常容易实现

• Exact algorithm - Finds global optimal solution
• Long running time
• Uses a lot of memory
• Very simple to implement

遗传算法（GA）：

• 估计-不一定找到全局最优解


• 运行时间短


• 内存使用量取决于个人数量，但通常是可管理的


• 解决方案的质量取决于选择有效的表示形式并使其运行足够长的时间


• 实施起来相当简单，设计决策可能是稍微复杂一点，尤其是如果您没有GA的丰富经验

• Estimation - Doesn't necessarily find the global optimal solution
• Short running time
• Memory usage depends on number of individuals but is generally managable
• Quality of solution depends on choosing an efficient representation + letting it run long enough
• Reasonably simple to implement, design decisions may be a little more complex, especially if you don't have significant experience with GAs

爬坡：

• 估算-不一定找到全局最优解。尽管可以通过多种方法来降低发生变化的机会，但与GA相比，更容易陷入局部最优的局面。发生这种情况


• 运行时间短


• 内存使用率非常低


• 实现起来很简单

• Estimation - Doesn't necessarily find the global optimal solution. More subject to halting at a local optimum than a GA, though there are ways to reduce the chance of this happening
• Short running time
• Very low memory usage
• Very simple to implement

DP（或用于NP完全问题的任何精确算法）通常仅是一个相对较小的问题或寻找全局最优解的好主意是最重要的事情。

DP (or any exact algorithm for an NP-complete problem) is generally only a good idea for a reasonably small problem, or if finding the global optimal is the most important thing.

DP有两种方法：（有一个相当简单的优化，其中只存储2行，我的内存使用情况分析是基于

There are 2 approaches to DP: (there is a reasonably simple optimization where you only store 2 rows, my memory usage analysis goes on the assumption that this optimization is used)

• 具有项x权重的矩阵，单元格值为最大值

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

矩阵大小= 500 x 20000000

Matrix size = 500 x 20 000 000

运行时间= O（500 * 20000 000）= O（1000000000000）

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

内存=最大值10 * 500- > 5 000->短= 2字节-> 2 * 20000000 * 2 = 80000000< 80 MB

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

说明：下面的A [i，j]表示从元素1到i的任何子集中权重小于的最佳（最高）值或等于 j。下面的更新规则意味着-在不包括当前元素（因此重量和值保持不变）或包括它之间找到最佳值（因此查找（当前重量减去当前项目的重量）的最佳值并添加当前项目的值）。然后只需返回A [500，20000000]，它代表从背包最大尺寸的最大权重的所有元素的任何子集中可获得的最大值。

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.

算法：

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]

具有项矩阵x值，其中单元格值为最小权重

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

矩阵大小= 500 x 10 * 500

Matrix size = 500 x 10*500

运行时间= O（500 * 10 * 500）= O（2 500 000）

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

内存=最大值2000000-> int = 4字节- > 2 * 500 * 4 = 4 000< 4 KB

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

说明：下面的A [i，j]表示可以从元素1到i的任何子集中获得的最低权重，其值等于 j。下面的更新规则意味着-在不包括当前元素（因此权重和值保持不变）或包括它之间找到最佳值（因此，查找最佳值（当前值减去当前项的值）并添加当前商品的重量）。任何单元格上的值都是子集的精确权重以产生该值，因此我们需要遍历所有单元格A [500，x]，该单元代表任何值的元素的最小权重子集x。

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.

算法：

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的数据仍然可以忽略不计）（请注意，根据规则，这是 FAR ，每个案例都需要自己进行分析）。

So, yeah, the complexities pretty much speak for themselves, you'll wait a few hours for the first way, but mere seconds for the second, and there's a similar difference in memory usage (though 80 MB is still near negligible) (note that this is FAR from a rule, every case needs to be analysed in its own right).

这篇关于遗传算法和动态规划之间解决经典0-1背包的最佳方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！