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

• 作者: 王泽昆
• 来源期刊: 新一代信息技术
• 关键词: 具有单连续变量的背包问题 组合优化问题 二进制粒子群优化算法 V型传递函数
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 科技论文
• 页码范围: 30-37
• 页数: 8页
• 分类号: TP391.06
• 语种: 中文
• DOI: 10.3969/j.issn.2096-6091.2021.06.004

摘要

具有单连续变量的背包问题(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的性能比其他算法有显著提升.