|
|||||
|
|
| 求解多限制0-1背包问题的混合遗传算法 | |
| 引用本文： | 宋海生,宋海洲,傅仁毅,徐瑞松.求解多限制0-1背包问题的混合遗传算法[J].计算机工程,2009,35(13):4-7,10. |
| 作者姓名： | 宋海生 宋海洲 傅仁毅 徐瑞松 |
| 作者单位： | 1. 顺德职业技术学院计算机技术系,佛山,528300;中国科学院广州地球化学研究所,广州,510640;中国科学院研究生院,北京,100049 2. 华侨大学数学科学学院,泉州,362021 3. 顺德职业技术学院计算机技术系,佛山,528300 4. 中国科学院广州地球化学研究所,广州,510640 |
| 基金项目： | 中国科学院知识创新工程重要方向基金资助项目 |
| 摘 要： | 为求解多限制0-1背包问题，设计一种新的价值密度，提出一种基于贪心法的混合遗传算法，采用二进制编码对适应值进行升序排列，并运用轮盘赌选择方法对背包资源利用不足的可行解进行修正处理，对不可行解进行修复处理，并将其与传统遗传算法进行比较。实验结果表明，该算法能够有效提高问题求解的速度和精度，具有一定优越性。 |
| 关 键 词： | 背包问题 贪心法 遗传算法 不可行解 |
| 修稿时间： | |
Hybrid Genetic Algorithm for Multiconstraint 0-1 Knapsack Problem |
|
| SONG Hai-sheng,SONG Hai-zhou,FU Ren-yi,XU Rui-song.Hybrid Genetic Algorithm for Multiconstraint 0-1 Knapsack Problem[J].Computer Engineering,2009,35(13):4-7,10. | |
| Authors: | SONG Hai-sheng SONG Hai-zhou FU Ren-yi XU Rui-song |
| Affiliation: | 1.Dept.of Computer Technology;Shunde Polytechnic;Foshan 528300;2.Guangzhou Institute of Geochemistry;Chinese Academy of Sciences;Guangzhou 510640;3.Graduate University of Chinese Academy of Sciences;Beijing 100049;4.School of Mathematical Sciences;Huaqiao University;Quanzhou 362021 |
| Abstract: | In order to solve multi-constraint 0-1 knapsack problem, a new profit-density is designed, on basis of which, a Hybrid Genetic Algorithm(HGA) based on greedy algorithm is proposed, which uses the binary code to amend the feasible solution, and applies roulette wheel selection method to rectify knapsack resources with insufficient use, and repairs the infeasible solution.The algorithm is compared with other traditional ones.Experimental results show this HGA can promote the speed and accuracy of solving rele... |
| Keywords: | knapsack problem greedy algorithm Genetic Algorithm(GA) infeasible solution |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程》浏览原始摘要信息 | |
| 点击此处可从《计算机工程》下载全文 | |