改進(jìn)的混合蛙跳算法求解背包問題

陳 亮

(泰山職業(yè)技術(shù)學(xué)院信息工程系，山東泰安 271000)

0 引 言

混合蛙跳算法(shuffled frog leaping algorithm，SFLA)是2000年由Eusuf和Lansey受青蛙群體覓食的行為啟發(fā)，并總結(jié)其規(guī)律而提出的一種基于群體智能的后啟發(fā)式仿生算法[1]。該算法將全局信息交換和局部深度搜索相結(jié)合，通過局部搜索使得信息能在局部個(gè)體間傳遞，其采用的混合策略能使得局部信息在全局范圍內(nèi)得以傳遞[2]。

1 背包問題

背包問題(knapsack problem)是一種組合優(yōu)化的NP完全問題，通常背包問題分為0/1背包問題、完全背包問題、多重背包問題、混合背包問題4種，由于后3種可以轉(zhuǎn)化為第一種，因此，文中只討論0/1背包問題[3]。

0/1背包問題的數(shù)學(xué)模型描述為:

式中:n——物體個(gè)數(shù);

w i——第i種物品的重量(i=1，2，…，n);

vi——第i種物品的價(jià)值;

xi——第i種物品的選擇狀態(tài)，當(dāng)物件i被選入背包時(shí)，定義變量xi=1或0;

C——背包的最大容量。

2 混合蛙跳算法基本流程

隨機(jī)生成P只青蛙，每只青蛙代表一個(gè)問題的解，記為Ui，并視為初始族群。然后計(jì)算族群內(nèi)所有的青蛙的適應(yīng)度，并將青蛙按適應(yīng)度降序排列，再將整個(gè)族群內(nèi)的青蛙分成m個(gè)子族群，每個(gè)子族群包含n只青蛙，因此滿足關(guān)系P= m*n。分配方法:按排定順序把第1，2，…，n只青蛙分別分到第1，2，…，n個(gè)子族群中，第a+1只青蛙分到第1個(gè)子族群中，依次類推，直至全部青蛙分配完畢[4]。

對(duì)于每一個(gè)族群，設(shè)UB為適應(yīng)度最好的解，UW為適應(yīng)度最差的解，U g為所有族群中具有全局最好適應(yīng)度的解。然后對(duì)每個(gè)族群進(jìn)行局部深度搜索，并對(duì)局部最優(yōu)解進(jìn)行更新，更新策略為[5]:

式中:S——青蛙個(gè)體的調(diào)整矢量;

S max——青蛙個(gè)體允許改變的最大步長(zhǎng);

rand——0和1之間的隨機(jī)數(shù)。

3 基于混合蛙跳算法的0/1背包問題求解

3.1 青蛙個(gè)體向量表示

一只青蛙代表一個(gè)解，用物體選擇狀態(tài)向量表示，則青蛙U=(x1，x2，…，xn)，其中xi表示第i個(gè)物體的選擇狀態(tài)。即xi=1，表示選中第i個(gè)物體;xi=0，表示未選中第i個(gè)物體。青蛙個(gè)體適應(yīng)度函數(shù)f(i)定義為:

3.2 子族群的構(gòu)造

在構(gòu)造子族群時(shí)，根據(jù)適應(yīng)度的大小進(jìn)行青蛙選擇，即適應(yīng)度較大，選擇權(quán)重越大，越有機(jī)會(huì)選中加入到子族群中。按概率選擇青蛙進(jìn)行子族群的構(gòu)造，概率公式定義為[6]:

且

式中:pi——第i只青蛙被選中的概率;

n——每個(gè)族群中青蛙個(gè)數(shù)。

3.3 青蛙個(gè)體的更新策略

定義1 給定一個(gè)青蛙向量U，定義交換序C(i，j)為:

式中:Ui變值 ——物品i由選中狀態(tài)變?yōu)槿∠麪顟B(tài)，或相反;

Ui=Uj——物品i與物品j交換位置，即物品i與物品j同為選中或取消狀態(tài);

Ui≠Uj——選中物品i且取消物品j，或相反。

則交換操作的新向量

定義2 在族群中任意選兩只青蛙的向量Ui，U j，由U i調(diào)整到U j的所有交換序列稱為U i到U j的距離D:

式中:m——調(diào)整的次數(shù)。

