求解背包问题的贪心遗传算法及其应用

被引：43

作者：

贺毅朝

刘坤起

张翠军

张巍

机构：

[1] 石家庄经济学院信息工程系

来源：

计算机工程与设计 | 2007年 / 11期

关键词：

背包问题; 约束优化; 混合遗传算法; 贪心变换; 贪心遗传算法;

D O I：

10.16208/j.issn1000-7024.2007.11.048

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

分析了文献[2]中求解背包问题(KP)的混合遗传算法(HGA)所采用的贪心变换方法缺陷;重新定义了贪心变换的概念,并给出了一种新的且更高效的贪心变换方法,将此方法与遗传算法相结合得到一种新的混合遗传算法,称之贪心遗传算法(简记GGA)。利用GGA得出了文献[2,4]中一个著名KP问题实例的目前最好结果;同时,对于文献[7]中的KP问题实例和一个随机生成的KP问题实例,将GGA算法与求解KP问题的最有效算法HGA算法进行对比计算,结果表明GGA算法远远优于HGA算法。

引用

页码：2655 / 2657+2681 +2681

页数：4