基于模擬退火思想改進的粒子群算法求解背包問題

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

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

中圖分類號:TP312 文獻標識碼:A

文章編號: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

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

1 0-1背包問題描述

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

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

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

0，物品i未被選中

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

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

約束條件:

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

2 基本粒子群算法

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

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

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

在空間中運動的粒子通過極值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次迭代時的位置; X k+1為粒子在k次迭代后的新位置;pBestk為粒子本身所找到的最優(yōu)解位置;gBestk為整個種群找到的最優(yōu)解位置;ω為慣性權(quán)重因子，范圍(0~1);c1，c2為群體認知系數(shù)，范圍(0~2)。

對于每一維粒子的速度都會被限制在一個最大速度 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為初值。隨機產(chǎn)生粒子的初始位置和初始速度。

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

計算粒子群的適應度(即物品價值)，若粒子的適應度優(yōu)于原來個體的極值pBest，則用當前粒子的適應度作為個體極值pBest。

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

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

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

End

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

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

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

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

計算粒子群的適應度(即物品價值)。若粒子的適應度優(yōu)于原來個體的極值pBest，則用當前粒子的適應度作為個體極值pBest。

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

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

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

若接受粒子的新位置，則進行退火操作:

t=t

對粒子位置進行離散化。

End

4 數(shù)值實驗

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

物品價值: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;實驗運行30次，實驗結(jié)果見表1。

表1 實驗結(jié)果

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

基本粒子群18295238

模擬退火-粒子群26295241

5 結(jié) 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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