一種改進的模擬退火螢火蟲混合算法求解0/1背包問題

任靜敏，潘大志

(西華師范大學數學與信息學院，四川南充 637000)

0 引言

背包問題(knapsack problem，KP)[1]是運籌學中典型的組合優化問題，即給定n個物品的重量和價值，選擇一組物品，使其總重量不超過給定的背包容量，并得到盡可能大的總價值.模型廣泛運用于資本預算、負荷問題、資源配置、項目選擇實際問題中.目前解決背包問題有兩類方法：精確算法和啟發式算法，其中精確算法有分支界定法、動態規劃法、回溯法、割平面法等，精確算法能求得問題的最優解，但往往時間成本過大，占有內存較大.啟發式算法的出現有效的提高了這些問題的求解效率.隨著啟發式算法不斷被研究和改進，求解背包問題在求解時間和求解精度上取得平衡，目前的啟發式算法有遺傳算法[2]、蟻群算法[3]、粒子群算法[4]、人工魚群算法[5]、螢火蟲算法[6]等.

此前已有學者將螢火蟲算法、模擬退火算法等用于求解一些實際問題.例如，候聰亞等[7]將振蕩權重函數和模擬退火算法引入到螢火蟲算法中,抑制螢火蟲算法在極值點區域出現無規則的振蕩現象,并將改進后的算法用于對橋式起重機箱型主梁優化.羅天洪等[8]提出一種基于時變螢火蟲群優化算法，該算法根據螢火蟲與鄰域內所有螢火蟲個體間的最小距離改變而時變步長，引入Boltzman選擇機制，實時動態調整搜索過程中的移動方向與位置，增強了算法的動態適應性，改進后的算法用于平面冗余機器人手臂運動學逆解問題求解，表現出很好的穩定性.陸屹等[9]提出針對專配序列規劃問題的人工螢火蟲算法，為了防止算法早熟，加入模擬退火算法對其進行改進.基于螢火蟲算法具有較強的全局搜索能力，而模擬退火算法有較好的局部搜索能力的特點，本文將模擬退火算法與螢火蟲算法結合用于求解0-1背包問題.在融合過程中加入基于種群密度自適應變異概率，當螢火蟲過于集中時增大變異概率以提高種群的多樣性.采用貪心修復算法實現不可行解的可行化，同時對模擬退火算法退火速度進行改進以減少運算時間，提高算法的運行效率.仿真實驗結果表明，改進后的模擬退火螢火蟲混合算法能有效的解決0-1背包問題.

1 0-1背包問題

0-1背包問題是組合優化中經典的NP問題之一，其具體描述如下：

給定n個物品和有一定重量限制的背包，其中物品i的重量為wi，價值為pi，背包的最大載重重量為V.考慮如何分配物品裝入背包，使得在保證不超過背包重量限制的情況下，背包內物品價值之和最大.故0-1背包問題的數學模型如下：

(1)

(2)

其中，X=(x1,x2,...,xn)，若xi=1則表示物品i裝入背包；若xi=0則表示物品i未裝入背包.

2 算法思想

2.1 螢火蟲算法

螢火蟲算法(Firefly Algorithm，FA)是一種基于種群的元啟發式算法，由xin-she yang于2009年首次提出.作為一種新型仿生群智能優化算法，螢火蟲算法具有魯棒性強、求解精度高、運算速度快等優點.根據螢火蟲的行為生態學，FA采用以下三個基本規則[6]:①螢火蟲是雌雄同體的，每只螢火蟲都會被其他螢火蟲吸引；②吸引度和亮度是一致的，亮度低的螢火蟲會移向亮度高的螢火蟲，當兩只螢火蟲之間的距離增加時，他們的吸引度和亮度就會降低，當其他螢火蟲沒有亮度時，螢火蟲會隨機移動；③螢火蟲的亮度與問題的目標相關.基于以上三條規則，亮度決定螢火蟲移動方向，吸引度決定螢火蟲移動距離，群體中的螢火蟲受更亮螢火蟲吸引，根據亮度和吸引度更新自己位置，螢火蟲經過多次的位置更新，最終所有個體飛行到最亮螢火蟲的位置，此時即是目標函數值最優.螢火蟲算法[6]具體描述如下：

(1)相對亮度：螢火蟲自身亮度與目標函數值有關：

Ii=f(xi)

(3)

其中，f(xi)為第i只螢火蟲所在位置對應的目標函數值.在最大化問題中，亮度高的個體吸引亮度低的個體，第i只螢火蟲的相對熒光亮度為：

I(r)=I0e-γr2

(4)

其中，I0為螢火蟲i的自身亮度，γ為光強吸收因子，r為兩只螢火蟲間的歐式距離.

