基于多交换邻域搜索的多维0_1背包问题竞争决策算法

第 30 卷第 8期 2010年 8 月 系统工程 System s E ng i ne e ring 中图分类号: 理论与实践 一 T ho o r y 2. 上海第二工业大学计算机与 信息学院, 上海 2 0 12 0 9) 摘要 提出了一种求解多维0 / 1 背包问题的竞争决策算法, 算法采用一种新的资源交换规则 ) 多交换的资源交换规则, 使问题具有更大的 邻域搜索空间, 从而避免问题陷入局部最优解, 同时通 过对可行解的随机部分扰动进一步扩大问题的搜索空间. 经过测试表明: 算法具有计算时间短, 求 解效果好的特点. 关键词多维 0 / 1 背包问题;竞争决策算法;竞争力函数;决策函数;资源交换规则;多交换 C o m P etitiv ed eeisio n k n a P sa c k P ro b le mb a s e d al gori thm f o r m ul ti di m ensi onalo/1 o n m ulti一 ex eh a n g e n eig h bo rh o o d se areh x IO N GX ia o -hu al,2,N I NGA i - b i n gl,M A L i an gl (1.SehoolofM anagem en t , Uni v e rsit y ofShangha i f o rSei enc e a n d Te C hnolo瓢 Sha n gh a i200093, China: 2. Col l e g e of C om puter a n d Inf o rm a t i on, Sha n g h ai Se c ond Pol y t e c hni e U ni v e r s i t y ,Sha n g喊 201209, C hi na) A b s tr a ct pr o posed a new c o m pe t itiv e de c i si on al g o r ithm (C D A )to s o l v e m ul ti di m e n s i o n a l o/1 knapsa C k probl e m , A n di t a doPts m ui t i 一 exeha n罗 n ei gh borhood s e a r eh a sre s ou r ee exeha n g erul e . T h enewre s ouree ex eh a ng eru l e P rev e n tth e p ro b l e mf r o mb ec o m i n g tr即 p ed in l o ea loP tim a l so lu tion a nd i m p r o v eth e ef f e et and ef f i el e nc yofth eal gori thm . T he al g o ri thmPr o Pos e d her ei nc o rp ora t e sa novela pPr o 朗 h tha tc o nsi s t s of ra n dom l y Per t urbing the eurren tsolution in order to m o v esom e item sf r o m knaPsa c k, w hic hm akesr o om f o r new item s to be inser t e dthr o ugh m ui t i 一 exeha n g e刀 “ ovem en t s a n d al low s f o r i m pro v ed sol u tions. w 七u s e this a l g n ri thmto s o lv em a叮 test i nstanees of M K P a n d eom puta t i ona lr e sui t s re s ul t in g ood perf o rm a nc e s. K eyw ords m u lti -dim ensiona l o/1 kn即sack problem ;eom peti ti v e de c i sf o n algorithm ;com peti ti v ef o ree f u n eti o n : d e ei si o n f u n eti o n ; re s ou rees ex c h a n g eru l e ; m ui t i - e x eh a n g e 1 引言 背包问题 ( K na p sa c k P r o b l em )是一个典型的组合优化难题, 属于经典的NP 难题, 有着广泛的实际应用 背景. 如可应用于投资决策 !资源分配 !项目 选择 !货物装载等, 并且还常常作为其他间题的子间题而加以 研究 = ,一 2 .该问题有多种形式, 其中一般的整数背包间题都可以转化为等价的 “ /1背包问题.传统的 “ /1背 包间题是把具有一定重量 ( 或体积)和价值的 “件物品放在一个重量 ( 或容量)有限的背包中, 最后使得背包 中物品的总价值最大. 记 p- 0, 二- 0 分别表示物品 乞 的价值!重量, x -表示物品乞 的标志变量 ( x - = 1 表示将物品装入到背 包中, x - 二 0 表示不装入), V 表示背包的重量 (或体积)限制, 则 “ 八 背包间题的数学模型可描述如下: ma x :一 艺几 二 (1) 收稿B 期:200, o孚 25 资助项目:国家自 然科学基金(7 0 87108 1 ) ; 上海市高校选拔培养优秀青年教师科研专项基金 (21012);上海市重点学科建设项目 ( s 3 0 5 0 , ) ;上海市教育委员会知识创新工程智能信息月 赂 与支持工程项目 作者简介:熊小华 (19 7 8 - - ), 女, 博士研究生, 主要研究方向为系统工程 !算法设计;宁爱兵 (1972一 ), 男, 博士, 副教授, 主要研究 方向为系统工程 !算法;马良( l 9 6 4 - - ), 男, 博士,教授, 博士生导师, 主要研究方向为系统工程 !算法. 第 8期熊小华, 等:基于多交换邻域搜索的多维 0 / 1 背包问题竞争决策算法 1449 , . ., . . . . . . . . ,几 - ! J 1 . 户- l 产 Q q d g 了. .-口 了- ! 艺 -! x- 三 V 乞 = 1 xi 1O,1 在传统的 “ /1背包问题中, 仅考虑物品的一种约束, 如所有装入背包的物品的总重量不超过背包的重量 限制.但在不少情况下, 需要同时满足 2 个或 2 个以上的约束, 如要求所有装人背包物品的总重量不超过背 包的重量限制, 且要求所有装入物品的总体积不超过背包的容量限制, 这类具有多个约束的 0/1 背包间题称 为多维 “ /1背包问题 ( M ul ti di m ensi onalo/1kn叩sa c k probl em , M K p)1 3一 .- , 多维 “ /l背包间题的数学描述 如下: 动封 九 一 艺几 ! 云 = 1 艺:- ,x*: “ , x -任0,l, J = 1,2, , ,m 乞=1, 2, , , n Z 了. . . ,- ! 田I D S 其中n 表示物品的数量, 爪表示背包约束的维数 ( 也即约束的个数);p -沙! 0 ) 为物品 乞 的价值, 从 ( 6) 为物品 乞 的标志变量, 物品 乞 被选中装入背包则 x, = 1, 否则 x-= 0 ; 八 J ( 八 , 0 ) 为物品 i耗用背包第 j 维资源的 数量, 勿为背包第 J 维资源的总量. 不失一般性, 假定上述参数满足下列约束: ! J I 少! l 产! ! . . 了 门 了0 0 0 刁 才 了. .! / 口! ! / 矛. ! . 一 . 叹 和 b 7都 是 正 数 S. t. 一 1( 日 J ,昏 r- ,6 7. - 1 1. 200. m L r叮兰勿 目前求解 M K P 间题的算法主要有两大类:精确算法和启发式算法.精确算法如隐枚举法 !分支定界法 等, 这类算法在求解较大规模问题时大多存在计算量大 !迭代时间长的缺点, 在工程实践中求解规模较大的 问题时, 大多会寻找一个高效可行的启发式算法.启发式算法主要包括:遗传算法 !蚁群算法 !免疫算法 !禁 忌搜索算法等.启发式算法是模拟自 然现象或人类思维过程而提出的算法, 具有框架灵活 !与具体间题本身 无关等一系列优点, 因而获得了非常广泛的应用.本文在以上研究的基础上, 提出了一种新的求解多维 0 / 1 背包间题的竞争决策算法.为了避免间题在寻找最优解的过程中过早的陷入局部最优, 采用新的多交换的资 源交换规则来扩大间题的搜索领域以避免问题陷入局部最优.并对大量的实例进行了实算测试. 2竞争决策算法 这里, 简要给出竞争决策算法的原理与基本概念, 算法的详细介绍可参阅文献 = 12一 19!. 2.1 竞争决策算法原理 自 然界中的竞争和决策都是在一定的竞争规则下, 在竞争者的实力 !竞争者和环境间的关系 !多个竞争 者实力的差距和初始竞争状态等多种因素的作用下, 经过多次竞争和决策后, 使不同的竞争者分别占有一定 的资源而达到一种新的竞争状态. 只要新的竞争状态优于初始竞争状态, 就会达到优化的目 的.竞争决策算法 就是利用该原理来达到优化的目的, 它通过构造一个或多个竞争者参与到对一个或多个资源的竞争过程中, 通过优胜劣汰的决策原则使一部分竞争者获得资源而增强实力, 使另一部分竞争者失去资源而削弱实力甚 至死亡. 2 . 2 基本概念 l ) 竞争者:参与竞争的对象. 为了便于描述竞争, 若只有一个竞争者时, 可以假设存在一个虚拟的竞争 者 N ( 代表自 然), 虚拟的竞争者 N 没有自己的竞争力函数. 2)资源:竞争者争夺的对象, 整个竞争和决策过程都是围绕着资源进行的. 3)竞争决策状态:竞争决策状态是某一时刻每个竞争者所占有资源的情况, 初始状态就是指在竞争决策 前各竞争者所占有资源的情况. 4)竞争力函数:竞争力函数代表竞争者对某种资源具有的竞争力. 5)决策函数:决策函数起到裁判的作用, 用来裁决资源的分配.其具体作用有: 1450 系统工 程理 论与 实践 第 3 0 卷 当竞争决策中只有一个非虚拟的竞争者时, 决策函数确定竞争者占有资源的次序; 当竞争决策中有多个非虚拟的竞争者时, 决策函数一方面确定竞争者占有资源的次序, 另一方面确定 当前资源应分配给具体的某一个竞争者; 决定把某一资源从某一竞争者手中剥夺出来并分配给另一个竞争者. 6)竞争决策均衡:竞争决策中的均衡是一种资源分配的状态, 在此状态下不存在一个非虚拟竞争者可以 根据竞争力函数和决策函数占有更多的资源. 7) 资源交换规则: 在竞争决策算法中的均衡状态时, 通过资源交换规则使竞争进入到一个非稳定的状 态, 从而使各竞争者重新进行竞争并使竞争进入到一个新的竞争决策均衡状态.资源交换规则必须使竞争进 入到一个非稳定的状态, 即在此非稳定的状态下进行竞争会达到一个新的竞争决策均衡状态而不是进入到原 来的竞争决策均衡状态. 3多维 “ /1 背包问题的竞争决策算法 3. 1 算法原理 在 M K P 问题的竞争决策算法中, 把 n 个物品看作各个竞争者争夺的资源.将背包看作竞争者 A , 另一 个竞争者是虚拟竞争者 N .竞争开始时虚拟竞争者 N 占有所有物品, 竞争者 A 不占有任何物品, 竞争结束 时竞争者 A 占有的资源即为确定要装入到背包中的物品. 3. 2 基本符号及含义 为了方便叙述, 文中采用如下符号来表示: n表示物品的数量; “表示背包约束的维数; 抓约表示物品 乞 的价值; :( 乞 ,j ) 表示物品 乞 耗用背包第 j 维资源的数量; 6( 力表示背包第 j 维资源的总量约束; do n! /“ (- )表 示 物 品- 的 平 均 价 值 密 度 ,其 数 学 描 述 如 下 :d/ n/“ (- )飞丹丽; S 0 表示还未装入到背包中的物品的队列, s 0 按照物品的de n s i t 抓 动值降序排列,也即如果 乞 任S 0 ,j 任S 0 且 乞 1 ; 物品的价值 尸= pl,pZ, ,p “ 且 p - 0; “ = 背包的资源约束维数且 m 1;B = 乙 1, - 2, , 6m 为背包各维资源的总量限制;R = 与 与 0, 乞 = 1,2, , ,n;J = 1,2, , “ 为每个物品各维资源的消耗量; 输出:队列 S* 中的物品即为需要装入背包的物品. Step i 初始化 计算每个物品的 dens乞 t夕 (乞 )值; S 0 = l, 2, ,n, 51= , S*= , 爪e一 “ ( j)= 乙 ( j), j 二1,2, ,m ; step Z 竞争决策 在竞争开始, 虚拟竞争者 N 占有所有的物品资源, 竞争者 A 不占有任何物品资源; 根据竞争力函数的定义计算竞争者 A 对每个物品的竞争力函数值 P o 二 e r ( i ) ; step 2. 1 资源分配阶段 若不存在竞争力函数值大于0 的物品, 则跳转至 St 叩 2. 2 ; 否则按照决策函数, 将符合要求的物品分配给 竞争者 A , 即将竞争力函数值最大的物品k 装入到背包中并按如下方式修改:S 0 二S 0 一岭;51= 51+ 岭; 嫩 e一 “ ( j)= 而 e一 “ ( j)一r( k, j), j = 1,2, , “ 在约束 而 e一 “ ( 力 下, 若物品不能放入背包则置其竞争力函数为 “ , 否则不变. 跳转到 Step Z # 1; s t ep 2. 2 资源交换阶段 在该阶段中, 通过剥夺竞争者 A 已占有的物品来扩大问题的搜索领域, 资源交换直到通过交换不能得到 更好的解为止. w h i l e 执行次数 夕 ( k)则 B egin S 0= 5 1 = S 0 +科一凡; 51一无 + S 3 ; F ree刃( J)= e“ :一( j)一又 r( s,J s 1S 3 S * = 5 1; en d . en d . 子程序:2一 o p t操作 对队列 S: 中顺序的两个物品 k 和 t, 且 无 兴t B egin cor - - v( j) = 血 e一 “ ( j)+ r(k,J)+ :( 亡 ,J), J = 1,2, , “; 在约束 c t L :刃( 力臼= 1,2, ,m )下, 计算 S 0 中能装入到背包中的物品的总价值, 记为pe, 计算过程中 放入的物品的集合记为 凡; 若 p “ ( p( k)+ p(t )则 B egin S 0二S 0 + k,好一凡; 51= 51一无 ,t+ S 3 ; F :ee山( J)= e“ :一( J)一 E:( s,j); s 任5 3 S * =5 1; end . end . 子程序:3一 o p t操作 对队列 51 中顺序的三个物品 k !亡 和 v, 且 k 并艺 , 亡 笋“ , “兴k B egin e“ 二“ ( J) = 而 e一 “ ( j)+ :(无 ,J)+ :(t,j)+ r( v,J), J = 1,2, , “; 在约束 洲r - “ ( j ) ( J 二1,2, ,7 n )下, 计算 s 0中能装入到背包中的物品的总价值, 记为p “ , 计算过程中 放入的物品的集合记为 凡; 若p “ ( p ( k)+ p( 艺 )+ 夕 ( v)则 B egin S 0 = S 0 + k,亡 ,v一S 3 ; 51= 51一儿 ,亡 , “ + 53; F r e e一( 力二c u , 川( j )一 E:(, ,力; s 任5 3 S * =5 1; end . end . 子程序:R a n dom 一 perturbi ng 操作 随机产生三个在 1一“之间的互不相等的整数 hl, h:和 h3; 若编号为 hl的物品在队列 51 中, 则调用子程序 R e 丑em (hl); 若编号为 hZ 的物品在队列 51 中, 则调用子程序 R e m o v ejt e m (hZ); 若编号为 h3 的物品在队列 51 中, 则调用子程序 R e m o v ejt e m (h3); 子程序:R em J t e m ( g) 操作 S 0 = S 0 + g; S:= 51一夕 ; 第 8期熊小华, 等:基于多交换邻域搜索的多维 0/1 背包问题竞争决策算法 1453 而 e一 “ ( j)= cor - - v( J)+ r( 夕 ,J)( j = 1,2, , ,二) : 3. 6 时间复杂度分析 S t e P I 中 对 S 0 采用折半 ( 二分法)插入排序算法按平均价值密度从大到小排序, 其时间复杂度为O ( nl o g 0) 排序后最多把所有的物品扫描一次就可以了, 因此 St印 1最坏情况下的复杂度为O (n l o g 0);S t 印 2. 1最坏情 况下复杂度为 O ( n x “);S t e P2. 2 中w h i l e 循环次数为迭代次数, 每次循环要么交换物品, 要么结束本次循 环, 每次循环移出物品总次数为 3n, 接着每一次装入物品时最多扫描 n 个物品, 扫描一个物品时需要判断该 物品的m 维资源耗用量能否得到满足, 因此 St即 2. 2 最坏情况下复杂度为 0 (迭代次数 x3nZx 二). 由此可 知, 整个算法最坏情况下的复杂度为 O ( 迭代次数 x302x m ). 4实验结果与分析 为验证算法的有效性, 采用 D e lph i 7. 0 在一台配置为 Ce le r o n ( R )2. 4G Hz.的 PC 机上实现了该算法, 并 对 3 7 个测试算例进行了计算测试, 这些测试实例可以通过 h t t P : /pe o P l e. br u n e l . a c . u k /!m a s t jj b 加b加r l i b/ f il es/m nk a p一 1. t xt( m kn即ebl. t xt)下载. 例 1 m nk a n一 1. t x t文件中的 7 个算例. 在表 1 中列出了每个问题的规模 !公布的最优解 !采用 CDA M K P 算法得到的最好解 :*. S *是最好解取得时装入背包的物品集合. 表 1m n恤p_l.txt 文件中的 7 个算例 扩 问 题规模 (n / m ) 公布的最优解 6/10 10/10 15/10 20/10 28/10 39/5 50/5 38 0 0 87 06 .1 40 15 6 12 0 12 40 0 10 6 18 16 53 7 3 80 0 87 06 .1 4 0 15 6 12 0 1 24 00 10 60 4 16 53 7 0 1 1 白4 n n 匕口甲八氏口T T T T T T T 上述 7 个算例采用 CDAM KP 算法得到的最好解中放入背包的物品集合分别为: TI:S*= 2,3,6; TZ:S*= 2,4,5,8,10; T3:S*= 1,2,4,6,7,9,10,14,15; T4:S*= 1,10,14,15,16,17,18,19,20: TS:S*= 1,2,3,9,14,15,16,17,18,19,20,21,22,23,25,26,27,28; T6:S*= 1,4,6,7,8,9,11,13,14,15,16,17,19,20,21,22,23,25,26,27,28,29,31,32,33,34,35,37,38,39; T7:S*= 4,6,8,9,11,12,13,15,16,17,19,20,23,25,26,27,28,29,31,32,34,35,36,37,38,39,40,41,42,43,4 4 ,47,48, 49,50 # 从表 1 中我们可以看到, 通过 CD AM K P 算法我们可以找到所有 7 个算例的最优解或近似最优解. 例 2 在文件 m k naP c b l . t x 七 中有 3 0 个测试算例. 每个算例都有 1 0 0 个物品和 5 个背包约束并且没有 公布最优解.下面给出 CDA M KP 算法计算得到的最好解的结果. T l: z* = 24373. S*= 2,7,8,9,11,16,18,19,24,27,29,30,32,35,44,50,57,62,63,66,68,69,76,77,79,85,86,93,99. T Z : z* = 24274 . S*= 4,11,19,21,28,29,35,37,42,43,46,49,50,54,57,58,59,62,63,65,74,75,82,89,91,92,94,96,100. T 3 : z* = 23 538 . S*= 5,8,11,12,14,19,22,29,30,33,35,38,45,49,52,56,60,65,70,73,75,80,82,85,88,93,94,97,100. T 4: 之* = 2350 1. S*= l,4,6,7,9,12,13,14,23,25,28,31,35,36,37,43,50,54,55,56,57,64,71,77,79,80,87,95,96. T S: z* 二23991. 1454 系 统工 程理论 与 实践第 30卷 S*= 2,5,9,14,18,29,35,41,45,47,50,51,55,56,57,61,62,63,66,67,68,72,80,82,88,93,96,97,99,100. T 6: 名 * = 24 613. S*= 3,6,8,17,18,21,23,24,30,31,32,33,34,35,41,45,47,49,54,55,57,59,65,71,74,76,79,85,90. T 7 :z *= 2559 1 . S*= 7,9,14,15,19,22,23,26,29,30,34,40,42,45,47,51,60,61,64,65,66,74,77,79,80,88,89,92,93,94,97. T S :z *= 23 37 4 . S*= 15,17,20,21,22,25,27,30,32,41,43,44,46,48,53,54,56,59,60,66,70,78,80,83,84,85,91,95,99. T g: z * = 24 024 . S*= 8,12,16,19,24,25,28,32,35,37,41,56,60,66,67,70,72,75,78,79,81,83,84,92,93,95,97,99. T IO : z * = 244 11. S*= 8,10,11,13,15,19,20,23,31,34,37,38,39,40,45,46,49,52,56,57,60,62,63,71,77,83,87,91. T ll : z * = 4 275 7. S*= 1,3,4,8,9,11,13,16,18,19,20,25,26,27,30,31,33,35,36,37,38,39,40,41,43,45,47,50,51,53,54, 56,58, 60,66,68, 71,72,74,75,77,80,81,83,84,85,87,92,93,94,99,100. T 12: 之* = 4 24 71. S*=2,5,7,12,13,14,23,24,25,27,29,31,33,34,35,36,38,40,41,43,44,46,47,48,49,50,51,52,55,56,58, 59,62, 69,70,71,72,74,77,79,82,84,86,87,88,90,94,97,98,99,100. T 13: z* = 4 1946 . S*= 4,5,7,9,10,12,13,14,16,17,19,20,21,24,25,26,30,32,36,37,40,41,42,45,46,47,48, 49,50, 51,53,54,58, 59,61,65,66,68,70,71,72,76,77,78,79,85,86,87,88,89,92,93,95,96. T 14: z* = 450 70 . S*=1,4,5,7,8,9,12,13,14,18,20,22,23,26,27,29,30,32,34,37,38,39,41,42,43,45,48,50, 52, 53,55,56,57, 60,61,63,64,65,69,71,74,75,77,80,84,87,88,92,93,94,96,97,100. T 15: z* = 422 18 . S*= 2,3,4,5,6,10,17,19,21,22,24,25,26,27,28,29,31,32,33,35,37,38,39,40,41,42,44,47,49,52,53, 56, 58, 64,66,67,68,73,74,77,78,79,81,83,84,86,87,89,92,93,95,96,97,99. T 16: z* = 42927 . S*= 1,3,6,8,9,12,13,14,20,23,25,27,28,29,33,36,37,39,41,43,4 4 ,45,48,50,52,55,56,57, 58,60,61, 63,66, 67,68,69,72,73,75,76,77,78,79,84,85,86,88,90,93,94,95,97,99,100. T 17: z* = 42009 . S*=4,5,6,7,8,9,10,11,12,15,17,18,19,20,21,22,24,25,28,29,30,34,36,39,40,41,42,43,46, 47,49,50, 51,53, 55,56,58,60,61,62,63,64,65,66,68,69,76,80,85,86,87,90,93,98,99. T 18 : z * = 4 50 20 . S*= 3,4,6,8,9,11,13,17,18,22,24,25,26,29,30,31,32,34,38,41,42,43,45,46,47,48,51,53,55, 57,58,59, 62, 63,65,66,67,68,69,70,73,74,78,81,83,84,86,88,89,90,91,97,100. T 19: 之 * = 4344 1. S*= 2,4,6,11,15,16,19,20,21,22,23,25,27,28,30,32,33,35,41,44,45,47,49,50,51,52,53,55,58, 59,61,62, 65,66,67,68,69,70,71,73,7 4 ,7 6 ,77,81,82,84,86,92,97,98,99,100. T 20: z* = 44540 . S*= l,4,5,6,7,8,10,13,14,15,16,17,18,19,21,22,24,26,28,29,30,32,33,35,36,38,39,4 0 ,43,46, 47,49,51, 56,60,65,66,67,69,70,71,76,77,78,79,82,84,88,89,92,94,95,96,99. T 21: z* = 5982 2. S*= 1,2,3,5,6,7,8,9,11,12,14,15,17,18,19,20,21,22,23,24,25,26,28,29,32,33,35,36,37,39,4 D , 41,42,43,45,46, 47,4 8,49 ,50 ,5 1,53,56,57 ,58,59,60 ,62,63,64 ,66,6 7,68 ,69,70 ,7 1,72,74 ,75,76,77,78, 79 ,80 ,81,82,83,86 ,8 7, 88,89,90,91, 93,95,96,97,99. T 22 : z * = 6 20 81. 第8期熊小华, 等:基于多交换邻域搜索的多维0 / 1 背包问题竞争决策算法 1455 S*= l,2,3,4,7,10,11,12,13,14,15,16,17,18,19,20,22,23,25,26,27,29,30,31,32,33,34,35,36,37, 39 ,40 ,42 ,43,45,4 6,47 ,48,4 9,50 ,51,53,54 ,55,56 ,57,59,60 ,6 1,63,64 ,65 ,67,68,71,73,7 4 ,75,76,77 ,80, 82,85,86,88,89,90,91,92,93,94,95,96,97,98,99,100. T 23: z* = 59802 . S*= 3,4,6,8,9,10,11,12,13,15,16,17,18,19,20,21,22,23,24,25,27,28,29,30,31,34,35,36,37,38,39,43, 45 ,46,47,48 ,49 ,50,51,52,53 ,54,55 ,57 ,58,59,60 ,61,63,64 ,65,66 ,67 ,68,70 ,72 ,73,74 , 76,77,80, 83,84,85,86,87,88,89,90,91,92,94,95,96,97,99,100. T 24: 名 * = 60479 . S*= 1,2,4,5,6,8,9,10,11,12,14,15,16,18,19,20,21,22,25,26,28,29,30,32,34,36,39,40,41,42,43,45,48,49, 50 ,5 1,53 ,54,55,56,58 ,61,62,63 ,64 ,65,66 ,67,69,70 ,7 1,72,74 ,76,77,78 ,79,80,8 1,82 ,83,84 ,85 , 86,87,88, 90,91,92,94,95,96,97,98,99,100. T 25: z* = 6 109 1. S*= 1,2,4,5,7,9,10,11,12,15,17,18,19,20,21,23,24,25,26,27,28,29,30,31,32,33,35,37,38,40,42,44, 4 5,46 ,49,50,51,52 ,53 ,54,55,57 ,58,59,6 1,62,6 4,65 ,66,67,68 ,69,70 ,71,72,73,74 ,75,76,77 ,79,80, 81,82,83,84, 85,87,90,91,92,93,94,95,96,97,98,99. T 26: z* = 58959. S*= l,3,4,5,7,9,10,12,14,15,16,18,19,20,21,22,23,24,25,26,29,30,31,32,33,35,36,37,38,39,40,41,42,43, 4 4 ,48,50 , 5 1,52,54,56,57,59 ,60,62,63 ,64,65,66 ,67,68,70 ,72,73,74 ,77 ,78,79 ,8 1,82,83 ,84,85,86 ,88, 89,90,91,92,94,95,96,97,98,99,100. T 27: 乞 * = 61519. S*= 2,3,4,5,6,8,9,10,11,12,13,15,16,17,18,20,23,24,27,28,30,32,33,34,35,36,37,39,40,41,42,43, 45,46, 47,48,4 9,5 1,52,53,54 ,55 ,56 ,58,59 ,60 ,61,6 3,64 ,66,67,68 ,69,70 ,7 1,73,75,76 ,77,78,8 1,82,83,84 ,85, 87,88,89,90,91,92,93,95,97,98,99. T 28 : z * = 6 1520 . S*= l,2,3,5,6,7,10,12,13,14,15,16,17,20,22,23,25,26,27,28,29,30,31,32,33,34,36,37,39,40,42,43,44,45, 46 ,47 , 48 ,49,50,51,53 ,54 ,55,56 ,57 ,61,62,63 ,64,65,66 ,67,6 9,7 1,72,73,74 ,75 ,77,79,80 ,81,82,83 ,86, 87,89,90,91,92,93,94,97,98,99,100. T 29 : 之 * = 59453 . S*= 2,3,4,5,6,8,9,10,11,12,14,16,17,20,21,22,23,24,26,27,28,29,30,31,32,35,36,37,39,40,41,42,44,45, 47 , 48 ,49 ,50,51,52,53 ,54,55,56 ,57 ,58,60 ,6 1,63,64 ,65 ,67,6 8,70,71,72,73 ,74,75,76 ,77,79,80,81,82 , 84,85,88,89,90, 91,92,95,96,98,100. T 30: z* = 59965 . S*= 1,2,3,4,5,7,8,9,10,11,12,13,15,17,18,19,20,21,22,26,27,31,32,33,34,35,36,38,39,40,41,42,43,44,45, 46 , 47 ,48 ,49,50,52 ,54 ,55,56,58 ,59,60,6 1,62,64 ,65 ,67,69,7 1,72,76,77,78 ,79,80 ,8 1,83,84 ,85,87,88 ,90 , 92,93,94,95, 96,97,98,99,100. 5 至 聋 隶语 竞争决策算法是在分析大自 然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就 优化 !决策决定左右的特性提出的一种能广泛应用于一系列组合优化难题的新型寻优算法.本文提出基于多 交换的资源交换规则的多维 “ /1 背包间题的竞争决策算法提高了算法求解的效果, 这在一定程度上丰富了 竞争决策算法的理论基础, 促进了竞争决策算法研究的进一步开展. 参考文献 B a l a sE , Z em e l E . 11 3任 114 5 . A n al gori thm f o r la r ge zerne kn即sack problem s J#O pera t i ons R esea r c h , 1980, 28(5): l l 2 D em bo R S, xgso, 36(1): H am m er P L.A re d uetion algori thm f o r knaps-k probl em s J 8 .M ethods ofO pera t ions Resea r eh 49 书 0 . 14 56 系统 工程 理论 与实践第 30卷 38C h up C ,B ea s l即 J E.A G eneti e al gori thm f o r the m ul ti dim ensi ona l kn即sa c kproblem Jl.JournalofH euri sti es, 1998, 4(1):63一 86. ! 4 : G ottli eb J, R ai dl G R .C ha r a j c teri zing loea ity in deeode r 一 ba s ed EA s f o r the m ul ti dim ensiona l kn即sa c kprob- l e m = C /Leetur e N o t es i n C om puter Sei enee (V O I. 1829), Spri nger - V e rl鳍, London U K , 1999:38一 52. 5 : R a i dlG R .A n i m pro v ed 罗neti e a l 即rithm f o rthe m ultieonstra i ned 0 - 1 kna P sack probl em = C!/Proe.ofthe sth IE E EIn t erna t i ona lC onf e renee on E v o l uti ona r y C om p uta t ion, 1998 IE E EW 6rl d C ong r ess on C om P uta t i ona l In t ell l罗n ee, A nehorage, A la s k a , 1998: 207 - - 211. 6 8T hi el J, V O ss 5.Som e experienees on solvi ng m ui ti eonstrai n tzero - one kn即sac k probl e m s with 罗neti e a l z o - ri thm s J!.Inf o r , 1994, 32(4):22序242. = 7 Cra m a Y , M a z zola J.O n thestreng t h ofrel a x a t i onsofm ui ti dim ensiona l knapsac k probl em s J 8 .Inf o r, 1994, 32(4): 2 1于 22 5 . 8 : R 德 vil le A , Pl a t eau G .A n ef f i eien t preproeessing proee d ure f o r the m ul ti dim ensi ona l 0 - - 1 knapsack problem J. D iscr e te A ppli e dM a t hem a t i es, 1994, 49(1/3): 18于212. = 9 H il l R , R e i lly Ch. T he ef f e c t s of eoef f i ei en teorr e l a t ion strueture in tw o -di m ensi ona l kna P sac kprobl em son soluti on proce d ure perf o rm ance J8#M a n a s em en t Sei enee, 2000, 46(2): 302一 317. = 10 8V im on t Y , Boussi er S, V舫quez M .R e dueed eosts prop鳃a t ion in a nef f i eien t im pli eit enum era t i on f o r the 0 1 m ul ti di m e nsi onalkn即sa c k probl em Jl#Journa l ofCom bi n a t oria l o pti m i za t i on, 2008, 15(2): 165一 178. = 11: F r 乙 vil le A , H a n a f i5. T he m ul ti dim e nsiona l 0 - 1 knapsa C k probl em 一 Bounds a n d c o m puta t iona l a s peets Jl. A nna l sofo pera t ions R e sea r c h , 2005, 139(1):195忍27. = 1 2 : 宁爱兵, 马良 竞争决策算法及其对车辆路径问题的 (V R P)求解 s l .管理科学学报, 200 5 , 8(6): 1华1 8 . N ing A B , M a L.Com pe t itiv e deeision al go过 thm a n d i ts 即pl iea t i on to v e hiele routing probl em J 8 .Journa l of M a n 鳍em en t Seienee in Chi na, 2005, 8(6): 10一 15. = 1 3 : 宁爱兵, 马良#度约束最小生成树 (D C M ST )的竞争决策算法 s #系统工程学报, 20 0 5, 2 0 (6):