折扣{0-1}背包问题的简化新模型及遗传算法求解

当前折扣{0-1}背包问题（D{0-1}KP）模型将折扣关系作为一个新的个体，导致求解过程必需采取修复法对个体编码进行修复，求解方式较少。针对求解方法单一的问题，通过改变模型中二进制的编码表达方式，提出折扣关系不在个体编码中的表达方法。首先，设定对任意折扣关系，当且仅当所涉及个体编码值同时为1（即其乘积为1）时，折扣关系成立，据此建立简化折扣{0-1}背包问题（SD{0-1}KP）模型；然后，针对SD{0-1}KP模型，基于杰出者保留策略（EGA），结合贪心策略（GRE），提出改进遗传算法——第一遗传算法（FG）；最后，再结合罚函数法，提出求解SD{0-1}KP高精度罚函数法——第二遗传算法（SG）。结果表明，SD{0-1}KP能够完全覆盖D{0-1}KP问题领域，与FirEGA相比，所提出的两类算法在求解速度方面优势明显，且SG算法首次引入罚函数法，有效地丰富了该问题的求解算法。     

折扣{0-1}背包问题粒子群算法的贪婪修复策略探究

群智能启发式算法求解折扣{0-1}背包问题（D{0-1}KP）时,为提升求解效率和求解质量,需采用某种修复与优化策略将非正常编码个体转换为符合解约束条件的编码个体。在引入项集价值密度概念基础上,以粒子群算法（PSO）为例,提出一组基于项集的贪婪修复与优化方法（group greedy repair and optimization algorithm,GGROA）,并进一步构造PSO-GGRDKP算法（PSO based GGROA for solving D{0-1}KP）以探究GGROA方法的可行性和性能。PSO-NGROADKP（PSO based NGROA for solving D{0-1}KP）和PSO-GRDKP（PSO based GROA for solving D{0-1}KP）是基于项贪心修复与优化方法的粒子群算法。在D{0-1}KP标准数据集的实验结果表明：与PSO-NGROADKP和PSO-GRDKP相比,PSO-GGRDKP算法的解误差率略高,但算法时间性能分别提升了13.8%、12.9%。     

贪心核加速动态规划算法求解折扣{0-1}背包问题

针对现有动态规划算法求解折扣{0-1}背包问题（D{0-1}KP）缓慢的问题，基于动态规划思想并结合新型贪心修复优化算法（NGROA）与核算法，通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划（GCADP）算法。首先利用NGROA对问题进行贪心求解，得到非完整项；然后通过计算得到模糊核区间的半径和模糊核区间范围；最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划（BDP）算法求解。实验结果表明：GCADP算法适用于求解D{0-1}KP，且在求解速度上相比BDP算法平均提升了76.24%，相比FirEGA算法平均提升了75.07%。     

变异蝙蝠算法求解折扣{0-1}背包问题

针对确定性算法难于求解规模大、数据范围广的折扣{0-1}背包问题（D{0-1}KP）,提出了基于蝙蝠算法的快速求解D{0-1}KP的变异蝙蝠算法（MDBBA）。首先,利用双重编码解决D{0-1}KP的编码问题;其次,将贪心修复与优化算法（GROA）应用于蝙蝠个体适应度计算中,使算法快速得到有效解;然后,选择使用差分演化（DE）的变异策略提高算法的全局寻优能力;最后,蝙蝠个体按一定概率进行Lévy飞行,增强算法探索能力和跳出局部极值的能力。对四类大规模实例的仿真计算表明：MDBBA非常适于求解大规模的D{0-1}KP,比第一遗传算法（FirEGA）和双重编码蝙蝠算法（DBBA）求得的最优值和平均值都更优,MDBBA收敛速度明显快于DBBA。     

基于细菌觅食算法求解折扣{0-1}背包问题的研究

折扣{0-1}背包问题（D{0-1}KP）是新型的0-1背包问题。提出了基于细菌觅食算法（BFO）求解D{0-1}KP的方法,首先描述了D{0-1}KP的两个数学模型,然后将BFO分别与两个数学模型相结合,即细菌个体分别采用二进制向量和四进制向量的编码方法,并利用贪心策略优化初始解和修复非正常编码个体,给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明,FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例,能得到最优解或近似比接近1的近似解。     

基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题

针对确定性算法难于求解的各项的重量系数和价值系数在大范围内取值的折扣{0-1}背包问题（D{0-1}KP）,提出了基于差分演化策略的混沌乌鸦算法（DECCSA）。首先,采用混沌映射生成初始乌鸦种群;然后,采用混合编码方式和贪心修复与优化策略（GROS）解决了D{0-1}KP的编码问题;最后,引入差分演化策略提高算法的收敛速度。对4类大规模D{0-1}KP实例的计算结果表明：DECCSA比遗传算法、细菌觅食算法和变异蝙蝠算法求得的最好值和平均值更优,能得到最优解或更好的近似解,非常适于求解D{0-1}KP。     

基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题

针对大规模的折扣{0-1}背包问题（D{0-1}KP）难以用确定性算法求解的问题,提出了基于Lévy飞行的差分乌鸦算法（LDECSA）。首先,利用混合编码解决D{0-1}KP的第二数学模型的编码问题;其次,利用新的贪心修复与优化算法（NROA）处理求解过程中产生的不可行解;然后,针对乌鸦个体过早陷入局部最优和收敛较慢等缺陷,引入Lévy飞行和差分策略;最后,通过实验确定了感知概率和飞行长度的合理取值以及差分策略的选择。对四类大规模D{0-1}KP实例的计算结果表明：LDECSA非常适合求解大规模D{0-1}KP,能得到满意的近似解。     

自适应细菌觅食算法求解折扣{0-1}背包问题

针对确定性算法难以求解的大规模折扣{0-1}背包问题（D{0-1}KP）,提出了自适应细菌觅食算法（ABFO）求解D{0-1}KP的两种算法。首先,给出了D{0-1}KP的两种数学模型;然后,针对细菌觅食算法的趋化操作提出了自适应趋化策略;最后,利用两种贪心修复与优化策略处理两种数学模型中的不可行解,得到求解D{0-1}KP的FirABFO和SecABFO算法。仿真实验表明,FirABFO和SecABFO均能得到最优解或近似比几乎等于1的近似解,非常适于求解D{0-1}KP,并且SecABFO 的求解性能比FirABFO更优。     

基于离散混合多宇宙算法求解折扣{0-1}背包问题

为了利用多宇宙算法（MVO）求解折扣{0-1}背包问题（D{0-1}KP）,基于模运算建立了离散型隧道模型和离散虫洞模型,引入具有反向搜索与突变特性的局部搜索策略,提出了第一个具有四进制编码的离散混合多宇宙算法DHMVO。在利用修复与优化算法消除不可行解的基础上,基于DHMVO提出了求解D{0-1}KP的一个新方法。为了检验DHMVO求解D{0-1}KP的性能,利用Kruskal-walli检验确定了其参数的最佳取值;将DHMVO求解四类大规模D{0-1}KP实例的计算结果与已有最好算法的计算结果进行比较,比较结果表明：DHMVO比其他算法的求解精度更高、稳定性更强,非常适合高效求解大规模D{0-1}KP实例。     

求解折扣{0-1}背包问题的新遗传算法

折扣{0-1}背包问题（Discounted {0-1} Knapsack Problem,D{0-1}KP）是比0-1背包还要难以求解的NP-hard问题。提出了一种求解D{0-1}KP的新遗传算法GADKP。GADKP针对D{0-1}KP问题本身结构特征,借鉴启发式搜索思想设计了3种有效的交叉算子和1种变异算子。4种算子的操作都能够保证进化过程中解的可行性;3种交叉算子从3个不同的角度提高算法的搜索能力;变异算子采用逐层贪心机制提高个体的局部开发能力。通过4组共40个D{0-1}KP实例测试,和已有的求解D{0-1}KP的遗传算法相比,GADKP求解精度更高,是一种新颖有效的求解D{0-1}KP的方法。