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

摘要：

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

关键词：背包问题、约束优化、混合遗传算法、贪心变换、贪心遗传算法

所属期刊栏目：28

分类号：TP181(自动化基础理论)

资助基金：河北省教育厅科研项目2004454;2005338

在线出版日期：2007-07-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：2655-2657,2681