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

Competitive decision algorithm for multidimensional 0/1 knapsack problem based on multi-exchange neighborhood search

作　　者：熊小华[1,2] 宁爱兵[1] 马良[1] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]上海第二工业大学计算机与信息学院,上海201209

出　　处：《系统工程理论与实践》2010年第8期1448-1456,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70871081);上海市高校选拔培养优秀青年教师科研专项基金(21012);上海市重点学科建设项目(S30504);上海市教育委员会知识创新工程智能信息服务与支持工程项目

摘　　要：提出了一种求解多维0/1背包问题的竞争决策算法,算法采用一种新的资源交换规则——多交换的资源交换规则,使问题具有更大的邻域搜索空间,从而避免问题陷入局部最优解,同时通过对可行解的随机部分扰动进一步扩大问题的搜索空间.经过测试表明:算法具有计算时间短,求解效果好的特点.Proposed a new competitive decision algorithm（CDA） to solve multidimensional 0/1 knapsack problem.And it adopts multi-exchange neighborhood search as resource exchange rule.The new resource exchange rule prevent the problem from becoming trapped in local optimal solution and improve the effect and efficiency of the algorithm.The algorithm proposed here incorporates a novel approach that consists of randomly perturbing the current solution in order to move some items from knapsack,which makes room for new items to be inserted through multi-exchange movements and allows for improved solutions.We use this algorithm to solve many test instances of MKP and computational results result in good performances.

关 键 词：多维0/1背包问题 竞争决策算法 竞争力函数 决策函数 资源交换规则 多交换 

分 类 号：O223[理学—运筹学与控制论]