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

摘要

具有单连续变量的背包问题(KPC)既是一个组合优化问题,又是一个NP-hard问题,求解难度较大。为了更加高效地求解具有单连续变量的背包问题(KPC),本文首先提出了一个新颖V型转换函数,给出了利用该转换函数将一个实向量转换为0-1向量的新方法。然后基于新V型转换函数提出了一个新的二进制粒子群优化算法(NVBPSO);在KPC的离散数学模型基础上,基于NVBPSO与处理KPC不可行解的有效算法相结合,提出了求解KPC的一个新的高效方法。为了检验基于NVBPSO求解KPC的算法性能,利用它求解四类大规模KPC实例,通过与具有混合编码的单种群二进制差分演化算法(S-HBDE)、具有混合编码的双种群二进制差分演化算法(B-HBDE)和离散二进制粒子群优化算法(BPSO)等的计算结果比较表明:NVBPSO不仅比S-HBDE、B-HBDE和BPSO的平均计算结果更优,而且算法稳定性更佳,说明NVBPSO的性能比其他算法有显著提升。