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

• 作者: 刘益 杨洋 潘大志 谭代伦
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 简化折扣{0-1}背包问题 贪婪策略 近似计算 数学模型 遗传算法
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 人工智能
• 页码范围: 656-662
• 页数: 7页
• 分类号: TP18
• 字数: 9735字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2018071580

摘要

当前折扣{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算法首次引入罚函数法,有效地丰富了该问题的求解算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘大志	西华师范大学数学与信息学院	50	194	9.0	11.0
2	谭代伦	西华师范大学数学与信息学院	17	35	3.0	5.0
3	刘益	西华师范大学数学与信息学院	9	13	2.0	3.0
4	杨洋	西华师范大学数学与信息学院	19	32	4.0	5.0