摘要
提出了一种求解多维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.
出处
《系统工程理论与实践》
EI
CSSCI
CSCD
北大核心
2010年第8期1448-1456,共9页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(70871081)
上海市高校选拔培养优秀青年教师科研专项基金(21012)
上海市重点学科建设项目(S30504)
上海市教育委员会知识创新工程智能信息服务与支持工程项目
关键词
多维0/1背包问题
竞争决策算法
竞争力函数
决策函数
资源交换规则
多交换
multi-dimensional 0/1 knapsack problem
competitive decision algorithm
competitive force function
decision function
resources exchange rule
multi-exchange
