具有非常大量元素的組分配優化

Question

問題： 我有n個不同的元素。有幾個類別可以將每個元素 分配到其中。每個元素可以被分配到一個或多個類別。然後可以對每個元素或組單獨評估這些分配的性能。可以爲每個元素或元素組計算性能分數。

問題： 對於n和m非常大的值（其中n> m和n和m的順序），有效解決（最大化單個元素的分數總和） 10^5）？作爲一個側面問題，組合優化問題是否會減少這個特殊問題？

使用遺傳算法似乎有點偏離。製作染色體的羣體，每一個都可能具有20000個所有元素的羣組分配......或者它是什麼？我不知道在這樣大的染色體上使用什麼樣的突變，選擇和交叉操作符。

Answer 1

大的值n和m限制您的選擇。如果你將它建模爲n*m布爾型決策變量，那麼按照10^10變量的順序......那麼它可能會很大以將單個實例加載到RAM內存中。如果你將它建模爲M型的變量，那麼你將變量的連接數限制爲任意數（本例中爲20），並且需要添加一個硬約束，即同一個n中沒有2個變量應該具有相同的值M值，但它可以加載到RAM內存中。例如，假設您的約束（性能得分）不是微不足道的：我看到的唯一優化算法可以縮放到如此多的變量，例如Local Search變體（Tabu Search，Late Acceptance，...），例如在Roadef2012比賽中。