面向强相关背包问题的BPSO算法优化OA
Optimization of BPSO Algorithm for Strongly Correlated Knapsack Problem
二进制粒子群(BPSO)算法是解决离散二进制空间最优化问题的重要群体智能算法,而背包问题经常被用作BPSO 算法的高维度优化问题的测试.背包问题中的强相关背包问题是这一领域的研究难点.强相关背包问题的解在解的空间范围上过于集中,BPSO 算法在寻优过程中很可能忽略解集中的聚集空间,导致搜索到的解与最优解相差较大.本文提出一种针对强相关背包问题的改进方法,即基于价值密度排序的分级竞优策略的 BPSO 算法.算法来源于分级淘汰赛的思想,增加全局搜索阶段空间上的搜索细腻程度,从而增加最优解聚集小区域被发现的可能性,避免过早陷入局部最优解.实验结果表明,无论是低维度、中维度还是高维度的强相关背包问题,本文方法都能以较高的准确率接近真实最优解,提高强相关背包问题求解的准确性和可靠性.
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.
赵青;刘涛;李昊
天津科技大学人工智能学院,天津 300457天津科技大学人工智能学院,天津 300457天津科技大学人工智能学院,天津 300457
信息技术与安全科学
二进制粒子群(BPSO)算法背包问题分级竞优策略,基于价值密度展开策略
binary particle swarm optimization(BPSO)algorithmknapsack problemgraded competitive strategystrategy based on value density expansion
《天津科技大学学报》 2026 (4)
71-80,10
国家自然科学基金项目(12273077)国家重点研发计划项目(2022YFF0711500)
评论