粒子群优化在0/1背包问题中的应用

【作者】 徐俊杰； 忻展红；

【机构】 北京邮电大学；

【摘要】 <正>§1 背包问题描述背包问题[1](Knapsack Problem)是组合优化领域内经典的NP完备问题,它在资金分配、货物装载、项目选择等问题上有着广泛的应用。背包问题有多种形式,本文研究的是最普通的单约束条件的0/1背包问题。其数学描述如下:给定n个物品及一个容积为c的背包,设p_j与w_j分别为物品j的价值(profit)与体积(capacity),求使得背包中所装物品价值最大的装载方案。即:更多还原

【Abstract】 Particle swarm optimization(PSO) is a novel stochastic global optimiza-tion algorithm. Through iterative operation which simulates the hunting behaviors ofbirds, it obtains satisfactory computation result. A solution to 0/1 knapsack problemby PSO is proposed. The feasibility of this method is demonstrated by elementaryeaperiments and future research issues are also discussed.更多还原