任靜敏，潘大志

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

0 引言

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

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

1 0-1背包問題

0-1背包問題是組合優(yōu)化中經(jīng)典的NP問題之一，其具體描述如下：

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

(1)

(2)

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

2 算法思想

2.1 螢火蟲算法

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

(1)相對(duì)亮度：螢火蟲自身亮度與目標(biāo)函數(shù)值有關(guān)：

Ii=f(xi)

(3)

其中，f(xi)為第i只螢火蟲所在位置對(duì)應(yīng)的目標(biāo)函數(shù)值.在最大化問題中，亮度高的個(gè)體吸引亮度低的個(gè)體，第i只螢火蟲的相對(duì)熒光亮度為：

I(r)=I0e-γr2

(4)

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

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

β(r)=β0e-γr2

(5)

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

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

(6)

(7)

(8)

2.2 模擬退火算法

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

(9)

由于0-1背包問題是有約束的最優(yōu)化問題，所以本文采用了文獻(xiàn)[11]中的擴(kuò)充Metropolis準(zhǔn)則：

(10)

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

Ti=T0*Ki

(11)

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

2.3 自適應(yīng)變異操作

遺傳算法中針對(duì)染色體實(shí)行變異操作可增強(qiáng)全局搜索能力，變異算子目前有單點(diǎn)變異，多點(diǎn)變異，以及自適應(yīng)變異等[13].本文提出一種基于個(gè)體密度的自適應(yīng)變異概率，在此概率的基礎(chǔ)上基于兩個(gè)個(gè)體間的Manhattan距離實(shí)行兩點(diǎn)變異.種群內(nèi)密度較大時(shí)說明個(gè)體過于集中，需要增大變異概率以此提高種群多樣性.當(dāng)密度較小時(shí)種群內(nèi)個(gè)體較離散，減小種群變異概率以保護(hù)優(yōu)秀個(gè)體免受破壞.

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

(12)

(13)

其中，n為種群規(guī)模，dim為解的維度，xi、xj、xbest分別是螢火蟲種群內(nèi)的個(gè)體i、個(gè)體j和最好適應(yīng)度個(gè)體.螢火蟲i的密度函數(shù)：

(14)

其中，count為螢火蟲i到群體內(nèi)所有個(gè)體的Manhattan距離小于螢火蟲i到最好個(gè)體的Manhattan距離的個(gè)數(shù).

自適應(yīng)變異概率：

(15)

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

當(dāng)ρi

根據(jù)自適應(yīng)變異概率確定對(duì)個(gè)體i是否采取變異操作，本文的變異操作是兩點(diǎn)變異，即對(duì)個(gè)體內(nèi)隨機(jī)選取兩個(gè)點(diǎn)，對(duì)兩點(diǎn)間部分采用0變1、1變0的操作.

2.4 編碼方式

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

(16)

3 模擬退火螢火蟲混合算法求解0-1背包問題的具體實(shí)現(xiàn)

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

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

Step2：令T=T0，利用貪心算法對(duì)初始種群的不可行解進(jìn)行修復(fù).

Step3：當(dāng)T

Step4：若L

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

Step6：計(jì)算當(dāng)前溫度T，計(jì)算并更新全局最優(yōu)值和最優(yōu)解.

Step7：對(duì)種群內(nèi)個(gè)體根據(jù)改進(jìn)變異概率判斷是否進(jìn)行變異操作，并同時(shí)對(duì)不可行解作修復(fù)處理.轉(zhuǎn)Step3.

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

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

4 仿真實(shí)驗(yàn)

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

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

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

對(duì)三組算例分別獨(dú)立運(yùn)行30次，測試結(jié)果分別與理論最優(yōu)值進(jìn)行對(duì)比，比較30次測試結(jié)果，得出各個(gè)算法的最優(yōu)解，最差解和成功次數(shù)，并根據(jù)所得數(shù)據(jù)計(jì)算其平均值，標(biāo)準(zhǔn)差，偏差和改進(jìn)比例.運(yùn)行結(jié)果見表2，其中平均值和最優(yōu)值可看出算法的尋優(yōu)能力，標(biāo)準(zhǔn)差可以反映算法的魯棒性，偏差能衡量算法的穩(wěn)定程度，偏差公式為：

偏差=(目標(biāo)最優(yōu)值-平均值)/目標(biāo)最優(yōu)值

改進(jìn)比例對(duì)比本文算法，其他三種算法的改進(jìn)程度，改進(jìn)比例公式為：

改進(jìn)比例=(改進(jìn)算法最優(yōu)值-其他算法最優(yōu)值)/其他算法最優(yōu)值

表2 4種算法所獲得統(tǒng)計(jì)值比較Tab.2 Statistic comparison of 4 algorithms

續(xù)表1：

N算法最優(yōu)解最差解平均值成功次數(shù)偏差/%標(biāo)準(zhǔn)差改進(jì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中各算法的收斂結(jié)果Fig.2 Different algorithm convergence in example 1圖3 算例2中各算法的收斂結(jié)果Fig.3 Different algorithm convergence in example 2圖4 算例3中各算法的收斂結(jié)果Fig.4 Different algorithm convergence in example 3

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

5 總結(jié)

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