(2)熒光在傳輸過程中會被傳輸介質吸收一部分，吸引度大小受光強吸收因子影響，螢火蟲間的吸引度為：

β(r)=β0e-γr2

(5)

其中，β0為螢火蟲在距離r=0時的吸引度，γ為光強吸收因子，r為兩只螢火蟲間的歐式距離.

(3)初始螢火蟲會被隨機分配于搜索空間的任意位置.每只螢火蟲代表一個可行解并隨機分布于搜索空間內，對于一個D維搜索空間，設置種群個數為n，第i只螢火蟲的位置表示為xi=(xi1,xi2,…,xin)，其位置更新公式為：

(6)

(7)

(8)

2.2 模擬退火算法

模擬退火算法(Simulated Annealing,SA)[10]由Metropolis等人于1953年提出來，隨后Kirkpatrick于1983年將其用于求解組合優化問題.模擬退火的算法思想來源于固體退火這一物理過程，將固體加熱至高溫，再使其自然冷卻.當固體溫度很高的時候，其內能較大，固體內部的粒子運動處于快速且無序的狀態，隨著溫度慢慢降低，固體的內能減小，粒子的運動逐漸趨于平穩，最后，當固體冷卻到平衡溫度時，內能最小且不再波動，粒子的狀態最為穩定.下面是模擬退火機制的原理：

(9)

由于0-1背包問題是有約束的最優化問題，所以本文采用了文獻[11]中的擴充Metropolis準則：

(10)

其中m為當前個體重量，Δm為當前個體與新個體的重量差值，ΔE為新個體與當前個體的適應度差值.T為當前溫度，本文采用文獻[12]中的快速退火算法，快速退火算法(VFSA)是由Ingber提出的一種降溫方法：

Ti=T0*Ki

(11)

其中i退火次數，T0為初始溫度，K∈(0,1)，本文設置K=0.95.

2.3 自適應變異操作

遺傳算法中針對染色體實行變異操作可增強全局搜索能力，變異算子目前有單點變異，多點變異，以及自適應變異等[13].本文提出一種基于個體密度的自適應變異概率，在此概率的基礎上基于兩個個體間的Manhattan距離實行兩點變異.種群內密度較大時說明個體過于集中，需要增大變異概率以此提高種群多樣性.當密度較小時種群內個體較離散，減小種群變異概率以保護優秀個體免受破壞.

對于個體i與種群內其他個體的平均Manhattan距離為公式(12)所示，個體i與種群內最好個體的Manhattan距離為公式(13)所示:

(12)

(13)

其中，n為種群規模，dim為解的維度，xi、xj、xbest分別是螢火蟲種群內的個體i、個體j和最好適應度個體.螢火蟲i的密度函數：

(14)

其中，count為螢火蟲i到群體內所有個體的Manhattan距離小于螢火蟲i到最好個體的Manhattan距離的個數.

自適應變異概率：

(15)

其中，crowd是常數，表示為個體i的擁擠程度，通常crowd∈(0,1).pmmax、pmmin分別是最大和最小變異概率，fi、fbest、fiavg分別為個體i適應度值、種群內最好個體適應度值和此時種群平均適應度值，ε為一個特別小的數，目的是防止分數無意義，本文取值ε=e-10.

當ρi

根據自適應變異概率確定對個體i是否采取變異操作，本文的變異操作是兩點變異，即對個體內隨機選取兩個點，對兩點間部分采用0變1、1變0的操作.

2.4 編碼方式

由于0-1背包問題是離散問題，而螢火蟲算法的尋優過程是連續的，所以需要將解空間內的連續解離散化，假設連續空間內的解為Xi={xi1,xi2,…,xiD},(i=1,2,…,n)，其中xij∈(-1,1),(i=1,2,…,n;j=1,2,…,D)，轉化為離散空間內的解為Yi={yi1,yi2,…,yiD}.本文采用以下編碼方式：

(16)

3 模擬退火螢火蟲混合算法求解0-1背包問題的具體實現

根據改進后的算法策略，構造了求解0-1背包問題的模擬退火螢火蟲混合算法(GMFS)，改進算法的具體步驟如下：

Step1：設置算法相關參數，種群大小n，光強吸收因子γ，螢火蟲吸引度β，最大變異概率pmmax，最小變異概率pmmin，初始溫度T0，終止溫度Tfinal，馬爾科夫鏈長度Lchain，快速降溫系數K，隨機初始化種群.

Step2：令T=T0，利用貪心算法對初始種群的不可行解進行修復.

Step3：當T

Step4：若L

Step5：利用貪心算法對新種群的不可行解進行修復，計算新解與舊解的能量差值，若差值為正則更新解；否則，以一定概率接受新解.

