摘要
针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包问题的置信传播算法。当算法收敛时,计算每个物体节点的置信度,以确定该物体的装包概率,从而高概率地给出0-1背包问题的解。与其他启发式算法进行了比较,结果表明,该算法具有较好的全局搜索能力。
To overcome the shortcoming of heuristic algorithm,such as local optimum and low optimization accuracy,a belief propagation algorithm was proposed for solving 0-1 knapsack problem.The factor graph model of the problem was constructed according to the linear programming.Based on the characteristics of the model,the corresponding identification function was defined,and a belief propagation algorithm was designed for the 0-1 knapsack problem.When the algorithm converged,the confidence of each object node was calculated to determine the packing probability of the object,then got a solution of the 0-1 knapsack problem with high probability.The experimental results showed that this method had better global searching ability compared with other heuristic algorithms.
作者
张丹丹
王晓峰
冯琬晶
左逢源
ZHANG Dandan;WANG Xiaofeng;FENG Wanjing;ZUO Fengyuan(College of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;Ningxia Key Laboratory of Intelligent Information and Big Data Processing, Yinchuan 750021, China)
出处
《郑州大学学报（理学版）》
CAS
北大核心
2021年第1期29-34,共6页
Journal of Zhengzhou University:Natural Science Edition
基金
国家自然科学基金项目(62062001,61762019,61862051,61962002)
宁夏自然科学基金项目(2020AAC03214,NZ17111,2019AAC03120,2019AAC03119)
北方民族大学重大专项(ZDZX201901)
北方民族大学校级科研一般项目(2019XYZJK05)。
关键词
0-1背包问题
线性规划
因子图
置信传播算法
0-1 knapsack problem
linear programming
factor graph
belief propagation algorithm
