摘要
将多维背包问题的贪心变换和两种求解算法,用于求解具有重量和体积两个约束的背包问题,分别将物品按价值/重量、价值/体积比的凸组合和无穷范数的定义获得两组混合"性价比"权值向量,再以该混合"性价比"权值为依据构造两种贪心粒子群算法(wPSO,infPSO)。数值试验表明,算法wPSO、infPSO不仅大大优于现有粒子群算法,而且表现出优秀、稳定的搜索能力和快速定位最优解的搜索能力。
Two new greedy transformations and the inspired algorithms are proposed to solve multi-dimensional knapsack problems（MKP01） with weight and volume constraints.Convex combination and infinite norm of the ratio vectors of performance to weight and performance to volume are computed and two integrative ＂performance-price ratio＂ vectors are obtained.Two greedy PSOs variants（wPSO： weighted PSO,infPSO： infinite norm PSO） are presented for MKP01 based on the integrative ＂performance-price ratio＂.The standard PSO,hybrid wPSO and infPSO are applied to solve various scales of MKP instances.Numerical experiments illustrate that wPSO and infPSO not only outperform PSO greatly,but also show excellent and steady searching abilities and encouraging efficiency to locate the optimal solutions.
出处
《计算机与现代化》
2011年第6期83-87,共5页
Computer and Modernization
基金
对外经济贸易大学校级科研课题资助项目(10QNGLX02)
关键词
多维背包问题
粒子群算法
贪心变换
混合性价比
multidimensional knapsack problem
particle swarm optimization
greedy transformation
integrative performance-price ratio
