解決經典的0-1揹包問題，遺傳算法和動態規劃之間的最佳方法是什麼？

比方說，我有這樣的問題：解決經典的0-1揹包問題，遺傳算法和動態規劃之間的最佳方法是什麼？

揹包容量= 20億
數項= 500
重量每件商品的是隨機數
每個利潤100 20之間萬元item是1到10之間的隨機數字

那麼哪個是我的問題最好的方法？ GA還是動態規劃？

請給我一個簡單的解釋，正如我在我的新手..

來源

2013-02-13 hanx

是重量+利潤的整數？ – Dukeling 2013-02-13 08:43:51

是的。他們是整數 – hanx 2013-02-13 08:58:26

動態規劃（DP）：

精確算法 - 查找全局最優解
運行時間長
使用了大量的內存
很簡單實現

遺傳算法（GA）：

估計 - 並不一定找到全局最優解
短的運行時間
內存使用量取決於個體的數量，但一般是可管理
的解決方案的質量取決於選擇一個有效的表示+讓它運行足夠長的時間
實施起來相當簡單，設計決策可能會更復雜一些，尤其是如果您對GA沒有太多的經驗

爬山：

估計 - 並不一定找到全局最優解。更應以一個local optimum比GA停止，雖然有很多方法可以減少這種情況發生的機率
短的運行時間
非常低內存佔用
很簡單實現

DP（或者NP完全問題的任何精確算法）通常只是一個合理小問題的好主意，或者如果找到全局最優是最重要的。

有2種方法DP：（有一個相當簡單的優化，你只能存放2行，我的內存使用情況的分析去，前提是這種優化使用）

有一個矩陣項目X重量，與細胞的值作爲最大值

矩陣大小= 500×20 000 000

運行時間= O（500 * 20 000 000）= O（10 000 000 000）

內存=最大10 * 500 - > 5 000 - >短= 2個字節 - > 2 * 20 000 000 * 2 = 80 000 000 < 80 MB

說明：[I，J]下面表示從元素1到i的任何子集可獲得的最佳（最高）值，其中權重小於或等於 j。下面的更新規則意味着 - 找到不包含當前元素（因此權重和值保持不變）或包含它（所以查找（當前權重減去當前項目的權重）的最優值之間的最佳值並添加當前項目的值）。然後返回A [500,20000000]，它代表可以從所有元素的任何子集獲得的最大值，並且具有揹包大小的最大權重。

算法：
```
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值的矩陣，與細胞的值作爲最小重量

矩陣大小= 500×10 * 500

運行時間= 0（500 * 10 * 500）= 0（2 500 000）

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

說明：下面的[i，j]表示可從元素1的任何子集給我的價值等於 j。下面的更新規則意味着 - 找到不包含當前元素（因此權重和值保持不變）或包含它（所以查找（當前值減去當前項目的值）的最佳值並添加當前項目的權重）。任何單元格的值都是產生該值的子集的權重，因此我們需要查看所有單元格A [500，x]，它表示任何值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，每種情況都需要自行分析）。

來源

2013-02-13 08:34:08 Dukeling

問題的大小並沒有那麼糟糕。我認爲在這個問題中，所有的值都是整數，所以存在僞線性算法，可以在幾個小時內完成。 – iampat 2013-02-13 08:40:56

所以GA並不總是給最好的結果吧？如果我使用DP，我必須減少重量和容量的權利？我可以將DP與縮放（和舍入）結合起來嗎？這會影響結果嗎？ – hanx 2013-02-13 08:50:24

@ user2067479不，GA並不總是給出正確的結果。縮放和舍入（特別是在這種情況下）可能會顯着降低結果的質量。如果我記得，我會在檢查了一些東西后的幾個小時內編輯答案。 – Dukeling 2013-02-13 09:07:08

沒有「最好」的方法，每一個都有它的優點和缺點。
在這種情況下，權衡是在找到的解決方案的最優性之間 - GA不以任何方式保證找到最佳解決方案。
計算解決方案所需的時間/空間 - 使用動態編程將爲您節省一些冗餘計算，但您仍然必須至少計算一次所有可能的組合，以找到最佳解決方案（或甚至可能是任何解決方案）。

來源

2013-02-13 08:31:36 yurib

首先您需要考慮動態編程作爲一個確切的算法，可以保證答案將是一個最佳答案。另一方面，遺傳算法是一種啓發式算法，通常收斂於局部最優解。如果它們是整數，那麼存在一個僞線性（O（容量* number_of_items））的揹包的動態編程解決方案。在你的情況下，你需要大約1e10的操作和內存。單臺計算機可行。因此，如果找到最佳答案對您很重要，並且您有足夠的時間（按幾個小時的順序），則可以使用動態編程方法。否則，您可能更願意使用啓發式算法，如GA。

來源

2013-02-13 08:37:27 iampat

動態編程可以及時運行O(numItems * knapsackCapacity)和O(knapsackCapacity)內存。這意味着，對於您的要求，您必須：

約20.000.000 x 500 = 10.000.000.000操作 - 將可能完成在幾個小時內執行，這取決於你的機器上;
由於一件商品的利潤最多爲10件，且最多可以有500件商品，這意味着您的最大理論利潤不能超過10 x 500 = 5000。這可以用2個字節表示（一小段）。所以你還需要內存的2 x 20.000.000/1024/1024 ~= 38 MB來存儲你的DP陣列。再次，不是那麼多。

其他人已經提到了各自的優缺點。 GA將會更快完成，但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)

來源

2013-02-13 14:16:14 IVlad

解決經典的0-1揹包問題，遺傳算法和動態規劃之間的最佳方法是什麼？

回答

相關問題