差分進化變異策略rand/3/bin求解0-1背包問題?

王澤旭文 斌羅自強

（1.數據科學與智慧教育教育部重點實驗室（海南師范大學）海口571158）

（2.海南師范大學云計算與大數據研究中心 海口571158）（3.海南師范大學信息科學技術學院 海口571158）

1 引言

0-1背包問題（Knapsack problem）的定義為在給定背包容量的情況下實現背包的總價值最大化問題，抽象為數學概念就是一個組合優化的完全NP問題［10］。0-1背包問題有著非常廣泛的實際應用。在組合數學、應用數學、密碼學等領域經常將問題抽象為0-1背包問題來研究和解決。

解決0-1背包問題的方法主要分為兩大類：最優算法和啟發式的算法。最優算法主要包括動態規劃、貪婪算法、回溯法等；啟發式算法包括遺傳算法、差分進化算法、粒子群算法等主要以仿自然算法為主。最優算法雖然可以解出函數的最優解，但是比較局限于處理小規模的問題求解。啟發式算法［8］更適合大規模的運算求解，這類算法主要以仿自然體算法為主，適用于求解全局最優值，但是由于超級個體、變異概率、交叉概率等因子選擇不恰當會導致早熟或者收斂過慢等問題。

本文通過結合差分進化算法不同變異策略的特點，提出一種新的解決離散型0-1背包問題的變異策略（rand/3/bin），該策略解決了一般的差分進化算法在收斂前期缺少多樣性收斂過快導致早熟，收斂后期收斂速度過慢的等問題。

2 0-1背包問題的數學模型如下

每一件商品都擁有其自己的重量wi、價值pi，共有n件商品，若有一個容量為R的背包載荷，需要考慮如何分配使得商品的總重量在不超過最大容量的前提下，使得商品的總價值最大［8］。即當商品i被選中時，對應的xi為1，否則為0。因此，實際背包的總重量為商品的總價值為其函數模型如下：

式中xi取0或1，i=1，2，…，n，n，c均為正值。

3 基本差分進化算法

將由前一代個體之間的變異產生的變異個體，以一定的概率將變異個體與前一代個體進行交叉實驗，生成實驗個體。根據適應的的大小，在前一代個體與實驗個體進行貪婪選擇，將比較優良的個體保留，實現進化的目的［11］。

對于D維的空間維度，當規模為NP的種群，進化到第t代時，種群表示為其中某一個個體用來表示。在進化過程中，對于每個都會進行變異、交叉和選擇的操作。

3.1 變異操作

3.2 交叉操作

3.3 選擇操作

差分進化算法采用的是“貪婪”選擇策略［1］，從前一代和試驗個體中進行貪婪選擇，選擇其中適應度值最好的個體作為下一代，表達式如下：

其中，fitness(·)為適應度函數，在選取適應度函數時一般選擇目標函數。本次實驗選取目標函數為適應度函數并求取函數極小值。

4 對于0-1背包問題改進的離散差分進化算法

本文通過結合多種變異策略在搜索過程中不同階段的特點以及在搜索過程中勘測能力與開發能力需求的變化，提出一種基于新的變異策略rand/3/bin的改進差分進化算法。

4.1 基于變異策略rand/3/bin的差分進化算法簡介

變異策略rand/3/bin是根據在搜索的過程中前半階段要求開發能力較強，后半階段收斂能力較強的動態需求變化，提出的一種新的變異策略。使得算法在快速收斂的同時，避免早熟陷入局部最優。要取得全局最優的結果就要保證在搜索的前期保證個體的多樣性，后期擁有較強的收斂速度。

在變異策略rand/3/bin中，使用以下方法產生新的變異個體：

4.2 改進差分進化算法的基本步驟

1）對參數進行初始化：種群規模NP；縮放因子F；變異因子CR；空間維數D；進化代數t=0；

3）對個體進行評價：通過計算適應度值，對個體進行評價。

4）變異：按如下所示rand/3/bin策略對每個個體進行變異操作，并得到變異個體

5）交叉：按式（2）對每個個體進行交叉操作，得到試驗個體

5 實驗

在利用差分進化算法進行0-1背包實驗時發現，變異策略為rand/1/bin和rand/2/bin的實驗結果較穩定，使用其他變異策略的差分進化算法并不適合解決0-1背包的離散型問題，因此，本實驗的加入編譯策略為rand/1/bin和rand/2/bin差分進化算法。

本次實驗使用10個典型的0-1型背包測試數據進行試驗（測試數據：https：//github.com/woods 1060/0-1knapsack-data.git），并通過將兩種不同的變異策略的差分進化算法、遺傳算法、粒子群算法做仿真對比實驗，驗證使rand/3/bin變異策略的改進的差分進化算法的有效性。

在仿真對比實驗中將改進的差分進化算法與遺傳算法、粒子群算法以及兩種基本的差分進化算法（采用rand/1/bin，rand/2/bin變異策略）進行對比分析研究。在改進算法的實驗中，設定參數F0=0.95，CR=0.8，其他算法中的參數設置選擇文獻推薦值。為了在公平的仿真環境下測試各個算法的性能，分別對每個測試數據每個算法進行30次的獨立運行。表1總結了各個算法在不同測試數據上所得到的仿真結果，表中的real value表示測試的最優值，best表示最好的實驗結果，mean表示30次實驗的平均值，std表示標準差，t表示時間單位為s。為了方便清晰地觀察實驗結果，用粗體表示各實驗測試的最佳結果。圖1繪制了基于最優值的收斂曲線，與表1不同，這些收斂曲線可以提供收斂性，穩定性等多種信息。

圖1 各算法的測試收斂曲線

表1 各算法實驗結果對比

由圖表分析可得，遺傳算法、差分進化算法、粒子群算法三種算法相比較而言，遺傳算法的實驗結果更能逼近實驗的最優值，但是需要更多的實驗迭代次數達到最優值；粒子群算法實驗結果相對較差，收斂速度中等；差分進化算法的實驗結果在逼近實驗最優值的同時，收斂速度很快，標準差較小，穩定性強，比較適合解決0-1背包問題。

變異策略DE/rand/2/bin獲得實驗值大部分情況下接近于真實值，但是其需要迭代的次數非常多；變異策略DE/rand/1/bin收斂速度比較快，但是在實驗值中得到的實驗結果并不是很穩定；變異策略DE/rand/3/bin改進算法在快速收斂的同時獲得實驗結果最為接近最優值。

對于變異策略DE/rand/2/bin，利于保持種群的多樣性容易獲得最優值，但是它的收斂速度過慢，局部搜索能力較差；變異策略DE/rand/1/bin，局部搜索能力較強，收斂比較快，但是不利于獲得多樣性的種群，得到的實驗值不能很好地靠近最優值；變異策略DE/rand/3/bin結合了rand/1保持種群能夠多樣性和rand/2局部搜索能力較強的特點，實現搜索前半期增強種群多樣性，后半階段增強局部搜索的能力，從而達到實驗優化的結果。由實驗數據可得，使用新的變異策略的差分進化算法在處理大規模的0-1背包問題時，擁有顯著的優越性。

6 結語

本文對于離散型0-1背包問題提出了一種基于新的變異策略rand/3/bin的差分進化算法，并通過實際算例驗證了新變異策略的可行性與有效性。使用該變異策略的算法實現過程簡單，實驗結果良好，算法穩定，擁有較強的勘測能力與開發能力，非常適合用于大規模的0-1型背包運算。