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

Adaptive bacterial foraging optimization algorithm for discounted {0-1} knapsack problem

作　　者：刘雪静 贺毅朝 吴聪聪 李靓 LIU Xuejing;HE Yichao;WU Congcong;LI Liang(College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China;Hebei Post Information Technology Bureau,China Post Group Corporation,Shijiazhuang 050011,China)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]中国邮政集团公司河北省邮政信息技术局,石家庄050011

出　　处：《计算机工程与应用》2018年第18期139-146,270,共9页Computer Engineering and Applications

基　　金：河北省高等学校科学研究计划项目(No.ZD2016005);河北省自然科学基金(No.F2016403055)

摘　　要：针对确定性算法难以求解的大规模折扣{0-1}背包问题(D{0-1}KP),提出了自适应细菌觅食算法(ABFO)求解D{0-1}KP的两种算法。首先,给出了D{0-1}KP的两种数学模型;然后,针对细菌觅食算法的趋化操作提出了自适应趋化策略;最后,利用两种贪心修复与优化策略处理两种数学模型中的不可行解,得到求解D{0-1}KP的Fir ABFO和Sec ABFO算法。仿真实验表明,Fir ABFO和Sec ABFO均能得到最优解或近似比几乎等于1的近似解,非常适于求解D{0-1}KP,并且Sec ABFO的求解性能比Fir ABFO更优。For the large-scale Discount{0-1}Knapsack Problem(D{0-1}KP)which is difficult to be solved by deterministic algorithm,two algorithms based on Adaptive Bacterial Foraging Optimization(ABFO)are proposed.Firstly,two mathematical models of D{0-1}KP are given.Secondly,the adaptive chemotaxis strategy is proposed.Thirdly,two greedy repair and optimization strategies are used to deal with non-normal solutions,and FirABFO and SecABFO are proposed.The simulation results show that both FirABFO and SecABFO are very suitable for solving large-scale D{0-1}KP instances,they can get best solution or approximate solution with approximate ratio almost closing to 1,and SecABFO has better solution performance than FirABFO.

关 键 词：折扣{0-1}背包问题 细菌觅食算法 自适应 贪心修复与优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]