基于遗传算法的0/1背包问题求解

被引：32

作者：

王莉

绍定宏

陆金桂

机构：

[1] 南京工业大学信息科学与工程学院

来源：

计算机仿真 | 2006年 / 03期

关键词：

遗传算法; 背包问题; 二重结构编码;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

背包问题是一个典型的NP完全问题。该文给出了背包问题基于0/1规划的数学模型,提出了解决该问题的二重结构编码的混合遗传算法;该算法在传统遗传编码方式的基础上提出了一种改进的编码方式二重结构编码,在约束条件的处理上结合"贪心法",提高了搜索效率。最后的实例仿真,通过大量的数值试验,给出了传统遗传编码与二重结构编码的混合遗传算法计算结果的比较,充分证明了使用二重结构编码的混合遗传算法来求解背包问题的有效性和实用性。

引用

页码：154 / 156

页数：3