陳 亮

(泰山職業(yè)技術(shù)學(xué)院,山東泰安271000)

求解背包問題的算法有很多種。經(jīng)典算法有分支定界法、動(dòng)態(tài)規(guī)劃法等,該類算法大多數(shù)過分依賴于問題本身特征,隨著問題規(guī)模擴(kuò)大,算法計(jì)算量按指數(shù)級(jí)增加,算法所需搜索時(shí)間過長(zhǎng)。智能優(yōu)化算法有蟻群算法、貪婪算法等,該類算法不依賴于問題本身特征,全局搜索能力較強(qiáng)。相關(guān)研究表明,把智能優(yōu)化算法與局部啟發(fā)式搜索相結(jié)合能有效提高算法搜索到最優(yōu)解的能力[1]。

混合蛙跳算法是2000年由Eusuf和Lansey提出的一種基于群體智能的后啟發(fā)式計(jì)算技術(shù),這種算法模擬青蛙群體尋找食物時(shí),按族群分類進(jìn)行思想傳遞的過程,該算法具有概念簡(jiǎn)單,調(diào)整的參數(shù)少,計(jì)算速度快,全局搜索尋優(yōu)能力強(qiáng),易于實(shí)現(xiàn)的特點(diǎn)[2]。文獻(xiàn)[3]使用基本混合蛙跳算法求解背包問題,但是由于基本混合蛙跳算法易陷入局部最優(yōu)。本文在其基礎(chǔ)上改進(jìn)了局部搜索策略,從而提出一種求解背包問題的混合蛙跳算法。

1 背包問題

背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題。背包問題分為0/1背包問題、完全背包問題、多重背包問題和混合背包問題。由于后三種可以轉(zhuǎn)換為0/1背包問題,因此本文只討論0/1背包問題。0/1背包問題的數(shù)學(xué)描述為：

假設(shè)有n個(gè)物體,背包中物品的總重量用W表示,wi為第i種物品的重量(i=1,2,…,n),背包中物品的總價(jià)值用V表示,vi為第i種物品的價(jià)值,xi為第i種物品的選擇狀態(tài),當(dāng)物件i被選入背包時(shí),xi=1否則xi=0,背包的最大容量為C,則0/1背包問題的數(shù)學(xué)模型為[4]：

2 混合蛙跳算法基本流程

隨機(jī)生成P只青蛙組成初始群體,每個(gè)青蛙個(gè)體表示問題的一個(gè)可行解,表示為U=(U1,U2,…,Un)(其中n為物體個(gè)數(shù)),然后計(jì)算族群內(nèi)所有的青蛙個(gè)體的適應(yīng)度f(i),并將青蛙按適應(yīng)度降序排列,再將所有青蛙分成m個(gè)族群,每個(gè)子族群包含k只青蛙,因此滿足關(guān)系P=m＊k。

2.1 局部更新策略

對(duì)于青蛙群體,具有全局最好適應(yīng)度的解記為Ug;對(duì)于每一個(gè)子族群,具有最好適應(yīng)度的解記為UB,最差適應(yīng)度的解記為UW,首先對(duì)每個(gè)族群進(jìn)行局部深度搜索,然后對(duì)局部最優(yōu)解進(jìn)行更新,更新策略為[5]：

其中,S表示青蛙個(gè)體的調(diào)整矢量,Smax表示青蛙個(gè)體允許改變的最大步長(zhǎng),rand表示0和1之間的隨機(jī)數(shù)。

2.2 引入高斯變異算子改進(jìn)局部更新策略

在基本混合蛙跳算法執(zhí)行過程中,不斷進(jìn)行全局信息交換,更新全局可行解的操作進(jìn)行,更新失敗的情況常常發(fā)生,一般采用隨機(jī)更新的方法,但該方法常常會(huì)陷入局部最優(yōu),降低算法的收斂速度。本文采用高斯變異算子對(duì)最差青蛙進(jìn)行擾動(dòng)：

其中,rand(0,1)為高斯隨機(jī)分布函數(shù)。

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

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

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

