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

doi:10.3969/j.issn.0372-2112.2018.06.010

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

差分进化帝王蝶优化算法求解折扣{0-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-hong¹, YANG Juan², HE Yi-chao¹, WANG Gai-ge³

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)

摘要/Abstract

摘要： 帝王蝶优化算法（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

中图分类号:

TP18

冯艳红, 杨娟, 贺毅朝, 等. 差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J]. 电子学报, 2018, 46(6): 1343-1350.

FENG Yan-hong, YANG Juan, HE Yi-chao, et al. Monarch Butterfly Optimization Algorithm with Differential Evolution for the Discounted {0-1} Knapsack Problem[J]. Acta Electronica Sinica, 2018, 46(6): 1343-1350.

参考文献

[1] Feng Y,Wang G G,Deb S,et al.Solving 0-1 knapsack problem by a novel binary monarch butterfly optimization[J].Neural Computing & Applications,2017,28(7):1619-1634.
[2] Faris H,Aljarah I,Mirjalili S.Improved monarch butterfly optimization for unconstrained global search and neural network training[J].Applied Intelligence,2018,48(2):445-464.
[3] Chen S,Chen R,Gao J.A monarch butterfly optimization for the dynamic vehicle routing problem[J].Algorithms,2017,10(3):107.
[4] 刘会超,吴志健.基于旋转学习机制的差分演化算法[J].电子学报,2015,43(10):2040-2046. Wu Hui-chao,Wu zhi-jian.Differential evolution algorithm using rotation-based learning[J].Acta Electronica Sinica,2015,43(10):2040-2046.(in Chinese)
[5] 閤大海,李元香,龚文引,等.一种求解约束优化问题的自适应差分进化算法[J].电子学报,2016,44(10):2535-2542. Xia Da-hai,Li Yuan-xiang,Gong Wen-yin,et al.An adaptive differential evolution algorithm for constrained optimization problems[J].Acta Electronica Sinica,2016,44(10):2535-2542.(in Chinese)
[6] Zhu H,He Y,Wang X,et al.Discrete differential evolutions for the discounted {0-1} knapsack problem[J].International Journal of Bio-inspired Computation,2017,10(4):219-238
[7] Guldan B.Heuristic and Exact Algorithms for Discounted Knapsack Problems[D].Bavaria,Germany:University of Erlangen-Nürnberg,2007.
[8] Rong A,Figueira J R,Klamroth K.Dynamic programming based algorithms for the discounted {0-1} knapsack problem[J].Applied Mathematics & Computation,2012,218(12):6921-6933.
[9] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12). He Yi-chao,Wang Xi-zhao,Li wen-bin,et al.Research on genetic algorithms for the discounted {0-1} knapsack problem[J].Chinese Journal of Computers,2016,39(12).(in Chinese)
[10] He YC,Wang XZ,He YL,et al.Exact and approximate algorithms for discounted {0-1} knapsack problem[J].Information Sciences,2016,369:634-647.
[11] 魏文红,周建龙,陶铭,等.一种基于反向学习的约束差分进化算法[J].电子学报,2016,44(2):426-436. Wei Wen-hong,Zhou Jian-long,Tao Ming,et al.Constrained differential evolution using opposition-based learning[J].Acta Electronica Sinica,2016,44(2):426-436.(in Chinese)
[12] 贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法[J].计算机研究与发展,2007,44(9):1476-1484. He Y C,Wang X Z,Kou Y Z.A binary differential evolution algorithm with hybrid encoding[J].Journal of Computer Research and Development,2007,44(9):1476-1484.(in Chinese)

[1]	胡向东, 吕高飞, 白银. 基于优化支持向量回归的工业互联网安全态势预测方法[J]. 电子学报, 2023, 51(2): 446-454.
[2]	龙文, 蔡绍洪, 焦建军, 伍铁斌. 一种改进的灰狼优化算法[J]. 电子学报, 2019, 47(1): 169-175.
[3]	程兰, 邢艳君, 任密蜂, 谢刚, 陈杰. 基于ε等级约束差分进化的多径估计算法[J]. 电子学报, 2018, 46(1): 167-174.
[4]	谢欢欢, 景跃骐, 李艳. 0-1规划的稀布同心圆阵方法研究[J]. 电子学报, 2018, 46(1): 61-67.
[5]	王亚辉, 吴金妹, 贾晨辉. 基于动态种群多策略差分进化模型的多目标进化算法[J]. 电子学报, 2016, 44(6): 1472-1480.
[6]	王福才, 周鲁苹. 混合精英策略的元胞多目标遗传算法及其应用[J]. 电子学报, 2016, 44(3): 709-717.
[7]	魏文红, 周建龙, 陶铭, 袁华强. 一种基于反向学习的约束差分进化算法[J]. 电子学报, 2016, 44(2): 426-436.
[8]	閤大海, 李元香, 龚文引, 何国良. 一种求解约束优化问题的自适应差分进化算法[J]. 电子学报, 2016, 44(10): 2535-2542.
[9]	朱大林, 詹腾, 张屹, 郑小东. 多策略差分进化的元胞多目标粒子群算法[J]. 电子学报, 2014, 42(9): 1831-1838.
[10]	彭虎, 吴志健, 周新宇, 邓长寿. 基于精英区域学习的动态差分进化算法[J]. 电子学报, 2014, 42(8): 1522-1530.
[11]	黄江华, 李彬, 王涛. 基于解空间收缩的差分进化算法的CLAD序列优化[J]. 电子学报, 2014, 42(8): 1571-1576.
[12]	高卫峰, 刘三阳, 黄玲玲. 受启发的人工蜂群算法在全局优化问题中的应用[J]. 电子学报, 2012, 40(12): 2396-2403.
[13]	时正;纪金松;陈香兰;龚育昌. 一种基于差分进化的Flash文件系统垃圾回收算法[J]. 电子学报, 2011, 39(2): 280-284.
[14]	张雪霞;陈维荣;戴朝华. 带局部搜索的动态多群体自适应差分进化算法及函数优化[J]. 电子学报, 2010, 38(8): 1825-1830.
[15]	张晓伟;刘三阳. 免比例因子F的差分进化算法[J]. 电子学报, 2009, 37(6): 1318-1323.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics