王泽昆

(河北地质大学 信息工程学院，河北 石家庄 050031)

0 引言

粒子群优化算法（PSO）[1]是1995年由Kennedy和Eberhart提出的一种著名群智能算法。该算法具有参数少，易实现和结构简单等优点，备受广大专家学者的关注。已经在神经网络[2]、约束优化[3]、调度问题[4]等众多问题中得到了成功应用。为了使 PSO算法能够求解离散组合优化问题，Kennedy和Eberhart[5]于 1997年提出了二进制粒子群优化算法（BPSO）。在BPSO中，利用Sigmoid转换函数将由实向量表示的粒子速度转换为由0-1向量表示的粒子位置，从而基于粒子速度实现对粒子位置的更新，可以说 Sigmoid转换函数是BPSO的设计与实现的关键所在[6]。

具有单连续变量的背包问题（KPC）[7]是1999年由Marchand和Wolsey提出的一个带有连续变量S的组合优化问题。目前，国内外学者对KPC的求解算法进行了研究，Lin等[8]首先将 KPC转化为一个伪背包问题和标准 0-1背包问题的组合形式，然后分别利用动态规划算法和分支定界法进行求解。He等[9]首先利用放缩法将 KPC中的连续变量离散化，将它转化为带有实函数的变载重背包问题的一个特例，然后基于动态规划法提出了一个精确算法DP-KPC。Zhao和Li[10]将KPC分解为两个具有标准 0-1背包问题形式的子问题进行求解，提出了一个时间复杂度为 O(n2)的 2-近似算法。最近，He等[11]提出了基于演化算法求解 KPC的新思路，首先基于降维法建立了 KPC的一个适于串行计算的数学模型和一个适用于并行求解的数学模型，然后基于混合编码二进制差分演化算法（HBDE）[12]给出了求解KPC的两个高效离散演化算法，具有混合编码的单种群二进制差分演化算法（S-HBDE）和具有混合编码的双种群二进制差分演化算法（B-HBDE）。……