摘 要:針對(duì)典型的背包問題，給出了一種基于粒子群算法的求解方法。考慮到粒子群算法在解決問題時(shí)容易陷入局部最優(yōu)的缺點(diǎn)，將模擬退火(SA)思想引入到了粒子群算法中，得到了粒子群 模擬退火算法。該算法保持了粒子群算法原有的簡單易實(shí)現(xiàn)特點(diǎn)，同時(shí)改善了粒子群算法易陷入局部最優(yōu)的缺點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該算法具有較好的求解質(zhì)量。

關(guān)鍵詞:模擬退火;粒子群; 背包問題; 遺傳算法

中圖分類號(hào):TP312 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)12-0085-02

Particle Swarm Algorithm Modified Based on Ideal of Simulated Annealing for Knapsack Problem

ZHANG Qi-liang1，2， CHEN Yong-sheng1

(1.Tongji University， Shanghai 201804， China; 2.School of Computer Science and Engineering， Jiangsu University of Science and Technology， Zhenjiang 212003， China)

Abstract:A solving process based on the particle swarm algorithm is presented to resolve the knapsack problem. Considering the shortcomings of the particle swarm algorithm that is easy to trap into local minimum， the ideal of the simulated annealing (SA) was introduced into the particle swarm algorithm and the PSO-SA algorithm was obtained. The PSO-SA algorithm maintains the characteristics of particle swarm algorithm easy to realize and also overcomes its defect. The experimental results show that the PSO-SA algorithm can obtain higher quality of the solution.

Keywords:simulated annealing; particle swarm; knapsack problem; genetic algorithm

背包問題是一個(gè)關(guān)于最優(yōu)解的經(jīng)典問題。背包問題有多種描述形式，通常被討論最多、最經(jīng)典的背包問題是0-1背包問題。背包問題屬于組合優(yōu)化的NP完全問題。傳統(tǒng)的求解方法主要有動(dòng)態(tài)規(guī)劃法[1]、貪婪法和一些智能優(yōu)化算法(遺傳算法[2]、模擬退火算法[3]、蟻群算法[4])。粒子群算法是一種基于群智能的新型仿生類算法，擅長解決連續(xù)優(yōu)化問題，但在離散優(yōu)化問題方面應(yīng)用較少。在此，嘗試采用粒子群算法解決0-1背包問題。

1 0-1背包問題描述

0-1背包問題的數(shù)學(xué)描述為:給定n種物品和1個(gè)背包，物品i的重量是wi，其價(jià)值為vi(wi>0，vi>0，i=1，2，…，n)，背包的容量為M，問如何選擇裝入背包的物品，使選中物品的總重量不超過背包的容量，但裝入背包的物品的總價(jià)值最大。數(shù)學(xué)模型為:

定義1: 定義變量xi為0-1變量:

xi=1，物品i被選中放入背包

0，物品i未被選中

定義2: 背包內(nèi)物品的總價(jià)值為:

max f(x1，x2，…，xn)=∑ n i=1 vixi

約束條件:

s.t.∑ n i=1 wixi≤M

2 基本粒子群算法

粒子群算法是一種進(jìn)化計(jì)算技術(shù)，最早由Kennedy和Eberhart于1995年提出。源于對(duì)鳥群捕食行為研究的粒子群算法與遺傳算法類似，是一種基于迭代的優(yōu)化工具，系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)解[5]。但同遺傳算法相比，粒子群算法的優(yōu)勢在于簡單、容易實(shí)現(xiàn)，并且沒有許多參數(shù)需要調(diào)整。目前，廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊控制以及其他遺傳算法的應(yīng)用領(lǐng)域。

粒子群算法中每個(gè)優(yōu)化問題的解都看作是搜索空間的一個(gè)“粒子”，算法首先初始化一群隨機(jī)粒子，然后通過一定次數(shù)的迭代找到最優(yōu)解。在每次迭代中，粒子通過2個(gè)極值更新自己的位置。這對(duì)極值是個(gè)體極值pBest和全局極值gBest。

2.1 粒子的速度和位置更新方程

在空間中運(yùn)動(dòng)的粒子通過極值pBest和gBest更新自己的速度和位置，其更新方程如下。

速度更新方程:

 V k+1=ω V k+c1(pBestk-xk)+c2(gBestk-xk) (1)

位置更新方程:

X k+1= X k+ V k+1 (2)

式(1)、式(2)中: V k為粒子第k次迭代前的飛行速度矢量; V k+1為粒子第k次迭代后的飛行速度矢量; X k為粒子在第k次迭代時(shí)的位置; X k+1為粒子在k次迭代后的新位置;pBestk為粒子本身所找到的最優(yōu)解位置;gBestk為整個(gè)種群找到的最優(yōu)解位置;ω為慣性權(quán)重因子，范圍(0~1);c1，c2為群體認(rèn)知系數(shù)，范圍(0~2)。

對(duì)于每一維粒子的速度都會(huì)被限制在一個(gè)最大速度 V max之內(nèi):

V k+1=V max，V k+1> V max

V k+1，V k+1≤ V max

2.2 粒子群解決背包問題算法

粒子群算法解決0-1背包問題的算法框架為:

初始化:定義粒子的維數(shù)為Dim;種群數(shù)為n;最大迭代次數(shù)為itera;ω，c1，c2，pBest，gBest為初值。隨機(jī)產(chǎn)生粒子的初始位置和初始速度。

while(當(dāng)前迭代次數(shù)<最大迭代次數(shù)itera)do

