Partition particle swarm optimization algorithm for multi-dimensional knapsack problem

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (36): 73-75.

• 研究、探讨 • Previous Articles Next Articles

Partition particle swarm optimization algorithm for multi-dimensional knapsack problem

ZHONG Peihua，WU Zhiyuan，MIAO Jianqun

School of Science，Jiangxi Agricultural University，Nanchang 330045，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-12-21 Published:2011-12-21

区域分割粒子群算法及多维背包问题求解

钟培华，吴志远，缪建群

江西农业大学理学院，南昌 330045

Abstract

Abstract: In order to overcome the premature convergence of discrete particle swarm optimi-zation（BPSO），a novel partition particle swarm optimization algorithm is proposed.With the partition method combined and some helpless points removed，the searching field of optimal solution is narrowed，and the probability of finding optimal solution enhances.To overcome the slow convergence of BPSO，the greedy method is used for a remedy to infeasible solutions and feasible solutions.Simulation results on benchmark problems show that the proposed algorithm is effective and has faster convergence speed and stronger global optimization ability.

Key words: multi-dimensional knapsack problem, discrete particle swarm optimization, partition

摘要： 为克服离散粒子群算法早熟的缺陷，通过引入区域分割算法后，移除了解空间中一些无希望的点集，缩小了解的搜索空间，提高了找到最优解的概率，并通过贪心策略对产生的粒子进行了修复和改进，克服了离散粒子群算法收敛慢的缺点。对典型多维背包问题的仿真实验表明，区域分割粒子群算法寻优能力更强，收敛更快。

关键词: 多维背包问题, 离散粒子群算法, 分割

ZHONG Peihua，WU Zhiyuan，MIAO Jianqun. Partition particle swarm optimization algorithm for multi-dimensional knapsack problem[J]. Computer Engineering and Applications, 2011, 47(36): 73-75.

钟培华，吴志远，缪建群 . 区域分割粒子群算法及多维背包问题求解[J]. 计算机工程与应用, 2011, 47(36): 73-75.

[1]	ZHANG Kehua, CHENG Weiqing. Differential Privacy Clustering Algorithm Based on Spatial Dynamic Partition [J]. Computer Engineering and Applications, 2021, 57(2): 97-103.
[2]	LIU Suolan, GU Jiahui, WANG Hongyuan, ZHANG Yunpeng. Human Behavior Recognition Based on Associative Partition and ST-GCN [J]. Computer Engineering and Applications, 2021, 57(13): 168-175.
[3]	LIU Yi, ZHANG Qigui. Fast Inter-Frame Prediction Algorithm with Partition Level Limitation [J]. Computer Engineering and Applications, 2021, 57(10): 200-203.
[4]	WANG Wenhui, LI Peng, HU Yundi. Measurement Set Partitioning Algorithm for Extended Target Based on Target Prediction [J]. Computer Engineering and Applications, 2020, 56(8): 143-148.
[5]	LI Chao, DONG Xinhua, CHEN Jianxia. Asynchronous Iterative Updates Method Based on Subgraph in Spark [J]. Computer Engineering and Applications, 2020, 56(7): 67-73.
[6]	HUANG Sheng, LI Mengfang, ZHANG Qianyun. Fast Inter Algorithm for Surveillance and Conference Video Based on Background Frame [J]. Computer Engineering and Applications, 2020, 56(22): 205-210.
[7]	YU Qiaoyu，WU Yaohua，WANG Yanyan. Tasks Scheduling Optimization of Tier-to-Tier Shuttle-Based Storage and Retrieval System with Double Lifts [J]. Computer Engineering and Applications, 2020, 56(20): 270-278.
[8]	AN Likui, HAN Liyan. Instruction Prefetching and Cache Partitioning for Multicore Cache WCEC Optimization [J]. Computer Engineering and Applications, 2020, 56(1): 69-75.
[9]	YAN Miaomiao, LIU Sanyang. Multi-Classes Interaction Teaching-Learning-Based Optimization Algorithm [J]. Computer Engineering and Applications, 2019, 55(9): 10-16.
[10]	WANG Junwei, CHEN Xing, DENG Yimin, LIU Yang, WANG Junhui. Research on Adaptive Layering of Feature Information of STL Model [J]. Computer Engineering and Applications, 2019, 55(6): 244-251.
[11]	SU Qing1, ZHANG Jingfang1, LIN Zhengxin1, LI Xiaomei1, CAI Zhaoquan2, ZENG Yong’an1. Collaborative Filtering Recommendation Algorithm Based on Improved Fuzzy Partition Clustering [J]. Computer Engineering and Applications, 2019, 55(5): 118-123.
[12]	YANG Kang, YOU Xiaoming, LIU Sheng. Self-Adaptive Double-Population Ant Colony Algorithm with Entropy [J]. Computer Engineering and Applications, 2019, 55(19): 66-73.
[13]	WANG Lingyang, CHEN Qinkuang, SHOU Lidan, CHEN Ke. Reserch of Entity Matching Based on Multiple Heterogenous Data [J]. Computer Engineering and Applications, 2019, 55(19): 87-95.
[14]	ZHONG Yuling, WANG Xite, BAI Mei, ZHU Bin, LI Guanyu. FODU：Fast Outlier Detection Approach on Uncertain Data Sets [J]. Computer Engineering and Applications, 2019, 55(19): 105-114.
[15]	DAI Min. Web Cache Replacement Strategy Based on NB Classifier for Re-access Probability Prediction [J]. Computer Engineering and Applications, 2019, 55(19): 134-140.

Partition particle swarm optimization algorithm for multi-dimensional knapsack problem

区域分割粒子群算法及多维背包问题求解

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics