折扣{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)易陷入局部最优解,同时存在大量无效交叉变异操作使得算法收敛较慢等问题,本文基于精英保存策略(EGA)和贪心修复算法(GROA),将核算法与遗传算法进行融合,提出求解D{0-1}KP的核加速遗传算法(CEGA)。将CEGA用于求解四类大规模D{0-1}KP实例,结果表明:CEGA适用于求解D{0-1}KP,且精确度和收敛速度均好于第一遗传算法(FirEGA)。

扩展SD{0-1}KP背包问题的建模及其遗传算法求解

在SD{0-1}KP的基础上对项集中的物品数由两个扩展为三个,提出扩展SD{0-1}KP问题。在扩展问题中,各项集中物品组合选择情况采取三元组进行编码表示,建立扩展SD{0-1}KP模型,再将贪心策略与遗传算法融合构造求解模型的算法。为验证算法的求解效果,随机生成四种扩展SD{0-1}KP大规模数据实例。求解结果表明:该算法适合求解扩展SD{0-1}KP大规模数据,且效果较好。