每只青蛙的選擇狀態(tài)向量表示背包問題的一個(gè)可行解。設(shè)青蛙U=(x1,x2,…,xn),其中xi表示第i個(gè)物體的選擇狀態(tài),當(dāng)物體被選中時(shí),xi=1,否則xi=0。青蛙個(gè)體適應(yīng)度函數(shù)f(i)定義為：

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

在構(gòu)造子族群時(shí),將所有青蛙按適應(yīng)度降序排列,依次選入子族群,即優(yōu)先選擇適應(yīng)度大的青蛙。按概率選擇青蛙進(jìn)行子族群的構(gòu)造。族群中的青蛙依概率選取構(gòu)造成子族群的概率公式為：

其中,pi為第i只青蛙被選中的概率,n表示每個(gè)族群中青蛙個(gè)數(shù),其中

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

定義1 給定一個(gè)青蛙狀態(tài)向量U,定義交換序C(i,j)為：

其中,i=j表示物體i由選中狀態(tài)變?yōu)槿∠麪顟B(tài),i≠j且xi≠xj表示物品i由選中狀態(tài)變?yōu)槿∠麪顟B(tài),并且物品j由取消狀態(tài)變?yōu)檫x中狀態(tài),其它情況取值0。經(jīng)過交換后的新向量為U′=U+C(i,j)。

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

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

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

其中,l表示更新Uw所用的交換序的個(gè)數(shù),lmax表示允許的最大的交換序個(gè)數(shù),S表示更新Uw所需的交換序列。

3.4 全局信息交換策略

在各個(gè)族群的青蛙進(jìn)行過局部搜索之后,將全體青蛙重新混合在一起,按照一定的概率對(duì)每一個(gè)青蛙個(gè)體按式(1)進(jìn)行變異操作,因此保證了青蛙個(gè)體的多樣性,也大大降低了搜索全局最優(yōu)解的時(shí)間消耗。

3.5 算法描述

步驟1 初始化青蛙族群,并生成初始子族群;

步驟2 按式⑵計(jì)算每只青蛙的適應(yīng)度,并按降序排序;

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

步驟4 按式⑷更新最差可行解UW得新解Uq;

步驟5 如果Uq優(yōu)于UW,則令UW=Uq,否則按式⑴產(chǎn)生新的可行解U′W,并令UW=U′W;

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

步驟7 輸出Ug。

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

本文采用兩個(gè)經(jīng)典0/1背包問題實(shí)例：實(shí)例1選自文獻(xiàn)[4],物體的重量集W={44,46,90,72,91,40,75,3 5,8,54,78,40,77,15,61,l7,75,29,75,63},物體的價(jià)值集V={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,l4,58},背包所能承受的最大重量C=878,模=20。實(shí)例2選自文獻(xiàn)[7],物體的重量集W={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1},物體的價(jià)值集V={220,208,198,192,180,180,165,162,160,158,155,130,125,122,12,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1},包所能承受的最大重量C=1 000,規(guī)模n=50。采用的對(duì)比算法是分支限界法。在相同實(shí)驗(yàn)條件下對(duì)兩個(gè)實(shí)例分別進(jìn)行20次仿真實(shí)驗(yàn)以統(tǒng)計(jì)其平均實(shí)驗(yàn)結(jié)果如表1。

表1 混合蛙跳算法和分支定界法在實(shí)例1、2上的測(cè)試結(jié)果

經(jīng)過對(duì)比分析實(shí)驗(yàn)結(jié)果得到以下結(jié)論：兩種算法執(zhí)行結(jié)果相同,說明混合蛙跳算法在解決組合優(yōu)化問題上是有效的;從時(shí)間對(duì)比可知,混合蛙跳算法的時(shí)間消耗較低,說明混合蛙跳算法是可行的。

5 結(jié)束語

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

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

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

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

[4] 吳哲輝.算法設(shè)計(jì)與分析[M].高等教育出版社,1993.

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

[6] 水文工具集網(wǎng).引入高斯變異算子的混合蛙跳算法[EB/OL].(2009-10-03)[2011-02-20]http：//cnhup.com.

[7] 賀毅朝,劉坤起,張翠軍,等.求解背包問題的貪心遺傳算法及其應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2007(11)：2655-2657.