电子学报2018，Vol.46Issue(6)：1343-1350,8.DOI:10.3969/j.issn.0372-2112.2018.06.010
差分进化帝王蝶优化算法求解折扣{0-1}背包问题
Monarch Butterfly Optimization Algorithm with Differential Evolution for the Discounted {0-1} Knapsack Problem
摘要
Abstract
Recently,inspired by the migratory behavior of monarch butterflies in nature,a swarm intelligence optimi-zation 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 indi-viduals 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 re-placed 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 in-creasing the time complexity. Meanwhile,the approximation ratio of all the D {0-1} KP instances obtained by DEMBO is close to 1.0.关键词
折扣{0-1}背包问题/差分进化/帝王蝶优化算法/贪心修复策略/近似比Key words
discounted {0-1} knapsack problem/differential evolution/monarch butterfly optimization algorithm/greedy repair strategy/approximate ratio分类
信息技术与安全科学引用本文复制引用
冯艳红,杨娟,贺毅朝,王改革..差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J].电子学报,2018,46(6):1343-1350,8.基金项目
江苏省自然科学基金(No.BK20150239) （No.BK20150239）
国家自然科学基金(No.61503165,No.61402207,No.61673196) （No.61503165,No.61402207,No.61673196）
