求解多约束0-1背包问题的遗传算法的改进

作者：吕聪颖; **; 刘炯

来源：计算机与现代化, 2012, (09): 140-142.

• 多约束0-1背包问题
• 遗传算法
• 线性规划松弛法
• 修复操作
• 局部优化 multi-constrained 0-1 knapsack problem
• genetic algorithm
• LP-relaxed algorithm
• repair operator
• local optimization

提出对基本遗传算法(Genetic Algorithm,GA)的改进策略,并将其应用于多约束0-1背包问题(Multi-constrained 0-1Knapsack Problems,MKP)的求解。改进策略主要有:将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失,将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后,对大规模测试数据的标准集进行实验,并将该算法与先前的方法进行比较,结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。

• 出版日期2012
• 单位南阳理工学院; 国家知识产权局