摘要
提出对基本遗传算法(Genetic Algorithm,GA)的改进策略,并将其应用于多约束0-1背包问题(Multi-constrained 0-1Knapsack Problems,MKP)的求解。改进策略主要有:将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失,将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后,对大规模测试数据的标准集进行实验,并将该算法与先前的方法进行比较,结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。
The improved strategies for GA are presented, and used to solve the MKP. These main improved strategies are： the so- lution of the LP-relaxed MKP is used as the initial solution; the repair and local improvement operators are used to avoid the loss of population diversity. By using a standard set of large-sized test data to test the new GA, the results show that the new GA has better performance and converges much faster to better solutions.
出处
《计算机与现代化》
2012年第9期140-142,共3页
Computer and Modernization
基金
国家自然科学基金青年科学基金资助项目(81101490)
关键词
多约束0-1背包问题
遗传算法
线性规划松弛法
修复操作
局部优化
multi-constrained 0-1 knapsack problem
genetic algorithm
LP-relaxed algorithm
repair operator
local optimiza-tion
