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

doi:10.3969/j.issn.0372-2112.2018.06.010

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-08

- Monarch Butterfly Optimization Algorithm with Differential Evolution for the Discounted {0-1} Knapsack Problem
- Acta Electronica Sinica Vol. 46, Issue 6, Pages: 1343-1350(2018)
- 作者机构：
  
  1. 河北地质大学信息工程学院,河北,石家庄,050031
  2. 凯理学院数学科学学院,贵州,凯里,556011
  3. 中国海洋大学信息科学与工程学院,山东,青岛,266100
  4. 河北地质大学信息工程学院,河北,石家庄,050031
  5. 凯理学院数学科学学院,贵州,凯里,556011
  6. 中国海洋大学信息科学与工程学院,山东,青岛,266100
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2018.06.010
  CLC： TP18
- Published Online：25 June 2018，
  
  Published：2018
- 稿件说明：
移动端阅览
Monarch Butterfly Optimization Algorithm with Differential Evolution for the Discounted {0-1} Knapsack Problem[J]. Acta Electronica Sinica, 2018, 46(6): 1343-1350.
DOI：

Monarch Butterfly Optimization Algorithm with Differential Evolution for the Discounted {0-1} Knapsack Problem[J]. Acta Electronica Sinica, 2018, 46(6): 1343-1350. DOI： 10.3969/j.issn.0372-2112.2018.06.010.

摘要

帝王蝶优化算法（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的近似解.

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.

关键词

Keywords

references

Views

1153

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Dynamic Differential Evolution Algorithm Based on Elite Local Learning

Constrained Differential Evolution Using Opposition-Based Learning

An Improved Grey Wolf Optimization Algorithm

Adaptive Differential Evolution Algorithm Based on Elite Differential Feedback Strategy

Related Author

ZHOU Lu-ping

WANG Fu-cai

DENG Chang-shou

ZHOU Xin-yu

WU Zhi-jian

PENG Hu

WEI Wen-hong

YUAN Hua-qiang

Related Institution

Department of Information and Electrical Engineering, Ludong University

School of Information Science and Technology Jiujiang University Jiujiang Jiangxi China

Computer School Wuhan University Wuhan Hubei China

State Key Lab of Software Engineering Wuhan University Wuhan Hubei China

School of Information Science and Technology, Jiujiang University

⁰