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

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

A Heuristic Network Strategy Model and Algorithm to the 0-1 Knapsack Problem

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.