推荐星级:
  • 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

部分页面预览

(完整内容请下载后查看)
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 OptimizationMBO) ,  
法 自提出优  
法  
, ,  
的性能 但是 法的个个体来个体 个  
.  
优解 全局经验失 根据  
MBO  
程的内在制以及差分进法的算  
MBO  
子能用个体间的差信息 将  
7 ( Differential EvolutionDE)  
性能应用广差分进化  
7 .  
略相实验验证了 种不法的性能 基性能优的  
DE/best/2 /bin  
式 提出了一差分进帝  
( Monarch Butterfly Optimization Algorithm with Differential EvolutionDEMBO) ,  
使法能够记最  
法  
.  
优解并实内部信息的达到敛速解的精度的目的 在  
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 EngineeringHebei GEO UniversityShijiazhuangHebei 050031China;  
2. School of Mathematical ScienceKaili UniversityKailiGuizhou 556011China;  
3. College of Information Science and EngineeringOcean University of ChinaQingdaoShandong 266100China)  
Abstract: Recentlyinspired by the migratory behavior of monarch butterflies in naturea swarm intelligence optimi-  
zation algorithmcalled monarch butterfly optimization algorithm ( MBO) is proposed. Since MBO is proposedit has good  
performances in various real-world optimization problems. Howevermigration operator of MBO selects randomly two indi-  
viduals to generate new offspringin 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 operatorMBO is combined  
with 7 kinds of DE mutation strategiesrespectively. Then a series of experiments are conducted to verify their performance.  
A DEMBO based on MBO and better differential evolution mutation strategy is presentedin 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. Meanwhilethe 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. 61503165No. 61402207No. 61673196)  
国家自然科学基金  
1344  
2018  
项目领域有实际应用  
1
引言  
D{ 0-1} KP  
: n  
题的象描述是 项目  
( Monarch Butterfly OptimizationMBO)  
(
) ,  
项目组  
i( 0 i n - 1)  
≤ ≤  
化  
均包含个  
3i  
1]  
提出能  
3i3i + 1 3i + 2  
为 以及  
系数分为  
品  
能优方法  
3i + 1  
p
p
系数分别  
品  
3i  
3i + 1  
MBO  
自然随着迁徙  
w
w
3i + 2  
品  
组  
w + w  
3i  
3i + 1  
23]  
行为 已有研究工作  
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  
45]  
tionDE)  
有一定的前  
MBO  
i( 0  
i
≤ ≤  
n - 1) ,  
品  
3i3i + 1  
3i + 2  
至  
项目组  
改进了一解  
C .  
有一题  
1]  
2]  
0-1  
如  
题  
网络训练  
3n  
部分填充不  
是用  
{ 0-1}  
( Discounted { 0-1} Knapsack  
扣  
题  
C
使中的和最大  
67]  
ProblemD{ 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 0n - 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  
{ 01} ,  
i 0n - 1( 4)  
 ∈  
3i + 2  
3i  
SecEGA) ;  
此外 似  
量  
x ( 0  
j
j
≤ ≤  
3n 1) j  
否  
D{ 0-1} KP  
题的性能进提出了一种  
解  
PSO  
果  
x = 0,  
j
j ;  
否  
制  
从  
( Migration OperatorMO)  
该问题的新路  
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 /kDE/current-to-rand /k  
括  
rent-to-best /k ( k = 12) .  
T
x ) , ,  
个个体的位标问题的一  
id  
MBO  
因此 将  
法分别  
差分种不同的合  
MBO  
,  
在解 此外 度值个  
7
7
P
群  
SP1( N1 ) SP2( N2  
个个体 群  
差分的新实验验证了算  
) ,  
个个体 子  
( Migration OperatorMO)  
调  
法的性能 到  
MBO  
算  
( Butterfly Adjusting OperatorBAO)  
子  
群  
子中 产生数  
于  
, :  
差分进法  
( Monarch Butterfly Op-  
timization with Differential EvolutionDEMBO) ,  
不  
r = rand* peri,  
仅记优解并实内部信息的享  
p,  
并且给出参产生个体式为  
:
.  
且加验证  
t + 1  
t
x
= x  
( 5)  
DEMBO D{ 0-1} KP  
法的有效三类模  
ik  
jk  
689]  
i = 12 N1; k = 12d; t  
;
数  
中  
(
UDKPWDKP  
SDKP)  
行一系  
为  
rand 01]  
服从数  
; peri  
代表迁  
DEMBO  
实验 实验明 本文提出法在求  
; p 1 . r pj  
≤  
D{ 0-1} KP  
的性能  
1 , ,  
在子个个体 个体  
j
2
D{ 0-1} KP  
数学模型  
2.  
群  
68]  
D{ 0-1} KP  
提出源于领域中的 打  
rand p2  
蝴蝶调整子中 个体  
题  
,  
该问较高理论和实投资  
:
式更新  

全部评论(0)

暂无评论

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

  • 打赏
  • 30日榜单

推荐下载