| 求解多约束0-1背包问题的遗传算法的改进 |
| |
| 引用本文： | 吕聪颖,胡平,刘炯.求解多约束0-1背包问题的遗传算法的改进[J].计算机与现代化,2012(9):140-142. |
| |
| 作者姓名： | 吕聪颖 胡平 刘炯 |
| |
| 作者单位： | [1]南阳理工学院计算机与信息工程学院,河南南阳473000 [2]中华人民共和国国家知识产权局,北京100088 |
| |
| 基金项目： | 国家自然科学基金青年科学基金资助项目（81101490） |
| |
| 摘 要： | 提出对基本遗传算法(Genetic Algorithm,GA)的改进策略,并将其应用于多约束0-1背包问题(Multi-constrained 0-1Knapsack Problems,MKP)的求解。改进策略主要有:将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失,将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后,对大规模测试数据的标准集进行实验,并将该算法与先前的方法进行比较,结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。
|
| 关 键 词： | 多约束0-1背包问题 遗传算法 线性规划松弛法 修复操作 局部优化 |
Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem |
| |
| LO Cong-ying,HU Ping,LIU Jiong.Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem[J].Computer and Modernization,2012(9):140-142. |
| |
| Authors: | LO Cong-ying HU Ping LIU Jiong |
| |
| Affiliation: | 1. College of Computer and Information Engineering, Nanyang Institute of Technology, Nanyang 473000, China; 2. State Intellectual Property Office of the People＇s Republic of China, Beijing 100088, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | multi-constrained 0-1 knapsack problem genetic algorithm LP-relaxed algorithm repair operator local optimiza-tion |
| 本文献已被 CNKI 维普 等数据库收录！ |