Step6：計算當前溫度T，計算并更新全局最優值和最優解.

Step7：對種群內個體根據改進變異概率判斷是否進行變異操作，并同時對不可行解作修復處理.轉Step3.

GMFS算法流程圖如圖1所示：

圖1 GMFS算法流程圖Fig.1 The flow diagram of GMFS

4 仿真實驗

為了驗證本文提出的GMFS算法的有效性，文章選用三組算例，背包內物品個數分別為20個，50個，100個.其中20個物品和50個物品的背包問題實驗數據來源[14], 100個物品的背包問題實驗數據來源[15]，每次實驗獨立運行30次.同組對比實驗的算法AGAA來源于文獻[16]，加入貪心修復的螢火蟲算法FA來源于文獻[17]，貪心模擬退火算法來源于文獻[11].

本文仿真實驗所用硬件環境為處理器：AMD A6-3420M APU with Radeon(tm) HD Graphics 1.50 GHz，安裝內存：4.0GB，系統類型64位操作系統，操作系統：Windows 7旗艦版.集成開發環境：MATLAB R2014b.下面對本文算法GMFS以及四個對比算法(AGAA，FA，SA，SAFA)進行參數設置，詳情見表1.其中Pc,Pm分別為交叉概率和變異概率，Tini,Tfin分別為初始溫度和終止溫度，L為markov鏈，K為退火參數，popsize為種群規模，maxgen為最大迭代次數，β0為最大吸引度，γ為介質吸收因子，α為步長因子.

表1 求解0-1背包問題的四種算法參數設置Tab.1 Parameter settings of 4 algorithms to solve the 0-1 knapsack problem

對三組算例分別獨立運行30次，測試結果分別與理論最優值進行對比，比較30次測試結果，得出各個算法的最優解，最差解和成功次數，并根據所得數據計算其平均值，標準差，偏差和改進比例.運行結果見表2，其中平均值和最優值可看出算法的尋優能力，標準差可以反映算法的魯棒性，偏差能衡量算法的穩定程度，偏差公式為：

偏差=(目標最優值-平均值)/目標最優值

改進比例對比本文算法，其他三種算法的改進程度，改進比例公式為：

改進比例=(改進算法最優值-其他算法最優值)/其他算法最優值

表2 4種算法所獲得統計值比較Tab.2 Statistic comparison of 4 algorithms

續表1：

N算法最優解最差解平均值成功次數偏差/%標準差改進比例/%50AGAA30983007306703.0920.640.16SA30132933296004.6029.732.98FA30953050307001.0612.230.26SAFA30903075308600.132.880.42GMFS3103310331033000-100AGAA79197453770003.94117.431.22SA79247621782702.3666.011.16FA74737070724309.6496.507.27SAFA80167991800160.191.700GMFS8016801680163000-

圖2 算例1中各算法的收斂結果Fig.2 Different algorithm convergence in example 1圖3 算例2中各算法的收斂結果Fig.3 Different algorithm convergence in example 2圖4 算例3中各算法的收斂結果Fig.4 Different algorithm convergence in example 3

通過對以上數據的對比觀察，可以看出，當物品個數為20時，SA、AGAA、GMFS、SAFA都能達到最優解，且SA的成功次數等于本文算法，反映了SA對于低維背包的搜索能力很強，但是從圖2中可以看出SA與AGAA的收斂速度不及GMFS.當物品個數為50時，GMFS在第4代時就找到全局最優值，而SA、SAFA與AGAA均未能在100代內搜索到，且此時SA的標準差與偏差數值都較大，說明當選擇物品個數較多時，GMFS能快速且精準的搜索到全局最優.當物品個數為100時，通過表2和圖4可看出，GMFS在退火次數30代內即能搜尋到全局最優值，相對其他三種算法的改進比例較大.SAFA雖然在30次獨立實驗中有6次找到最優值，但收斂速度慢，且精確度不高.SA與AGAA的偏差和標準差數值偏大，且都陷入了局部最優，相對本文算法其爬行能力較弱，全局搜索能力不強.而FA在三次算例中均未找尋到全局最優，這與螢火蟲算法自身局部搜索能力較弱有關系.仿真實驗表明，GMFS具有全局搜索能力強，收斂速度快等優點.

5 總結

本文算法GMFS在三次算例中都能很快搜尋到全局最優，得益于改進后的變異操作，增加其全局搜索能力，通過螢火蟲算法找尋新解與模擬退火算法選擇新解，在一定程度上保留了種群多樣性和當前最優解，貪心算法的加入減小了種群內解的損失，同時加快收斂到全局最優值的速度.說明本文算法能有效求解0-1背包問題，是一種性能較好，魯棒性強的算法.