基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题  

Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem

作　　者：刘雪静 贺毅朝 路凤佳 吴聪聪 才秀凤 UU Xuejing;HE Yichao;LU Fengjia;WU Congcong;CAI Xiufeng(College of Information Engineering,Hebei GEO University,Shijiazhuang Hebei 050031,China)

机构地区：[1]河北地质大学信息工程学院,石家庄050031

出　　处：《计算机应用》2018年第1期137-145,181,共10页journal of Computer Applications

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

摘　　要：针对确定性算法难于求解的各项的重量系数和价值系数在大范围内取值的折扣{0-1}背包问题(D{0-1}KP),提出了基于差分演化策略的混沌乌鸦算法(DECCSA)。首先,采用混沌映射生成初始乌鸦种群;然后,采用混合编码方式和贪心修复与优化策略(GROS)解决了D{0-1}KP的编码问题;最后,引入差分演化策略提高算法的收敛速度。对4类大规模D{0-1}KP实例的计算结果表明:DECCSA比遗传算法、细菌觅食算法和变异蝙蝠算法求得的最好值和平均值更优,能得到最优解或更好的近似解,非常适于求解D{0-1}KP。In Discount{0-1}Knapsack Problem(D{0-1}KP),the weight coefficients and the value coefficients in a large range,are difficult to solve by deterministic algorithms.To solve this problem,a Chaotic Crow Search Algorithm based on Differential Evolution strategy(DECCSA)was proposed.Firstly,the initial crow population was generated by chaotic mapping.Secondly,mixed coding and Greedy Repair and Optimization Strategy(GROS)were used to solve the coding problem of D{0-1}KP.Finally,Difference Evolution(DE)strategy was introduced to improve the convergence rate of the algorithm.The experimental results on four large-scale D{0-1}KP instances show that DECCSA is better than Genetic Algorithm(GA),bacterial foraging optimization algorithm,and mutated bat algorithm,and it can get the optimal solution or approximate optimal solution.It's very suitable for solving D{0-1}KP.

关 键 词：乌鸦算法 折扣{0-1}背包问题 混沌 贪心修复与优化策略 差分演化策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]