积分商城

最新搜索： ispLEVER ESAM sonar NE555.PDF BRIGHTEK 电解电容封装库
您现在的位置是：首页 > 技术资料 > 差分进化帝王蝶优化算法求解折扣{0-1}背包问题
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

更新时间：2019-12-24 01:34:05 大小：1M 上传用户：守着阳光1985查看TA发布的资源 标签：背包问题 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

帝王蝶优化算法(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}背包问题.pdf 1M

【关注视频号领20积分】   【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
6
Vol． 46 No． 6  
Jun． 2018  
第
期
电
子
学
报
2018  
6
ACTA ELECTRONICA SINICA  
年
月
差分进化帝王蝶优化算法求解  
{ 0-1}  
折扣  
背包问题  
1
2
1
3
， ， ，  
冯艳红 杨 娟 贺毅朝 王改革  
( 1．  
，
河北地质大学信息工程学院 河北石家庄  
050031; 2．  
，
凯理学院数学科学学院 贵州凯里  
556011;  
3．  
，
中国海洋大学信息科学与工程学院 山东青岛  
266100)  
:
( 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}  
:
;
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
折扣  
背包问题 差分进化 帝王蝶优化算法 贪心修复策略 近似比  
0372-2112 ( 2018) 06-1343-08  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 06． 010  
:
TP18  
:
A
:
文章编号  
文献标识码  
电子学报  
Monarch Butterfly Optimization Algorithm with Differential  
Evolution for the Discounted { 0-1} Knapsack Problem  
1
2
1
3
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)  
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．  
Key words: discounted { 0-1} knapsack problem; differential evolution; monarch butterfly optimization algorithm;  
greedy repair strategy; approximate ratio  
: 2017-01-17;  
: 2017-07-03;  
:
责任编辑 梅志强  
收稿日期  
修回日期  
:
基金项目 江苏省自然科学基金  
( No． BK20150239) ;  
( No． 61503165，No． 61402207，No． 61673196)  
国家自然科学基金  
1344  
2018  
年
电
子
学
报
、
决策 项目安排和预算控制等诸多领域都有实际应用  
．
1
引言  
D{ 0-1} KP  
: n  
问题的简单形象描述是 给定 个项目  
( Monarch Butterfly Optimization，MBO)  
(
) ，  
物品 组 任意一个项目组  
i( 0 i n － 1)  
≤ ≤  
帝王蝶优化  
均包含三个  
， 3i  
［1］  
算法 是王改革等人提出的一种较为新颖的群体智能  
3i，3i + 1 3i + 2  
编号分别为 以及  
的价值系数分别为  
的物品 其中物品  
和
，
算法 不同于基于生物群体的其他群体智能优化方法  
，
3i + 1  
p
p
，
重量系数分别  
物品  
和
3i  
3i + 1  
MBO  
模拟的是自然界中帝王蝶随着季节变化进行迁徙  
w
w
，
3i + 2  
为
和
物品  
被认为是前两个物品结对组  
＜ w + w  
3i  
3i + 1  
［2，3］  
．
的行为 已有的相关研究工作  
，MBO  
在求解数  
指出  
，
合而成 拥有折扣重量  
w
，
不变的总价值  
3i + 2  
3i  
3i + 1  
，
值优化问题时 寻优性能与差分进化  
( Differential Evolu-  
p
= p + p ． w ＜ w ，w  
同时  
3i + 2  
＜ w  
，
对于每一  
3i + 2  
3i  
3i + 1  
3i  
3i + 1  
3i + 2  
［4，5］  
tion，DE)  
．
等算法相比有一定的竞争力 目前  
，MBO  
i( 0  
i
≤ ≤  
n － 1) ，  
物品  
3i，3i + 1  
3i + 2  
以及 至  
个项目组  
及其改进形式已被应用到了一些实际优化问题求解  
C ．  
多允许有一个物品被装入最大载重为 的背包 问题  
［1］  
［2］  
， 0-1  
中 如  
、
．
等
背包问题  
神经网络的训练  
3n  
，
个物品的一部分去填充背包 在物品总重量不  
是用  
{ 0-1}  
( Discounted { 0-1} Knapsack  
折扣  
背包问题  
C
超过 的前提下使装入背包中的物品价值之和最大  
．
［6，7］  
Problem，D{ 0-1} KP)  
Guldan B  
首先提  
最早由学者  
D{ 0-1} KP  
:
的第一数学模型为  
则
n－1  
， ;  
出 并给出了求解该问题的动态规划法 之后  
，Aiying  
max f( X) = max  
( x p +x  
3i 3i  
p
3i + 1 3i + 1  
+x  
p
3i + 2 3i + 2  
) ( 1)  
［8］  
∑
Rong  
D{ 0-1} KP  
( Core)  
的核 问题进行研究并  
等人对  
i = 0  
［9］  
s． t． x + x  
3i  
+ x  
1，  
≤
i ［0，n － 1］ ( 2)  
 ∈  
