电子学报 ›› 2018, Vol. 46 ›› Issue (6): 1343-1350.DOI: 10.3969/j.issn.0372-2112.2018.06.010

• 学术论文 • 上一篇    下一篇

差分进化帝王蝶优化算法求解折扣{0-1}背包问题

冯艳红1, 杨娟2, 贺毅朝1, 王改革3   

  1. 1. 河北地质大学信息工程学院, 河北石家庄 050031;
    2. 凯理学院数学科学学院, 贵州凯里 556011;
    3. 中国海洋大学信息科学与工程学院, 山东青岛 266100
  • 收稿日期:2017-01-17 修回日期:2017-07-03 出版日期:2018-06-25
    • 通讯作者:
    • 王改革
    • 作者简介:
    • 冯艳红,女,1978年生,河北卢龙人,河北地质大学信息工程学院副教授,研究方向:进化计算、群体智能及机器学习.E-mail:qinfyh@163.com;杨娟,女,1982年生,湖南邵阳人,凯里学院数学科学学院副教授,研究方向:数学物理方程、近似算法.E-mail:hnyangjuan1982@126.com;贺毅朝,男,1969年生,河北晋州人,硕士,教授,计算机学会(CCF)高级会员,研究方向为进化算法理论与应用、算法设计与分析、计算复杂性理论和Group Testing理论.E-mail:heyichao119@163.com
    • 基金资助:
    • 江苏省自然科学基金 (No.BK20150239); 国家自然科学基金 (No.61503165,No.61402207,No.61673196)

Monarch Butterfly Optimization Algorithm with Differential Evolution for the Discounted {0-1} Knapsack Problem

FENG Yan-hong1, YANG Juan2, HE Yi-chao1, WANG Gai-ge3   

  1. 1. School of Information Engineering, Hebei GEO University, Shijiazhuang, Hebei 050031, China;
    2. School of Mathematical Science, Kaili University, Kaili, Guizhou 556011, China;
    3. College of Information Science and Engineering, Ocean University of China, Qingdao, Shandong 266100, China
  • Received:2017-01-17 Revised:2017-07-03 Online:2018-06-25 Published:2018-06-25
    • Corresponding author:
    • WANG Gai-ge
    • Supported by:
    • National Natural Science Foundation of Jiangsu Province,  China (No.BK20150239); National Natural Science Foundation of China (No.61503165, No.61402207, No.61673196)

摘要: 帝王蝶优化算法(Monarch Butterfly Optimization,MBO)是一种新颖的群体智能算法,自从提出就在实际优化问题上表现出很好的性能.但是,帝王蝶优化算法的迁移算子采用随机选择两个个体来生成新个体,并没有记忆整个种群的最优解,容易造成全局最优帝王蝶搜索经验的丢失.根据MBO寻优过程的内在机制以及差分进化算法的变异算子能够利用个体间的差异信息,将MBO分别与目前性能最优、应用范围最广的7种差分进化(Differential Evolution,DE)变异策略相结合,实验验证了7种不同算法的性能.基于性能最优的DE/best/2/bin变异模式,提出了一种差分进化帝王蝶优化算法(Monarch Butterfly Optimization Algorithm with Differential Evolution,DEMBO),使得算法能够记忆种群最优解并实现种群内部信息的充分共享,达到既加快收敛速度又提高解的精度的目的.在30个典型折扣{0-1}背包问题(D{0-1}KP)实例上进行了一系列实验,实验结果表明:(1)DEMBO能够在时间复杂度不变的条件下,显著提高算法的求解精度和收敛速度;(2)DEMBO在求解所有D{0-1}KP实例时,均能够获得一个近似比非常接近1的近似解.

关键词: 折扣{0-1}背包问题, 差分进化, 帝王蝶优化算法, 贪心修复策略, 近似比

Abstract: Recently,inspired by the migratory behavior of monarch butterflies in nature,a swarm intelligence optimization algorithm,called monarch butterfly optimization algorithm (MBO),is proposed.Since MBO is proposed,it has good performances in various real-world optimization problems.However,migration operator of MBO selects randomly two individuals to generate new offspring,in which the useful search experience of global optimal individual is easily lost.Based on the intrinsic mechanism of the search process of MBO and the character of differential mutation operator,MBO is combined with 7 kinds of DE mutation strategies,respectively.Then a series of experiments are conducted to verify their performance.A DEMBO based on MBO and better differential evolution mutation strategy is presented,in which migration operator is replaced by differential mutation operator to enhance its global optimization ability.The over-all performance of DEMBO is verified and analyzed by 30 typical discounted {0-1} knapsack problem (D {0-1} KP) instances.The experimental results demonstrate that DEMBO can significantly improve the solution quality and convergence speed under the condition of not increasing the time complexity.Meanwhile,the approximation ratio of all the D {0-1} KP instances obtained by DEMBO is close to 1.0.

Key words: discounted {0-1} knapsack problem, differential evolution, monarch butterfly optimization algorithm, greedy repair strategy, approximate ratio

中图分类号: