天津科技大学学报2026，Vol.41Issue(4)：71-80,10.DOI:10.13364/j.issn.1672-6510.20240208
面向强相关背包问题的BPSO算法优化
Optimization of BPSO Algorithm for Strongly Correlated Knapsack Problem
摘要
Abstract
The binary particle swarm optimization(BPSO)algorithm is an important swarm intelligence algorithm for solv-ing discrete binary space optimization problems.The knapsack problem,particularly the strongly correlated knapsack prob-lem,is often used as a benchmark for testing BPSO on ultra-high-dimensional optimization problems and has long been a research difficulty in this field.This difficulty arises because the solutions to strongly correlated knapsack problem are highly concentrated in the range of the connected space,making it likely that the BPSO algorithm may ignore this solution concen-trated aggregation space in the process of searching for the optimal,resulting in a significant deviation from the optimal solu-tion.This article proposes an improved BPSO algorithm method specifically for the strongly correlated knapsack problem,based on value density ranking and graded competitive optimization strategy.Inspired by the principle of graded knockout tournament,the algorithm enhances the granularity of spatial search in the exploration phase,thereby increasing the likeli-hood of discovering small regions where optimal solutions are concentrated and avoiding premature convergence to local optima.The experimental results show that the proposed algorithm approaches the true optimal solution with high accuracy across in low-,medium-or high-dimensional knapsack problems,significantly improving both the accuracy and reliability of solving strongly correlated knapsack problems.关键词
二进制粒子群(BPSO)算法/背包问题/分级竞优策略,基于价值密度展开策略Key words
binary particle swarm optimization(BPSO)algorithm/knapsack problem/graded competitive strategy/strategy based on value density expansion分类
信息技术与安全科学引用本文复制引用
赵青,刘涛,李昊..面向强相关背包问题的BPSO算法优化[J].天津科技大学学报,2026,41(4):71-80,10.基金项目
国家自然科学基金项目(12273077) （12273077）
国家重点研发计划项目(2022YFF0711500) （2022YFF0711500）
