求解多维背包问题的贪心粒子群算法

doi:10.3969/j.issn.1006-2475.2011.06.024

计算机与现代化 ›› 2011, Vol. 1 ›› Issue (6): 83-5.doi: 10.3969/j.issn.1006-2475.2011.06.024

求解多维背包问题的贪心粒子群算法

郝俊玲

对外经济贸易大学信息学院，北京 100029

收稿日期:2011-03-28 修回日期:1900-01-01 出版日期:2011-06-29 发布日期:2011-06-29

Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems

HAO Jun-ling

School of Information Technology & Management Engineering, University of International Business and Economics, Beijing 100029, China

Received:2011-03-28 Revised:1900-01-01 Online:2011-06-29 Published:2011-06-29

摘要/Abstract

摘要： 将多维背包问题的贪心变换和两种求解算法，用于求解具有重量和体积两个约束的背包问题，分别将物品按价值/重量、价值/体积比的凸组合和无穷范数的定义获得两组混合“性价比”权值向量，再以该混合“性价比”权值为依据构造两种贪心粒子群算法(wPSO，infPSO)。数值试验表明，算法wPSO、infPSO不仅大大优于现有粒子群算法，而且表现出优秀、稳定的搜索能力和快速定位最优解的搜索能力。

关键词: 多维背包问题, 粒子群算法, 贪心变换, 混合性价比

Abstract: 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.

Key words: multidimensional knapsack problem, particle swarm optimization, greedy transformation, integrative performanceprice ratio

郝俊玲. 求解多维背包问题的贪心粒子群算法[J]. 计算机与现代化, 2011, 1(6): 83-5.

HAO Jun-ling. Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems[J]. Computer and Modernization, 2011, 1(6): 83-5.

[1]	毛明扬, 徐胜超. 面向粒子群优化BP神经网络的粗糙集连续属性离散化算法[J]. 计算机与现代化, 2023, 0(09): 115-119.
[2]	韩雪. 基于约束聚类和粒子群算法的多路径规划[J]. 计算机与现代化, 2023, 0(08): 7-11.
[3]	陈刚, 王志坚, 徐胜超. 基于粒子群算法的移动边缘计算任务分配方法[J]. 计算机与现代化, 2022, 0(11): 32-36.
[4]	刘雅文, 蒋妍, 潘大志. 改进二进制和声搜索算法求解多维背包问题[J]. 计算机与现代化, 2022, 0(08): 13-19.
[5]	黄玲, 白晓波. 基于PSO-KPLS的教师科研绩效预测[J]. 计算机与现代化, 2022, 0(06): 8-12.
[6]	刘志锋, 舒志浩, 胥越峰, 杨舒伊, 沈文龙. 基于PSO自适应双策略的人工鱼群算法[J]. 计算机与现代化, 2022, 0(05): 46-53.
[7]	张彦虎, 鄢丽娟, 马志愤, 张彦军. 一种适用于多任务多资源移动边缘计算环境下的改进粒子群算力卸载算法[J]. 计算机与现代化, 2022, 0(05): 54-60.
[8]	李凌, 陈曦, 沈维捷, 熊汉武, 蔡冉冉. 面向电工装备智能监造的边缘缓存策略[J]. 计算机与现代化, 2022, 0(05): 61-67.
[9]	梁正友, 王璐, 李轩昂, 杨锋, . 基于改进PSO-TrICP算法的点云配准[J]. 计算机与现代化, 2022, 0(05): 90-95.
[10]	柴晨境, 刘宾, 潘晋孝. 基于阈值筛选的室内定位优化算法[J]. 计算机与现代化, 2022, 0(04): 79-85.
[11]	王哲, 王龙达, 刘罡, 王兴成, 王忠君, 鲍鲁杰. 基于三次样条插值的自动入库泊车免疫粒子群改进算法[J]. 计算机与现代化, 2022, 0(02): 7-12.
[12]	郭成, 张万达, 王波, 王加富. 多种群并行协作的粒子群算法[J]. 计算机与现代化, 2022, 0(01): 33-40.
[13]	陈翔, 邹庆年, 谢绍宇, 陈翠琼. 基于迁移学习策略的压板开关状态识别[J]. 计算机与现代化, 2021, 0(05): 120-126.
[14]	张忠, 邹燕飞, 刘淑英. 考虑交通流量的改进型电动汽车充/换电设施选址布局[J]. 计算机与现代化, 2020, 0(06): 114-.
[15]	杨万里1,2，周雪婷1，陈孟娜1. 基于Logistic映射的新型混沌简化PSO算法[J]. 计算机与现代化, 2019, 0(12): 15-.

求解多维背包问题的贪心粒子群算法

Greedy Particle Swarm Algorithms for Multidimensional Knapsack Problems

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价