摘要
折扣{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的近似解。
The Discounted{0-1}Knapsack Problem(D{0-1}KP)is an extension of the classical 0-1 Knapsack Problem(0-1 KP).In this paper,it uses Bacterial Foraging Optimization algorithm(BFO)to solve D{0-1}KP,Firstly,the two mathematical models of the D{0-1}KP are described,and then BFO is combined with the two mathematical models,the bacterial individual uses the binary vector and the four binary vector coding method,and the greedy strategy is used to optimize the initial solution and repair the non normal coding individuals,Fir BFO and Sec BFO algorithms for solving D{0-1}KP are given.The calculations of four instances show that,Fir BFO and Sec BFO are suitable for solving large scale hard D{0-1}KP.And they can also obtain the approximate solution whose approximation rate is almost equal to 1.
作者
刘雪静
贺毅朝
吴聪聪
才秀凤
LIU Xuejing;HE Yichao;WU Congcong;CAI Xiufeng(College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China)
出处
《计算机工程与应用》
CSCD
北大核心
2018年第2期155-162,共8页
Computer Engineering and Applications
基金
河北省高等学校科学研究计划项目(No.ZD2016005)
河北省自然科学基金(No.F2016403055)
关键词
折扣{0-1}背包问题
细菌觅食算法
贪心策略
修复与优化
discounted{0-1}knapsack problem
bacterial foraging optimization algorithm
greedy strategy
repair and optimization
