首页 | 本学科首页   官方微博 | 高级检索  
     

求解背包问题的贪心遗传算法及其应用
引用本文:贺毅朝,刘坤起,张翠军,张巍.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计,2007,28(11):2655-2657,2681.
作者姓名:贺毅朝  刘坤起  张翠军  张巍
作者单位:[1]石家庄经济学院信息工程系,河北石家庄050031 [2]中国地质大学计算机学院,湖北武汉430074
摘    要:分析了文献2]中求解背包问题(KP)的混合遗传算法(HGA)所采用的贪心变换方法缺陷;重新定义了贪心变换的概念,并给出了一种新的且更高效的贪心变换方法,将此方法与遗传算法相结合得到一种新的混合遗传算法,称之贪心遗传算法(简记GGA).利用GGA得出了文献2,4]中一个著名KP问题实例的目前最好结果;同时,对于文献7]中的KP问题实例和一个随机生成的KP问题实例,将GGA算法与求解KP问题的最有效算法HGA算法进行对比计算,结果表明GGA算法远远优于HGA算法.

关 键 词:背包问题  约束优化  混合遗传算法  贪心变换  贪心遗传算法  求解  背包问题  贪心遗传算法  应用  applications  problems  knapsack  genetic  algorithm  对比计算  有效算法  随机生成  结果  利用  结合  变换方法  重新定义  法缺陷  混合  文献  分析
文章编号: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 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号