离散灰狼优化算法求解有界背包问题
详细信息    查看全文 | 推荐本文 |
  • 英文篇名:Discrete grey wolf optimizer for bounded knapsack problem
  • 作者:贺毅朝 ; 李泽文 ; 李焕哲 ; 郭晓虎 ; 李亚
  • 英文作者:HE Yi-chao;LI Ze-wen;LI Huan-zhe;GUO Xiao-hu;LI Ya;College of Information Engineering,Hebei GEO University;
  • 关键词:有界背包问题 ; 灰狼优化算法 ; 遗传算法 ; 编码转换法 ; 修复与优化法
  • 英文关键词:bounded knapsack problem;;grey wolf optimizer;;genetic algorithm;;encoding transformation method;;repair and optimization method
  • 中文刊名:SJSJ
  • 英文刊名:Computer Engineering and Design
  • 机构:河北地质大学信息工程学院;
  • 出版日期:2019-04-16
  • 出版单位:计算机工程与设计
  • 年:2019
  • 期:v.40;No.388
  • 基金:河北省高等学校科学研究计划基金项目(ZD2016005);; 河北省自然科学基金项目(F2016403055)
  • 语种:中文;
  • 页:SJSJ201904018
  • 页数:8
  • CN:04
  • ISSN:11-1775/TP
  • 分类号:115-122
摘要
为利用灰狼优化算法求解有界背包问题,基于编码转换法提出一种离散灰狼优化算法(discrete grey wolf optimizer,DGWO)。引入遗传算法的交叉策略增强局部搜索能力,使用基于贪心策略的修复与优化法处理不可行解,保证算法的求解效果,加快算法的收敛速度。对于3类大规模有界背包问题实例,通过与已有算法的计算结果比较与分析,验证了DGWO的有效性和稳定性。实验结果表明,DGWO的收敛速度比其它算法快,对于所有的有界背包问题实例均能获得一个近似比接近1的近似解。
        To solve the bounded knapsack problem using the grey wolf optimizer,a discrete grey wolf optimizer(DGWO)based on encoding transformation was proposed.A crossover strategy of genetic algorithm was introduced to enhance the local search ability,and the infeasible solutions were processed using the repair and optimization method based on the greedy strategy,which not only ensured the effectiveness,but also speeded up the convergence.Experiment using three kinds of large-scale instances of the bounded knapsack problem was carried out to verify the validity and stability of DGWO.By comparing and analyzing the results with other well-established algorithms,the computational results show that the convergence speed of DGWO is higher than that of other algorithms,the solutions of these instances of bounded knapsack problem are all well obtained with approximation ratio close to 1.
引文
[1]WANG Xizhao, HE Yichao. Evolutionary algorithms for knapsack problems[J].Journal of Software,2017,28(1):1-16(in Chinese).[王熙照,贺毅朝.求解背包问题的演化算法[J].软件学报,2017,28(1):1-16.]
    [2]Sbihi A.Adaptive perturbed neighbourhood search for the expanding capacity multiple-choice knapsack problem[J].Journal of the Operational Research Society,2013,64(10):1461-1473.
    [3]He Yichao,Wang Xizhao.Group theory-based optimization algorithm for solving knapsack problems[J].Knowledge-Based Systems,2018.
    [4]Pisinger D.A minimal algorithm for the bounded knapsack problem[C]//Integer Programming and Combinatorial Optimization,International IPCO Conference,Copenhagen,Denmark,Proceedings.DBLP,2000:95-109.
    [5]Arabali A,Ghofrani M,Etezadi-Amoli M.Genetic-algorithmbased optimization approach for energy management[J].IEEE Transactions on Power Delivery,2013,28(1):162-170.
    [6]Couceiro M,Ghamisi P.Particle swarm optimization[M]//Fractional Order Darwinian Particle Swarm Optimization.Springer International Publishing,2016:149-150.
    [7]Das S,Mullick SS,Suganthan PN.Recent advances in differential evolution-an updated survey[J].Swarm&Evolutionary Computation,2016,27(6):1-30.
    [8]Mirjalili S.SCA:A sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems,2016,96(15):120-133.
    [9]Mirjalili S,Lewis A.The whale optimization algorithm[J].Advances in Engineering Software,2016,95(5):51-67.
    [10]Mirjalili S,Mirjalili SM,Lewis A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69(3):46-61.
    [11]HE Yichao, WANG Xizhao,ZHAO Shuliang,et al.The design and applications of discrete evolutionary algorithm based on encoding transformation[J].Journal of Software,2018,29(9):2580-2594(in Chinese).[贺毅朝,王熙照,赵书良,等.基于编码转换的离散演化算法设计与应用[J].软件学报,2018,29(9):2580-2594.]
    [12]Masadeh R,Yassien E,Alzaqebah A,et al.Grey wolf optimization applied to the 0/1knapsack problem[J].International Journal of Computer Applications,2017,169(5):11-15.
    [13]Sharma S,Salgotra R,Singh U.An enhanced grey wolf optimizer for numerical optimization[C]//International Conference on Innovations in Information,Embedded and Communication Systems,2017:1-6.
    [14]Mirjalili S.How effective is the grey wolf optimizer in training multi-layer perceptrons[J].Applied Intelligence,2015,43(1):150-161.
    [15]Hatta NM,Zain AM,Sallehuddin R,et al.Recent studies on optimisation method of grey wolf optimiser(GWO):A review(2014-2017)[J].Artificial Intelligence Review,2018:1-33.
    [16]Emary E,Zawbaa HM,Hassanien AE.Binary grey wolf optimization approaches for feature selection[J].Neurocomputing,2016,172(C):371-381.
    [17]HE Yichao,WANG Xizhao,LI Wenbin,et al.Exact algorithms and evolutionary algorithms for randomized time-varying knapsack problem[J].Journal of Software,2017,28(2):185-202(in Chinese).[贺毅朝,王熙照,李文斌,等.求解随机时变背包问题的精确算法与进化算法[J].软件学报,2017,28(2):185-202.]
    [18]HE Yichao,SONG Jianmin,ZHANG Jingmin,et al.Research on genetic algorithm for solving static and dynamic knapsack problems[J].Application Research of Computers,2015,32(4):1011-1015(in Chinese).[贺毅朝,宋建民,张敬敏,等.利用遗传算法求解静态与动态背包问题的研究[J].计算机应用研究,2015,32(4):1011-1015.]
    [19]HE Yichao,WANG Xizhao,LI Wenbin,et al.Research on genetic algorithms for the discounted{0-1}knapsack problem[J].Chinese Journal of Computers,2016,39(12):2614-2630(in Chinese).[贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.]
    [20]Byrka J,Li S,Rybicki B.Improved approximation algorithm for k-level uncapacitated facility location problem(with penalties)[M].Springer-Verlag New York,Inc,2016.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700