王澤旭文 斌羅自強(qiáng)

（1.數(shù)據(jù)科學(xué)與智慧教育教育部重點(diǎn)實(shí)驗(yàn)室（海南師范大學(xué)）?？?71158）

（2.海南師范大學(xué)云計(jì)算與大數(shù)據(jù)研究中心 海口571158）（3.海南師范大學(xué)信息科學(xué)技術(shù)學(xué)院 ?？?71158）

1 引言

0-1背包問題（Knapsack problem）的定義為在給定背包容量的情況下實(shí)現(xiàn)背包的總價(jià)值最大化問題，抽象為數(shù)學(xué)概念就是一個(gè)組合優(yōu)化的完全NP問題［10］。0-1背包問題有著非常廣泛的實(shí)際應(yīng)用。在組合數(shù)學(xué)、應(yīng)用數(shù)學(xué)、密碼學(xué)等領(lǐng)域經(jīng)常將問題抽象為0-1背包問題來研究和解決。

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

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

2 0-1背包問題的數(shù)學(xué)模型如下

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

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

3 基本差分進(jìn)化算法

將由前一代個(gè)體之間的變異產(chǎn)生的變異個(gè)體，以一定的概率將變異個(gè)體與前一代個(gè)體進(jìn)行交叉實(shí)驗(yàn)，生成實(shí)驗(yàn)個(gè)體。根據(jù)適應(yīng)的的大小，在前一代個(gè)體與實(shí)驗(yàn)個(gè)體進(jìn)行貪婪選擇，將比較優(yōu)良的個(gè)體保留，實(shí)現(xiàn)進(jìn)化的目的［11］。

對于D維的空間維度，當(dāng)規(guī)模為NP的種群，進(jìn)化到第t代時(shí)，種群表示為其中某一個(gè)個(gè)體用來表示。在進(jìn)化過程中，對于每個(gè)都會(huì)進(jìn)行變異、交叉和選擇的操作。

3.1 變異操作

3.2 交叉操作

3.3 選擇操作

差分進(jìn)化算法采用的是“貪婪”選擇策略［1］，從前一代和試驗(yàn)個(gè)體中進(jìn)行貪婪選擇，選擇其中適應(yīng)度值最好的個(gè)體作為下一代，表達(dá)式如下：

其中，fitness(·)為適應(yīng)度函數(shù)，在選取適應(yīng)度函數(shù)時(shí)一般選擇目標(biāo)函數(shù)。本次實(shí)驗(yàn)選取目標(biāo)函數(shù)為適應(yīng)度函數(shù)并求取函數(shù)極小值。

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

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

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

變異策略rand/3/bin是根據(jù)在搜索的過程中前半階段要求開發(fā)能力較強(qiáng)，后半階段收斂能力較強(qiáng)的動(dòng)態(tài)需求變化，提出的一種新的變異策略。使得算法在快速收斂的同時(shí)，避免早熟陷入局部最優(yōu)。要取得全局最優(yōu)的結(jié)果就要保證在搜索的前期保證個(gè)體的多樣性，后期擁有較強(qiáng)的收斂速度。

在變異策略rand/3/bin中，使用以下方法產(chǎn)生新的變異個(gè)體：

4.2 改進(jìn)差分進(jìn)化算法的基本步驟

1）對參數(shù)進(jìn)行初始化：種群規(guī)模NP；縮放因子F；變異因子CR；空間維數(shù)D；進(jìn)化代數(shù)t=0；

3）對個(gè)體進(jìn)行評價(jià)：通過計(jì)算適應(yīng)度值，對個(gè)體進(jìn)行評價(jià)。

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

5）交叉：按式（2）對每個(gè)個(gè)體進(jìn)行交叉操作，得到試驗(yàn)個(gè)體

5 實(shí)驗(yàn)

在利用差分進(jìn)化算法進(jìn)行0-1背包實(shí)驗(yàn)時(shí)發(fā)現(xiàn)，變異策略為rand/1/bin和rand/2/bin的實(shí)驗(yàn)結(jié)果較穩(wěn)定，使用其他變異策略的差分進(jìn)化算法并不適合解決0-1背包的離散型問題，因此，本實(shí)驗(yàn)的加入編譯策略為rand/1/bin和rand/2/bin差分進(jìn)化算法。

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

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

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

表1 各算法實(shí)驗(yàn)結(jié)果對比

由圖表分析可得，遺傳算法、差分進(jìn)化算法、粒子群算法三種算法相比較而言，遺傳算法的實(shí)驗(yàn)結(jié)果更能逼近實(shí)驗(yàn)的最優(yōu)值，但是需要更多的實(shí)驗(yàn)迭代次數(shù)達(dá)到最優(yōu)值；粒子群算法實(shí)驗(yàn)結(jié)果相對較差，收斂速度中等；差分進(jìn)化算法的實(shí)驗(yàn)結(jié)果在逼近實(shí)驗(yàn)最優(yōu)值的同時(shí)，收斂速度很快，標(biāo)準(zhǔn)差較小，穩(wěn)定性強(qiáng)，比較適合解決0-1背包問題。

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

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

6 結(jié)語

本文對于離散型0-1背包問題提出了一種基于新的變異策略rand/3/bin的差分進(jìn)化算法，并通過實(shí)際算例驗(yàn)證了新變異策略的可行性與有效性。使用該變異策略的算法實(shí)現(xiàn)過程簡單，實(shí)驗(yàn)結(jié)果良好，算法穩(wěn)定，擁有較強(qiáng)的勘測能力與開發(fā)能力，非常適合用于大規(guī)模的0-1型背包運(yùn)算。