一种新的求解多维背包问题的分散算法

为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避

第2 9卷第 5期21 0 2年 5月

计算机应用研究Ap l a in R s a c fC mp tr p i to e e r h o o u e s c

V0 . 9 No 5 12 . Ma 01 v2 2

一

种新的求解多维背包问题的分散算法水张晓霞，刘哲(辽宁科技大学软件学院，宁鞍山 14 5 )辽 10 1

摘

要：为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛，出一种求解多维背包问题的新型提

分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中，在搜索过程中，考虑解的质量，既又考虑解的分散性。同时，分散算法还采用了动态更新参考集与阈值接收算法的阂值参数，该以控制搜索空间来加快收敛速度。通过选取国际通用 M K D P实例库中的多个实例进行测试表明，算法可以避免陷入局部最优解，该 能提高全局寻优能力，其结果优于其他现有的方法，并获得了较好的结果。

关键词：多维背包问题；蚁群优化；分散搜索；参考集中图分类号：T 1 P8文献标志码：A ’文章编号：10— 6 5 2 1 ) 5 1 1—4 0 13 9 (0 2 0—7 6 0d i1 . 9 9 ji n 10—6 5 2 1 . 5 0 0 o:0 3 6/.s . 0 1 3 9 .0 2 0 .3 s

Ne s atrs ac lo i m o li i n in lk a s c r be w c te e rh ag rt h frmutdme so a n p a k p o lmZHANG a— i Xio x a,LI Zhe U

(colfSf ae nvrt Si c Tcnl yLann A sa ioig14 5,C ia Sho ow r,U i syo c ne& eh o g ioi o t ei f e o g, nh nLann 10 1 hn )Ab ta t o a od f i n no l c lo t l ou in a d t ep e tr o v r e c n t e p o e so e r h n p i z t n s r c:T v i al g i t o a pi i ma s l t n h r mau e c n e g n e i h rc s fs a c i g o t o miai os l to s,t i p r p e e e w c te s a c lo ih .Th sg e ag rt ou in h spa e

r s ntd a ne s a tr e r h a g rt m e de in d lo hm o i e h s l i o sr cin i c mb n d t e out on c n tu to

meh ns f n o n pi i t n A O nosa e s a h S ) t o s ee o o t n q a t a d dvrict n c a i o a t l yo t z i ( C )i c t r er ( S .I c ni r b t sl i u ly n ie f a o . m co m ao t t c d d h uo i s i iSmu t n o s i l e u l h lo t m d p e e d n mi p ai g s ae y a d t e p r mee r e o f h e h l c e tn o a— a y,t e ag r h a o t d t y a c u d t t tg n h a a trc t r n o r s o d a c p i g t c i h n r i i t c l rt h o v r e c wad ih q ai e i n fte s a c p c . ep roma c fte p o o e lo tm st s ee ae t e c n e g n e t r sh g— u t r go so e r h s a e nl e r n eo r p s d a g r h wa e— o l y h f h i t d o KP b n h r r b e o t e 0R L b ay h x ei n a r s l h W t a te p o o e l o t m a a od e n MD e c mak p o lmsf m h i rr .T e e p rme tl e ut s O h t h rp s d ag r h c n‘ l r s i v t p ig i o a o t l ou in a d e h n et e a i t f lb l p i z t n,a d i i c mp t ie t s le te mu t i n r p n n l c l pi l t n n a c h bl y o o a t a ma s o i g o miai o n t s o ei v o ov h l d me— t i s n lk a s c r b e c mp r d w t e oh rh u i i t o s i emso ou in q ai . i a n p a k p o lm o ae i t t e e r t meh d n tr f l t u l y o hh sc s o t

K yw rs e od:mu i m

ni a kasc rbe MD P) n cl yot i tn A O) ctrsac ( S;r eec ld e s nl npakpol ti o m( K;at o n pi z i ( C;sa e er S ) e rn e o m ao t h fs et

算法优于几种启发式方法。许多研究者围绕遗传算法研究，并

0引言 多维背包问题是运筹学领域中一个经典整数规划问题，有

取得很好的效果，分散搜索算法是在 G而 A基础上发展起来的。

着广泛的实际应用背景，管理中的资源分配、如资金预算…、分布式的数据库处理等，对其求解方法的研究无论是在理论上还是实践中都具有一定的意义。

本文是以 MD P问题为研究对象， K设计了一种混合分散

搜索 ( C&S ) A O S算法。该算法具有如下特点： ) C& S算法 aA O S在搜索过程中，考虑解的质量，考虑解的分散性； 既又 b) A O S算法采用一种新型子集组合成新解的构解机制， C&S即把

求解多维背包问题主要有精确算法和启发式算法两大类。 因为精确算法的时间复杂性都是呈指数增长的，以精确算法所只能求解规模相对较小的问题，大规模问题依赖智能优化算对法解决，常见的算法有模拟退火、遗传算法、蚁群算法等。由于智能优化算法是模拟生物自然现象而提出的新型算法，具有框

蚁群算法的信息素更新技术与分散搜索的组合机制相结合而生成新的解；) C信息素更新策略是影响算法收敛速度的关键

因素之一，了采用信息素局部与全局更新外，采用组合解除还公共物品临时信息素更新机制； ) d根据问题特点，出采用动提态更新参考集合策略，于阈值接收算法 ( A)基 T的局部搜索用

架灵活、与问题本身无关等优点，获得了比较广泛的应用研并究。Del出了模拟退火算法， rxl提 3实验测试一些实例能发现最优解。L等人提出了禁忌搜索算法，获得比较好的效 i并果。H nf等人提出了一种基于振荡策略与代理约束的新 aai

来改进算法性能，从而加快分散搜索算法收敛速度。

1多维背包问题的描述 MD P问题就是给出了 m种资源，种资源的最大提供 K各数量是 b(:1…,。现将 n种物品装入背包， i, m)每个物品 (=1…,) , n所需要的资

源为。,益值是。MD P问题的 受 K数学模型如下：

型禁忌搜索算法，其实验表明，荡策略是算法收敛性与分散振性的一种有效均衡，但是解决大规模的问题计算时间比较长。 T i等人提出标准的遗传算法( A)该算法只能解决小规 he l G,模的问题，决大规模问题效果不好。C u等人成功给出了解 h G该算法是限制搜索可行的范围， A,在合理的运行时间里，该收稿日期：2 1—9 1;修回日期：2 1 1 -4 0 10 -0 0 1 l0

基金项目：辽宁省教育厅资助项目( 2 1 16 L 00 9 )

作者简介：张晓霞(9 6 )女， 16 -,副教授，士，博主要研究方向为智能优化算法、组合优化问题 (s ag@13 cn)刘哲， a hnx 6 .o; z x硕士研究生