計(jì)算粒子群的適應(yīng)度(即物品價(jià)值)，若粒子的適應(yīng)度優(yōu)于原來個(gè)體的極值pBest，則用當(dāng)前粒子的適應(yīng)度作為個(gè)體極值pBest。

根據(jù)各個(gè)粒子的極值pBest找出全局極值gBest，若當(dāng)前找到的gBest優(yōu)于先前的gBest，則用當(dāng)前的gBest值作為全局極值。

按照式(1)更新粒子的速度，并限制在 V max范圍內(nèi)，按照式(2)更新粒子的位置。

進(jìn)行離散化:由于粒子的位置只有2種狀態(tài):0表示未選中;1表示選中。因此需要對(duì)粒子的位置進(jìn)行離散化，以0.5為分界點(diǎn)對(duì)函數(shù)值進(jìn)行離散化。

End

3 基于模擬退火思想的粒子群算法

模擬退火算法是基于蒙特卡羅(Monte Carlo)迭代求解法的一種啟發(fā)式隨機(jī)搜索算法，出發(fā)點(diǎn)來源于工程中固體物質(zhì)的退火原理。算法的基本思想是從一給定解開始，從領(lǐng)域中隨機(jī)地產(chǎn)生另一解，接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞，以一定的概率接受新解，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，直至找到最優(yōu)解。本文把這種思想用在粒子群算法中，對(duì)粒子的位置做一定的限制，引入模擬退火思想的粒子群算法解決0-1背包問題的算法框架為:

初始化。定義粒子的維數(shù)為Dim;種群數(shù)為n;最大迭代次數(shù)為itera;初值為ω，c1，c2，pBest，gBest為初值，初始溫度為T0;溫度控制參數(shù)為t;退火速度為。定義隨機(jī)產(chǎn)生粒子的初始位置和初始速度。

while(當(dāng)前迭代次數(shù)<最大迭代次數(shù)itera)do

計(jì)算粒子群的適應(yīng)度(即物品價(jià)值)。若粒子的適應(yīng)度優(yōu)于原來個(gè)體的極值pBest，則用當(dāng)前粒子的適應(yīng)度作為個(gè)體極值pBest。

根據(jù)各個(gè)粒子的極值pBest找出全局極值gBest，若當(dāng)前找到的gBest優(yōu)于先前的gBest，則用當(dāng)前的gBest值作為全局極值。

按照式(1)更新粒子的速度，并限制在 V max范圍內(nèi)，按照式(2)更新粒子的位置。

計(jì)算粒子位置變化引起的適應(yīng)度(物品價(jià)值)的改變值Δe，根據(jù)模擬退火思想，若Δe>0或者exp(Δe/t)>rand，則接受粒子的新位置，否則粒子的位置不變。其中，t為溫度控制參數(shù)，rand產(chǎn)生0~1之間的隨機(jī)數(shù)。

若接受粒子的新位置，則進(jìn)行退火操作:

t=t

對(duì)粒子位置進(jìn)行離散化。

End

4 數(shù)值實(shí)驗(yàn)

物品重量:w=[95 4 60 32 23 72 80 62 65 46];

物品價(jià)值:v=[55 10 47 5 4 50 8 61 85 87];

M=269。

粒子的維數(shù)=10;種群數(shù)=20;最大迭代次數(shù)=30;c1=c2=0.7;實(shí)驗(yàn)運(yùn)行30次，實(shí)驗(yàn)結(jié)果見表1。

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

算法獲優(yōu)次數(shù)算法最優(yōu)解算法最差解

基本粒子群18295238

模擬退火-粒子群26295241

5 結(jié) 語

本文將模擬退火思想引入到粒子群算法中，用以解決0-1背包問題。通過實(shí)驗(yàn)可以看出，加入模擬退火思想后粒子群算法比基本粒子群算法在求解時(shí)效果更好。粒子群在解決連續(xù)優(yōu)化問題中已取得了巨大的成功，對(duì)于解決離散問題應(yīng)用相對(duì)較少，還有待于進(jìn)一步研究。

參考文獻(xiàn)

[1]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京:電子工業(yè)出版社，2001.

[2]于美麗，張明.遺傳算法在0/1背包問題中的應(yīng)用及研究[J].計(jì)算機(jī)與現(xiàn)代化，2008(2):30-33.

[3]許小勇.基于改進(jìn)的模擬退火算法求解0/1背包問題[J].海南大學(xué)學(xué)報(bào):自然科學(xué)版，2008，26(4):356-358.

[4]馬良，王龍德.背包問題的螞蟻優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2001，21(8):4-5.

[5]高尚，楊靖宇.背包問題的混合粒子群優(yōu)化算法[J].中國工程科學(xué)，2006，8(11):94-97.

[6]李金玲，汪振華，王基維.基于模擬退火的遺傳優(yōu)化算法在TSP問題中的應(yīng)用[J].熱處理技術(shù)與裝備，2007，28(6):51-55.

[7]陳文蘭，戴樹貴.車輛路徑安排問題算法研究綜述[J].滁州學(xué)院學(xué)報(bào)，2007，9(3):19-25.

[8]曲強(qiáng)，陳雪波.基于Matlab的模擬退火算法的實(shí)現(xiàn)[J].鞍山科技大學(xué)學(xué)報(bào)，2003(3):196-199.

[9]高尚.求解旅行商問題的模擬退火算法[J].華東船舶工業(yè)學(xué)院學(xué)報(bào)，2003，17(3):13-16.

[10]孫燮華.用模擬退火算法求解旅行商問題[J].中國計(jì)量學(xué)院學(xué)報(bào)，2002，16(1):66-71.