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

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

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

中圖分類號: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

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

1 0-1背包問題描述

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

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

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

0，物品i未被選中

定義2: 背包內物品的總價值為:

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

約束條件:

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

2 基本粒子群算法

粒子群算法是一種進化計算技術，最早由Kennedy和Eberhart于1995年提出。源于對鳥群捕食行為研究的粒子群算法與遺傳算法類似，是一種基于迭代的優化工具，系統初始化為一組隨機解，通過迭代搜尋最優解[5]。……