基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题  

Binary particle swarm optimization algorithm based on novel S-shape transfer function for knapsack problem with a single continuous variable

作　　者：王泽昆 贺毅朝 李焕哲 张发展 WANG Zekun;HE Yichao;LI Huanzhe;ZHANG Fazhan(College of Information Technology,Hebei GEO University,Shijiazhuang Hebei 050031,China)

机构地区：[1]河北地质大学信息工程学院,石家庄050031

出　　处：《计算机应用》2021年第2期461-469,共9页journal of Computer Applications

基　　金：河北省自然科学基金资助项目(F2016403055,F2020403013);河北省高等学校科学技术研究计划项目(ZD2016005)。

摘　　要：为了高效求解具有单连续变量的背包问题(KPC),首先基于高斯误差函数提出了一个新颖S型转换函数,给出了利用该转换函数将一个实向量转换为0-1向量的新方法,由此提出了一个新的二进制粒子群优化(NBPSO)算法;然后,利用KPC的第二数学模型,并且把NBPSO与处理KPC不可行解的有效算法相结合,提出了求解KPC的一个新方法。为了检验NBPSO求解KPC的性能,利用NBPSO求解四类大规模KPC实例,并把所得计算结果与基于其他S、V型转换函数的二进制粒子群优化算法(BPSO)、具有混合编码的单种群二进制差分演化算法(S-HBDE)、具有混合编码的双种群二进制差分演化算法(B-HBDE)和二进制粒子群优化算法(BPSO)等的计算结果相比较。比较结果表明NBPSO不仅平均计算结果更优,而且稳定性更佳,说明NBPSO的性能比其他算法有显著提升。In order to solve the Knapsack Problem with a single Continuous variable(KPC)efficiently,a novel S-shape transfer function based on Gauss error function was proposed,and a new approach of transforming a real vector into a 0-1 vector by using the proposed transfer function was given,thereby a New Binary Particle Swarm Optimization algorithm(NBPSO)was proposed.Then,based on the second mathematical model of KPC and the combination of NBPSO and the effective algorithm to deal with the infeasible solutions of KPC,a new approach to solve KPC was proposed.For validating the performance of NBPSO in solving KPS,NBPSO was utilized to solve four kinds of large-scale KPC instances,and the obtained calculation results were compared with those of Binary Particle Swarm Optimization algorithms(BPSOs)based on other S and V-shape transfer functions,Single-population Binary Differential Evolution with Hybrid encoding(S-HBDE),Bipopulation Binary Differential Evolution with Hybrid encoding(B-HBDE)and Binary Particle Swarm Optimization algorithm(BPSO).The comparison results show that NBPSO is superior to the comparison algorithms in average calculation result and stability,illustrating that NBPSO has the performance better than other algorithms.

关 键 词：具有单连续变量的背包问题 组合优化问题 二进制粒子群优化算法 S型转换函数 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]