| 求解背包问题的贪心遗传算法及其应用 |
| |
| 引用本文： | 贺毅朝,刘坤起,张翠军,张巍. 求解背包问题的贪心遗传算法及其应用[J]. 计算机工程与设计, 2007, 28(11): 2655-2657,2681 |
| |
| 作者姓名： | 贺毅朝 刘坤起 张翠军 张巍 |
| |
| 作者单位： | 石家库经济学院,信息工程系,河北,石家庄,050031;石家库经济学院,信息工程系,河北,石家庄,050031;中国地质大学,计算机学院,湖北,武汉,430074 |
| |
| 摘 要： | 分析了文献[2]中求解背包问题(KP)的混合遗传算法(HGA)所采用的贪心变换方法缺陷;重新定义了贪心变换的概念,并给出了一种新的且更高效的贪心变换方法,将此方法与遗传算法相结合得到一种新的混合遗传算法,称之贪心遗传算法(简记GGA).利用GGA得出了文献[2,4]中一个著名KP问题实例的目前最好结果;同时,对于文献[7]中的KP问题实例和一个随机生成的KP问题实例,将GGA算法与求解KP问题的最有效算法HGA算法进行对比计算,结果表明GGA算法远远优于HGA算法.
|
| 关 键 词： | 背包问题 约束优化 混合遗传算法 贪心变换 贪心遗传算法 |
| 文章编号： | 1000-7024（2007）11-2655-03 |
| 修稿时间： | 2006-05-16 |
Greedy genetic algorithm for solving knapsack problems and its applications |
| |
| HE Yi-chao,LIU Kun-qi,ZHANG Cui-jun,ZHANG Wei. Greedy genetic algorithm for solving knapsack problems and its applications[J]. Computer Engineering and Design, 2007, 28(11): 2655-2657,2681 |
| |
| Authors: | HE Yi-chao LIU Kun-qi ZHANG Cui-jun ZHANG Wei |
| |
| Affiliation: | 1.Department of Information Project, Shijiazhuang University of Economics, Shijiazhuang 050031, China; 2. School of Computer, China University of Geosciences, Wuhan430074, China |
| |
| Abstract: | The flaw of greedy transform method adopted by hybrid henetic algorithm(HGA)is analyzed,which is a effective algorithm to solve knapsack problem in Ref.[2].A new define on greedy transform is redefined and a new and more effective implement method is advanced.The new method is combined with genetic algorithm to propose a new hybrid genetic algorithm that is greedy genetic algo- rithm(GGA).Using GGA,a best solution of famous knapsack sample is found in Ref.[2,4] at present.Moreover,for a knapsack sample in Ref.[7] and a randomly generated knapsack sample,the calculation results using GGA and HGA show that the global con- vergence of GGA is much more superior to HGA. |
| |
| Keywords: | knapsack problem constrained optimizations hybrid genetic algorithm greedy transform greedy genetic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