;
结合动态规划法对问题求解 最近贺毅朝 等人建立  
3i + 1  
3i + 2  
n－1  
D{ 0-1} KP  
，
的两个新的数学模型 并给出两种基于遗  
了
( x w + x  
3i 3i  
w
3i + 1 3i + 1  
+ x  
w
3i + 2 3i + 2  
)
C
( 3)  
≤
∑
(
传算法对该问题求解的可行有效方法 简记为  
FirEGA  
i = 0  
［11］  
x ，x ，x  
3i + 1  
{ 0，1} ，  
i ［0，n － 1］ ( 4)  
 ∈  
∈
3i + 2  
3i  
SecEGA) ;  
，
此外 贺毅朝 等人对确切性算法和近似  
和
，
其中 二元决策变量  
x ( 0  
j
j
≤ ≤  
3n － 1) j  
表示物品 是否  
D{ 0-1} KP  
，
问题的性能进行比较 提出了一种  
算法求解  
PSO  
．
被装入背包 如果  
x = 0，  
j
j ;  
说明物品 未被装入背包 否  
．
二进制  
本文从  
( Migration Operator，MO)  
算法求解该问题的新思路  
， j ．  
则 表示物品 被装入背包 显然  
，D{ 0-1} KP  
问题是包  
MBO  
，
寻优过程的内在机制出发 注意到迁  
PSO  
算
n + 1 、 0-1 KP  
个不等式约束 比经典  
含
更为复杂的组合  
徙算子  
法中的社会信息对于位置更新的贡献 此外 子种群  
中变异个体的生成仅仅考虑了父代种群中的一个个  
并未体现出如  
．
优化问题  
．
，
1
3
帝王蝶优化算法的基本原理  
，
体 忽略了全局最优个体对种群搜索方向的引导作用  
，
，
在标准帝王蝶优化算法中 假设目标问题对应一  
．
同时不利于种群多样性的保持 大量实验结果表明  
，DE  
d
， N  
维的解空间 随机初始化 个帝王蝶个体  
P =  
个
DE  
，
算法中最关键的步骤 高度影响  
算法的变异操作是  
DE  
( X ，X ，…，X )  
，
i
分布在此解空间 第 个个体在解空间  
N
1
2
．
DE  
算法的性能 目前性能最优且应用最广的  
变异  
DE /cur-  
和
d
的位置可以 表 示 为 一 个 维 向 量  
X = ( x ，x ，…，  
i2  
i
i1  
DE/best /k，DE/current-to-rand /k  
策略包 括  
rent-to-best /k ( k = 1，2) ．  
T
x ) ， ，  
显然 每一个个体的位置都对应着目标问题的一  
id  
，
MBO  
等
因此 本文将  
算法分别  
种典型差分变异策略结合 形成 种不同的混合  
MBO  
． ，  
个潜在解 此外 帝王蝶优化算法按照适应度值将整个  
7
，
7
与
P
种群 分为子种群  
SP1( N1 ) SP2( N2  
个个体 和子种群  
，
与差分变异的新算法 并通过实验验证了不同算  
) ，  
个个体 迁移算子  
( Migration Operator，MO)  
和蝴蝶调  
，
法的性能 寻找到  
MBO  
与最优变异策略结合的新算  
( Butterfly Adjusting Operator，BAO)  
整算子  
两个子种群  
在迁移算子中 先产生一个随机数  
分别作用于  
， :  
法 即 差分进化帝王蝶优化算法  
( Monarch Butterfly Op-  
．
timization with Differential Evolution，DEMBO) ，  
新算法不  
，
r = rand* peri，  
，
仅记忆种群最优解并实现种群内部信息的充分共享  
p，  
并且给出参数 则产生新个体的公式为  
:
、 ．  
而且加快收敛速度 避免算法陷入局部最优 为验证  
t + 1  
t
x
= x  
( 5)  
DEMBO ， D{ 0-1} KP  
算法的有效性 利用三类大规模  
i，k  
j，k  
实
［6，8，9］  
，i = 1，2 ，…，N1; k = 1，2，…d; t  
;
为当前进化代数  
其中  
(
UDKP，WDKP  
SDKP)  
和 进行一系  
例
分别简记为  
rand ［0，1］  
是 区间服从均匀分布的随机数  
; peri  
代表迁  
． ， DEMBO  
列实验 实验结果表明 本文提出的 算法在求  
; p 1 ． r p，j  
移周期 表示子种群 中帝王蝶所占比例 如果 ≤  
D{ 0-1} KP  
．
问题上表现出良好的性能  
解
1 ， ，  
是在子种群 中随机选择的一个个体 否则 个体  
j
随
2
D{ 0-1} KP  
的第一数学模型  
2．  
机选择于子种群  
［6，8］  
D{ 0-1} KP  
“
的提出源于商业领域中的 打  
， rand p， 2  
在蝴蝶调整算子中 若 ≤ 则子种群 中个体  
问题  
” ． ，  
折 思想 该问题具有较高的理论和实际价值 在投资  
:
按如下公式更新  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号