背包问题的一个k阶优化遗传算法

• 作者: 俞一 沈灏
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 动态规划 分枝定界 贪婪算法 遗传算法
• 年，卷（期）: 2007,（4）
• 页码范围: 92-94
• 页数: 3页
• 分类号: O212
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2007.04.024

摘要

背包问题是一个NP困难问题,该文在已有的性能比为(k+1)/k的k阶优化算法基础上,提出一个具有与k阶优化算法具有相同的近似性能比的启发式算法:将k阶优化法的结果加入遗传算法的初始种群使原本没有性能比保证的遗传算法具有近似性能比,在保证计算精度的同时大大降低算法的搜索次数,从而提高计算效率.这种算法也具有较高的适应性,可以根据计算速度或精度要求选择适当的正整数k.该文对提到的多种算法编程实现并加以分析,通过比较各种算法的程序输出结果和CPU时间,验证了结论的正确性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈灏	杭州电子科技大学理学院	15	22	3.0	3.0
2	俞一	杭州电子科技大学理学院	1	3	1.0	1.0