摘要
背包问题是计算科学理论中一个著名的NP-hard问题,也是典型的组合优化问题,在物流系统的库存分配和货物装载等方面都有非常重要的应用。采用借鉴遗传算法的编码、交叉和变异的遗传微粒群算法对背包问题进行求解。为了增强遗传微粒群算法的搜索性能,将基于自学习规则的启发式算法与遗传微粒群算法相结合得到混合遗传算法用于求解背包问题。对多个标准测试实例的仿真计算表明,该算法能有效求解KP问题。
The knapsack problem （KP） is a classic well- known NP- hard combinatorial optimization problem in scientific computing. It is applied in inventory allocation and cargo loading. This paper employed the genetic particle swarm optimization, which was derived from standard particle swarm optimization with genetic coding, crossover and mutation operators. To enhance the searching performance, a heuristic algorithm was introduced for genetic particle swarm optimization. The algorithm was implemented for well- known benchmark cases, and the simulation results have shown the infeasibility and effectiveness of the algorithm.
出处
《计算机与数字工程》
2008年第11期4-6,49,共4页
Computer & Digital Engineering
关键词
微粒群算法
背包问题
启发式算法
particle swarm optimization, knapsack problem, heuristic algorithm