定義3 在族群中任意選兩只青蛙的向量Ui，U j，由U i調(diào)整到U j的距離長(zhǎng)度為|D|

式中:m——調(diào)整的次數(shù)。

由以上定義確定青蛙個(gè)體的更新策略如下:

式中:l——更新UW選擇用交換的D(UB，UW)交換序的個(gè)數(shù);

lmax——允許選擇的最大交換序的個(gè)數(shù);

s——更新UW所需的交換序列。

3.4 全局信息交換策略

在基本混合蛙跳算法執(zhí)行過程中更新可行解的操作反復(fù)被執(zhí)行，不可避免地遇到更新失敗的情況，基本的混合蛙跳算法采用了隨機(jī)更新可行解的方法，但隨機(jī)方法經(jīng)常會(huì)陷入局部最優(yōu)或使算法的收斂速度降低。文中引入高斯變異算子以修正更新策略，即用高斯變異算子對(duì)子族群最差青蛙(可行解)進(jìn)行擾動(dòng)，即:

式中:Rand——高斯隨機(jī)分布函數(shù)。

新的更新策略在整個(gè)迭代過程中將提高群體的多樣性和最差個(gè)體搜索的遍歷性，可以確保群體持續(xù)進(jìn)化，有利于提高收斂速度，并避免陷入局部最優(yōu)，進(jìn)而期望算法既能快速收斂到最優(yōu)解的附近，又能比較好地逼近精度，改進(jìn)了混合蛙跳算法的性能。

3.5 算法描述

步驟1:初始化青蛙族群，并生成初始子族群。

步驟2:按式(1)計(jì)算每只青蛙的適應(yīng)度，并按降序排序。

步驟3:搜索出全局最優(yōu)可行解Ug、子族群最優(yōu)可行解UB和最差可行解UW。

步驟6:更新完成后，對(duì)所有子族群的所有青蛙重新進(jìn)行混合，形成新的族群。

步驟7:輸出Ug。

4 實(shí)驗(yàn)結(jié)果分析

采用兩個(gè)經(jīng)典0/1背包問題實(shí)例，實(shí)例1選自文獻(xiàn)[7]，實(shí)例2選自文獻(xiàn)[8]。采用的對(duì)比算法為0/1背包問題分支限界法。在相同實(shí)驗(yàn)條件下對(duì)兩個(gè)實(shí)例分別進(jìn)行20次仿真實(shí)驗(yàn)，統(tǒng)計(jì)其平均實(shí)驗(yàn)結(jié)果，見表1。

表1 實(shí)驗(yàn)結(jié)果

經(jīng)過分析實(shí)驗(yàn)結(jié)果，兩種算法執(zhí)行結(jié)果相同，混合蛙跳算法的執(zhí)行速度有較大提高，因此，混合蛙跳算法是有效、可行的。

5 結(jié) 語

混合蛙跳算法是一種具有隨機(jī)智能和全局搜索能力的搜索算法，文中應(yīng)用混合蛙跳算法解決了0/1背包問題求解。實(shí)驗(yàn)證明，混合蛙跳算法在解決0/1背包問題上具有較好的可行性和有效性，采用高斯變異算子有效避免了易陷入局部最優(yōu)的缺陷，在一定程度上提高了算法的收斂速度。

[1] 羅雪暉.改進(jìn)混合蛙跳算法求解旅行商問題[J].通信學(xué)報(bào)，2009，7(7):130-134.

[2] 周麗娟.改進(jìn)粒子群算法和蟻群算法混合應(yīng)用于文本聚類[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2009，30(3):281-284.

[3] 吳哲輝.算法設(shè)計(jì)與分析[M].北京:高等教育出版社，1993:248-249.

[4] 羅雪暉.基于混合蛙跳算法的背包問題求解[J].科學(xué)技術(shù)與工程，2009，8(15):4364-4365.

[5] 駱劍平，李霞.求解TSP的改進(jìn)混合蛙跳算法[J].深圳大學(xué)學(xué)報(bào)，2010，4(2):173-177.

[6] 欒壺琛.混洗蛙跳算法研究及其發(fā)展現(xiàn)狀[J].大眾科技，2009(1):24-26.

[7] 賀毅朝.求解背包問題的貪心遺傳算法及其應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(11):19-22.

[8] 吳哲輝.算法設(shè)計(jì)與分析[M].北京:高等教育出版社，1993:251-152.