一类0-1背包问题的启发式网络策略模型与算法

摘要/Abstract

摘要：

针对遗传算法(GA)易陷入局部最优解、搜索精度低等缺点,提出了网络启发式策略的遗传算法(NSHGA),并将其成功地应用于0-1背包问题的求解。该算法采用网络节点关联策略,使算法具有良好的全局寻优能力。同时引入网络节点矩阵优化,利用其精细的局部遍历搜索性能,使算法具有较高地搜索精度。实例仿真结果表明,NSHGA算法可有效避免基本GA算法的早熟收敛,且具有寻优能力强、搜索精度高等特点。此外,与基本遗传算法仿真相比,可明显提高0-1背包问题求解的精度。

关键词: 遗传算法, 启发式网络策略, 0 1背包问题, 节点矩阵

Abstract:

In order to overcome GA's disadvantages that it can be easily trapped into local optimization and has low accuracy of search,a network strategy heuristic genetic optimization algorithm has been proposed,and the algorithm has been successfully applied to solving the 0-1 knapsack problem.In this algorithm,the strategy of network node correlation is introduced to improve the global optimizing capability.This paper also introduces network node matrix optimization and uses its thorough local traversal search to improve the solution accuracy.The simulation results show that NSHGA can not only avoid premature effectively,but also has powerful optimizing ability and high optimizing precision.Compared with basic genetic algorithm simulation,NSHGA can obviously improve the accuracy of the solution to the 0-1 knapsack problem.

Key words: genetic algorithm;heuristic network strategy;0 1 knapsack problem;joint matrix

中图分类号:

TP301.6

夏倩,张晓龙. 一类0-1背包问题的启发式网络策略模型与算法[J]. , 2014, 27(10): 71-.

XIA Qian,ZHANG Xiaolong. A Heuristic Network Strategy Model and Algorithm to the 0-1 Knapsack Problem[J]. , 2014, 27(10): 71-.

参考文献

［1］MARTELLO S,TOTH P.An upper bound of Zero-one knapsack problem and a branch and bound algorithm［J］.European Journal of Operational Research,1977,1(3):169-175.

［2］ZOU Dexuan,GAO Liqun,LI Steven,et al.Solving 0-1 knapsack problem by a novel global harmony search algorithm［J］.Applied Soft Computing,2011,11(2):1556-1564.

［3］TUNG Khactruong,LI Kenli,XU Yuming.Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem［J］.Applied Soft Computing,2013,13(4):1774-1780.

［4］BALAS E,ZEMEL E.An algorithm of large zero-one knapsack problems［J］.Operation Researeh,1980,16(1):196-200.

［5］ZHANG Xiaoge,HUANG Shiyan,HU Yong,et al.Solving 0-1 knapsack problems based on amoeboid organism algorithm［J］.Applied Mathematics and Computation,2013,219(19):9959-9970.

［6］RAJA B S,KANNAN K.A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles［J］.Applied Mathematics and Computation,2008,20(11):71-77.

［7］YANG Zhen,WANG Guoqing,CHU Feng.An effective GRASP and tabu search for the 0-1 quadratic knapsack problem［J］.Computers & Operations Research,2013,40(5):1176-1185.

［8］LUCAS LTOCART,ANASS NAGIH,GRARD PLATEAU.Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem［J］.Computers & Operations Research,2012,39(1):12-18.

［9］RAJEEV K,SINGH P K.Assessing solution quality of biobjective 0-1 knapsack problem using evolutionary and heuristic algorithms［J］.Applied Soft Computing,2010,10
(3):711-718.

［10］JULIEN R,JOS RUI FIGUEIRA,YVES D S.The inverse 0-1 knapsack problem:Theory,algorithms and computational experiments［J］.Discrete Optimization,2013,10(2):181-192.

［11］金慧敏,马良.遗传退火进化算法在背包问题中的应用［J］.上海理工大学学报,2004,26(6):561-564.

［12］刘漫丹.文化基因算法在多约束背包问题中的应用［J］.计算技术与自动化,2007,26(4):61-67.

［13］张宗飞.求解组合优化问题的改进型量子进化算法［J］.计算机工程与设计,2010,31(17):3891-3894.

［14］贺毅朝,刘坤起,张翠军.求解背包问题的贪心遗传算法及其应用［J］.计算机工程与设计,2007,28(11):2655-2657.

［15］赵新超,韩宇,艾文宝.求解背包问题的一种改进遗传算法［J］.计算机工程与应用,2011,47(24):34-36.

［16］钱淑渠,武慧虹,涂歆.动态免疫优化算法及其在背包问题中的应用［J］.计算机工程,2011,37(20):216-218.

[1]	叶翔宇, 林晓会, 丁江乔, 解维坤. 基于优化BPNN的FPGA内嵌高速接口总抖动预测方法[J]. 电子科技, 2025, 38(2): 70-77.
[2]	周彪,张帅,闫登辉,林志成,王建. K波段宽带宽角低副瓣圆极化稀疏阵[J]. 电子科技, 2023, 36(9): 29-34.
[3]	胡逸飞,包梓群,包晓安. 一种基于改进遗传算法的动静态负载均衡算法[J]. 电子科技, 2023, 36(9): 79-85.
[4]	周彪,张帅,张德训,林志成,王建. W波段宽带宽角低副瓣类喇叭天线稀布阵[J]. 电子科技, 2023, 36(9): 8-14.
[5]	张大桂,周志峰,张怡. 基于遗传算法的平面麦克风阵列构型优化方法[J]. 电子科技, 2023, 36(7): 24-31.
[6]	卞大鹏,王叶婷,彭雅欣,汤皓泉. 基于仿真优化的甲板作业站位选择指标策略研究[J]. 电子科技, 2023, 36(5): 88-94.
[7]	王玉梅,王露露. 基于分时电价和用户侧储能的配电网调度优化策略[J]. 电子科技, 2023, 36(2): 7-12.
[8]	王欣阳,王瑞阳,魏云冰. 基于算术优化算法的低压配电网故障区段定位方法[J]. 电子科技, 2023, 36(12): 25-31.
[9]	陈星,李丹杨,何庆. 自适应多目标遗传算法的集成剪枝用于人脸表情识别[J]. 电子科技, 2023, 36(12): 55-63.
[10]	周启平,何伟,贾蕾,郭俊凯,赵建国. 基于北斗和边缘计算的车联网导航技术研究[J]. 电子科技, 2023, 36(1): 51-59.
[11]	魏泽丰,周元元. 移动边缘计算环境下基于移动感知的工作流调度算法[J]. 电子科技, 2022, 35(9): 58-64.
[12]	张崇崇,黄亚宇. GA-BP神经网络对片烟结构的预测研究[J]. 电子科技, 2022, 35(6): 35-42.
[13]	金霄,吴飞,鄢松,陆雯霞,张忠艺. 基于GAWK-means的地铁车站指纹定位方法[J]. 电子科技, 2022, 35(2): 34-39.
[14]	邵志慧,杨俭,袁天辰,伍伟嘉. 基于排列熵和支持向量机的轨枕病害诊断[J]. 电子科技, 2022, 35(2): 52-58.
[15]	赵鉴,袁渤巽,倪凌凡,林顺富,王维. 基于改进粒子群算法在多能互补微网中的应用[J]. 电子科技, 2022, 35(10): 72-78.