啓發式多維揹包

這是一個後續問題：Finding max value of a weighted subset sum of a power set 鑑於前面的問題解決了（以最優）在合理的時間內大小< = 15的問題，我想解決一個大小的問題〜2000近最優。啓發式多維揹包

作爲一個小例子的問題，我給予一定範圍的節點：

var range = [0,1,2,3,4];

的函數創建了一個功率範圍內的所有節點設置並分配每個組合一個分數值。負分數被刪除，導致以下數組S。 S[n][0]是按位全部包含節點的OR，並且S[n][1]是比分：

var S = [ 
    [1,0], //0 
    [2,0], //1 
    [4,0], //2 
    [8,0], //3 
    [16,0], //4 
    [3,50], //0-1 
    [5,100], //0-2 
    [6,75], //1-2 
    [20,130], //2-4 
    [7,179] //0-1-2 e.g. combining 0-1-2 has a key of 7 (bitwise `1|2|4`) and a score of 179. 
];

的最佳方案，最大限度地提高得分，將是：

var solution = [[8,3,20],180]

哪裏solution[0]是組合從S陣列。 solution[1]是最終得分。請注意，按位8 & 3 & 20 == 0表示每個節點僅使用一次。

問題細節：每個節點必須只使用一次，單節點組合的得分總是0，如上面的S陣列所示。

我目前的解決方案（seen here）使用動態編程並適用於小問題。我已經看到涉及動態編程的啓發式方法，如https://youtu.be/ze1Xa28h_Ns，但無法弄清楚如何將其應用於多維問題。鑑於問題的限制，適用的啓發式是什麼？

編輯：事情我已經試過

貪婪的方法（排序score最大到最小，選擇下一個可行的候選人）
與上述相同，但排序score/cardinality(combo)
GRASP（編輯每個score高達10％，然後分類，重複，直到在x秒內沒有找到更好的解決方案）

來源

2015-09-14 Matt K

你說15或2000的「尺寸」是多少？最大重量？物品的數量？如果是後者，並且實際上在內存中生成完整的powerset，那麼即使使用編譯語言，也可能無法獲得超過30的值。另外，爲什麼不首先消除所有消極因素，因爲它們永遠不可能處於最佳解決方案？（除非我誤解了。） –

啊，好問題。我稱之爲「大小」是範圍的長度。產生「功率集」的功能實際上也是一種啓發式功能，它只給我一個功率集的子集，通常小於10倍的尺寸（例如，尺寸1000的問題會產生10000的「S」）。 –

此問題實際上是一個整數優化問題，與二元變量x_i指示如果選擇的S的i^th元素和表示每個位被用來正好一次約束。目標是最大限度地提高所選元素的得分。如果我們定義S_i爲的S的i ^個元素，L_b是元素的索引在S與位b集，w_i爲與元件i相關的分數，並且假定有在設置S和k位n元件

min_{x} \sum_{i=1..n} w_i*x_i 
s.t. \sum_{i \in L_b} x_i = 1 \forall b = 1..k 
     x_i \in {0, 1}   \forall i = 1..n

在很多情況下，線性規劃求解是多少（很多很多）比在解決這些各種各樣的問題窮舉搜索更有效：，我們可以用數學符號爲寫這篇文章。不幸的是，我不知道任何JavaScript線性編程庫（一個谷歌查詢出現了SimplexJS和glpk.js和node-lp_solve - 我沒有任何經驗，無法立即得到任何工作）。因此，我將使用lpSolve包進行R中的實現。

w <- c(0, 0, 0, 0, 0, 50, 100, 75, 130, 179) 
elt <- c(1, 2, 4, 8, 16, 3, 5, 6, 20, 7) 
k <- 5 
library(lpSolve) 
mod <- lp(direction = "max", 
      objective.in = w, 
      const.mat = t(sapply(1:k, function(b) 1*(bitwAnd(elt, 2^(b-1)) > 0))), 
      const.dir = rep("=", k), 
      const.rhs = rep(1, k), 
      all.bin = TRUE) 
elt[mod$solution > 0.999] 
# [1] 8 3 20 
mod$objval 
# [1] 180

正如你會注意到的，這是你的問題的確切形式。但是，通過設置超時時間（您實際上需要使用R中的lpSolveAPI包而不是lpSolve包來執行此操作），可以在達到指定的超時之前獲得求解器找到的最佳解決方案。這可能不是最佳解決方案，您可以控制啓發式試圖停止嘗試尋找更好解決方案的時間。如果求解器在超時之前終止，則解決方案保證是最優的。

來源

2015-09-14 16:14:15 josliber

拍攝，我認爲你是對的，雖然我希望它不會來LP，因爲這意味着後臺處理LP（我還沒有找到一個可靠的JS解算器）。我還沒有嘗試足夠大的需要bitsets的問題（我的R很生鏽），但對於小型實例來說，它確實有效。 –

還有很多其他語言可以用來代替R（幾乎每種主要語言都有一個LP解決方案庫或三個）。這只是比任何DP解決方案都快，我認爲這是一條路。不幸的是，JavaScript對於運行LP來說是最理想的，因爲它滯留在瀏覽器中。你可以使用非javascript語言在服務器上進行優化，然後將結果發送回去嗎？ – josliber

是的，我認爲這就是我必須做的事情（服務器正在運行節點，所以JS是最好的）。你列出的那個節點包雖然對我來說是新的，但看起來它使用一個帶有JS包裝的C++二進制文件，所以我可能會在做「正確」的方式之前玩弄它。 –

A合理的啓發式（我想到的第一種）將是迭代地採用具有最大分數的可行元素的一種，消除與選定元素具有重疊位的所有元素。

我會實現這一點，首先按降序排序，然後迭代添加第一個元素並過濾列表，刪除重疊所選元素的任何元素。

在javascript中：

function comp(a, b) { 
    if (a[1] < b[1]) return 1; 
    if (a[1] > b[1]) return -1; 
    return 0; 
} 
S.sort(comp); // Sort descending by score 

var output = [] 
var score = 0; 
while (S.length > 0) { 
    output.push(S[0][0]); 
    score += S[0][1]; 
    newS = []; 
    for (var i=0; i < S.length; i++) { 
    if ((S[i][0] & S[0][0]) == 0) { 
     newS.push(S[i]); 
    } 
    } 
    S = newS; 
} 

alert(JSON.stringify([output, score]));

這將選擇元件7,8，和16，其具有得分179（而不是180°的最佳得分）。

來源

2015-09-14 06:12:09 josliber

我嘗試了這種貪婪的方法，首先按'score'排序，然後用'score/cardinality（combo）'排序，結果比我最熟悉的解決方案的結果差250倍。我知道基本揹包有一個簡單的方法來保證貪婪的啓發式的上限最壞情況，但這是可能的多維度？ –

@MattK在問題中說你已經嘗試了貪婪的分數並且不足以解決你的問題（這會爲我節省寫這個答案的時間！）。請編輯您的問題，以包括您嘗試過的內容以及效果不佳的示例數據集。 – josliber

你是對的，對不起！我被固定在類似DP的解決方案上，我忘記了我曾嘗試過的所有其他事情，直到您提到它。編輯添加 –

啓發式多維揹包

回答

相關問題