Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (2): 461-469.DOI: 10.11772/j.issn.1001-9081.2020050710

Special Issue: 先进计算

• Advanced computing • Previous Articles     Next Articles

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   

  1. College of Information Technology, Hebei GEO University, Shijiazhuang Hebei 050031, China
  • Received:2020-05-20 Revised:2020-07-16 Online:2021-02-10 Published:2021-02-27
  • Supported by:
    This work is partially supported by the Natural Science Foundation of Hebei Province (F2016403055, F2020403013), the Science and Technology Research Program of Colleges and Universities in Hebei Province (ZD2016005).

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

王泽昆, 贺毅朝, 李焕哲, 张发展   

  1. 河北地质大学 信息工程学院, 石家庄 050031
  • 通讯作者: 贺毅朝
  • 作者简介:王泽昆(1996-),男,河北石家庄人,硕士研究生,主要研究方向:演化算法;贺毅朝(1969-),男,河北晋州人,教授,硕士,CCF高级会员,主要研究方向:演化算法、组合优化、强化学习;李焕哲(1975-),男,河北唐山人,副教授,博士,主要研究方向:演化算法、机器学习;张发展(1995-),男,山东潍坊人,硕士研究生,主要研究方向:演化算法、组合优化。
  • 基金资助:
    河北省自然科学基金资助项目(F2016403055,F2020403013);河北省高等学校科学技术研究计划项目(ZD2016005)

Abstract: 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), Bi-population 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.

Key words: Knapsack Problem with a single Continuous variable (KPC), combinatorial optimization problem, Binary Particle Swarm Optimization (BPSO) algorithm, S-shape transfer function

摘要: 为了高效求解具有单连续变量的背包问题(KPC),首先基于高斯误差函数提出了一个新颖S型转换函数,给出了利用该转换函数将一个实向量转换为0-1向量的新方法,由此提出了一个新的二进制粒子群优化(NBPSO)算法;然后,利用KPC的第二数学模型,并且把NBPSO与处理KPC不可行解的有效算法相结合,提出了求解KPC的一个新方法。为了检验NBPSO求解KPC的性能,利用NBPSO求解四类大规模KPC实例,并把所得计算结果与基于其他S、V型转换函数的二进制粒子群优化算法(BPSO)、具有混合编码的单种群二进制差分演化算法(S-HBDE)、具有混合编码的双种群二进制差分演化算法(B-HBDE)和二进制粒子群优化算法(BPSO)等的计算结果相比较。比较结果表明NBPSO不仅平均计算结果更优,而且稳定性更佳,说明NBPSO的性能比其他算法有显著提升。

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

CLC Number: