文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 一种用于求解0-1背包问题的动态伸缩算法
侵权投诉

一种用于求解0-1背包问题的动态伸缩算法

针对0-1背包这个非确定多项式(NP)完全难题,提出一种新的启发式搜索算法来解决0-1背包问题。算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,通过用启发式策略选择交换背包内和背包外物品的位置,采用动态伸缩策略调整背包大小,选取种群中部分优秀解进入下一代继续进行优化。通过5个背包实例进行测试,实验结果表明该算法收敛速度快、求解精度高,并且具有良好

C m ue n i ei n A p i t n计算机工程与应用 o p t E gn r ga d p l ai s r e n c o

一

种用于求解 01 .背包问题的动态伸缩算法

拓守恒周涛, TUO ho he ZHOU a S u ng . To

1 .陕西理工学院数学与计算机科学学院,陕西汉中 7 3 0 200

2 .宁夏医科大学理学院,川 700银 504 1S h o f a h ma i s n mp trS in e S a n i i e st f e h o o y Ha z o g S a n i 2 0 0 Ch n . c o l M t e tc dCo u e ce c, h a x v ri o T c n l g, n h n, h a x 3 0, i a o a Un y 7

2 S h o fS in e Nig i e ia i e st, n h a 5 0 4 Ch n . c o l c e c, n x aM d c l o Un v r i Yi c u n 7 0 0, i a y TUO h u e g ZHOU a . w l o ih o o v n - n p a k p o l m a e n d n mi e e c p c s r t g .Co p t r S o hn, T o Ne a g rt m fs l i g 0 1 k a s c r b e b s d o y a c t l s o i t a e y m u e

E g e r ga d piain . 0 2 4 ( ) 4 - 9 n i e i n Ap l t s 2 1。 8 4: 74 . n n c o Ab t a t n o d rt o v h - n p a kNP c mp ee p o lm, e h u si e r h a g r h i r p s d Al o t m n o sr c:I r e o s l et e 0 1k a s c - o lt r b e an w e r t s a c lo t m sp o o e . g r h i e c d i c i i s

e t emu t d me so a e l o e . c r i g t ec s p ru i weg t i s r h e s n ad c e s g o d r a d i i r e d wi t l— i n i n l a— d d Ac o d n t o t e n t i h, t o t t e i m e ra i r e, n t so d r hh i r c oh s t i n n h t e i ms a e p t n o k a s c n i c n’ e i s l d Th l o i m x h n e h tm’

o i o so ei sd n u sd n一 h t r u t n p a k u tl a t n t l . e a g rt e i b a e h e c a g st e i e Sp st n f h n i e a d o ti e k印 i t

sc t e r t lo tm. g rh ajs ei msnte asc t y a c eecpc t tg n e et ou akwi ahuii a rh Alo t dut t e p akwi ad nmi tlso i s aeya dgt ab tr l— h sc g i i m sh t i h k n h r s es t n t h u u eg n r t n T i ag r h i se n 5 c a sc e p r n s a d t er s l s o h t t a o d a tg si o— i t e f tr e e a i . h s l o t m st td o l s i x e i o o o i e me t, n e u t h wst a ss me a v n a e c n h ih n

v r e c eo i, ouinp e iina dsa i z t n eg n ev lct s lt r cso n tbl ai . y o i o Ke r s 0 1 n p a k p o lm; e l o e h u it e rh a g r h; y a ct l s o i tae y y wo d: - a s c r b e r a d; e rs cs a c lo t m d n mi e c p cs tg k c i i e r

摘要: O1包这个非确定多项式( P完全难题,出一种新的启发式搜索算法来解决 01针对 .背 N)提 .背包问题。算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,过用启发式策略选择交换背包内和背包外物品的位置,通采用动态伸缩策略调整背包大小,种群中部分优秀解进入下一代继续进行优化。通过 5选取个背包实例进行测试,结果表明该算法收敛速度快、 实验求 解精度高,并且具有良好的稳定性

关键词: 1 0背包问题; -实数编码;启发式搜索算法;态伸缩调整策略动 DO:03 7 ̄i n10 .3 1 0 2 40 4文章编号:0 283 (0 2 0 .0 70 文献标识码: 中图分类号: P 0 . I 1.7 8 .s. 28 3 . 1. .1 s 0 2 0 10—3 12 1 )40 4 .3 A T31 6

l引言 01 -背包

问题 ( npakPol是非确定多项式 ( o. K as r e c b m) Nn dt mnscPl o i, P完全难题, e r i t o nm a N ) e ii y l具有重要的理论和现实意义。理论上很多整数规划问题的解决都依赖于一个高效的背包问题解法;,同时在工业和金融等领域,如资源分配、投资决策、材料切割、装载、资源分配等均可建模为背货物网络包问题加以研究。在过去几十年,有关背包问题的精确算法 ( xc loi s、似算法 ( p rxmae a oi ms与启 E atag rh )近 t m A po i t l rh ) g t

2 01 .背包问题描述 有 n物品s,,…每件重量和价值分别为 w,i=,件,: s s… i(l vi 2…,), n;是背包最大可承受的重量,的目 问题标就是要在不超过背包承重量的前提下,怎样使装入背包的物品价值 V 最大。背包问题的数学描述为:

f )mx f (= a x∑Vf l l=

() 1 () 2

发式方法 ( erts都发表了大量研究成果。穷举法、 H u sc) ii动态 规划法和递归回溯法等精确算法只适合于小规模问题u。蚁

S jt . m ue∑w W bct o t I 1=

w e f不将物品做入背 neX o r, 包中 .

群算法、禁忌搜索算法遗传算法等启发式算法是模拟和自然现象和生物行为过程而提出的新型算法,具有框架灵活、 求解迅速、解质量优良等一系列优点,因而获得了广泛应用。 但蚁群算法、禁忌搜索算法和遗传算法等基本都是采用二进制编码方式来处理背包问题,法复杂、算收敛速度慢而且很容 易陷入局部最优值。 本文提出一个新的简单实用的启发式搜索算法,法采算

i1将 入包中 物品 1,背 3求解 O1 .背包问题的启发式搜索算法 算法的基本思想:新算法首先将待装物品按“价值/量”重 的比值从大到小排序,装包时按物品顺序依次装包,直到装不下为止,后随机交换背包内和背包外物品,然交换后如果包内

物品重量之和小于

,尝试将背包外物品按已排序顺序装 ,则

用原始的实数串编码,启发式选择策略交换背包内和背包用

包,直至不能再装为止。如果包内物品重量之和超过

退包”

直到包内物品重量小于。计算调整外物品的位置,采用动态伸缩策略调整背包大小,选取部分优按相反的方法“如果调整后物品总价值更大,则保留当 胜解进入下一代。最后通用仿真实验表明,算法具有收敛速后的包内物品总价值,度快、稳定性好和求解精度更高等性能。 前解 (列顺序 )排。否则还原。

基金项目:国家自然科学基金 ( o 1613; N . 108 )国家高技术研究发展计划 (6 )N . 0A 0A 0 )陕西省教育厅科研基金 ( o 00K 5, 8 83 ( o 08 A 1 33; 2 N . 1J 49 2 2 1J 6 ) 0 0K4 6。

作者简介:拓守恒 (9 8 )男,C会员, 17一, C F讲师,主要研究方向为进化计算、人工智能、神经网络等;周涛 (97 )男, 17一,通讯作者,博士,副教授。 收稿日:0 1 6l;期 2 1—一 ̄N日期:0 1 8 1; N It ̄: 1—0 4 ht/ w . k. t c s e i1.17 P 0 10 4 0 7 O . m 0 O 2 1-—5 C K 1] 2 11-; p/ wc i e k m/ t l 1 2 . . 1 12 . 1 . 1 t l 0 t 0 2 t: w n n/ d a/ 2 T 2 1 1 h

一种用于求解0-1背包问题的动态伸缩算法

第1页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email