计算机应用

作者：杨洋, 潘大志, 刘益, 谭代伦

单位：西华师范大学 数学与信息学院, 四川 南充 637009

关键词：简化折扣{0-1}背包问题,贪婪策略,近似计算,数学模型,遗传算法

基金：国家自然科学基金资助项目（11371015）；四川省教育厅自然科学基金资助项目（18ZA0469）；西华师范大学博士启动基金资助项目（12B022）；西华师范大学校级科研团队项目（CXTD2015-4）；四川省大学生创新创业训练计划支持项目（201810638085）。

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

来源：2019年第3期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第3期