| 基于遗传算法的0/1背包问题求解 |
| |
| 引用本文： | 王莉,绍定宏,陆金桂. 基于遗传算法的0/1背包问题求解[J]. 计算机仿真, 2006, 23(3): 154-156 |
| |
| 作者姓名： | 王莉 绍定宏 陆金桂 |
| |
| 作者单位： | 南京工业大学信息科学与工程学院,江苏,南京,210009;南京工业大学信息科学与工程学院,江苏,南京,210009;南京工业大学信息科学与工程学院,江苏,南京,210009 |
| |
| 摘 要： | 背包问题是一个典型的NP完全问题。该文给出了背包问题基于0/1规划的数学模型,提出了解决该问题的二重结构编码的混合遗传算法;该算法在传统遗传编码方式的基础上提出了一种改进的编码方式二重结构编码,在约束条件的处理上结合"贪心法",提高了搜索效率。最后的实例仿真,通过大量的数值试验,给出了传统遗传编码与二重结构编码的混合遗传算法计算结果的比较,充分证明了使用二重结构编码的混合遗传算法来求解背包问题的有效性和实用性。
|
| 关 键 词： | 遗传算法 背包问题 二重结构编码 |
| 文章编号： | 1006-9348（2006）03-0154-03 |
| 收稿时间： | 2005-01-09 |
| 修稿时间： | 2005-01-09 |
The Genetic Algorithm of Solving 0/1knapsack Problem |
| |
| WANG Li,SHAO Ding-hong,LU Jin-gui. The Genetic Algorithm of Solving 0/1knapsack Problem[J]. Computer Simulation, 2006, 23(3): 154-156 |
| |
| Authors: | WANG Li SHAO Ding-hong LU Jin-gui |
| |
| Affiliation: | College of Information Science and Engineering NanJing University of Technology, NanJing Jiangsu 210(109, China |
| |
| Abstract: | Knapsack problem is a typical NP complete problem.Knapsack problem's correspondent mathematical model is proposed in this paper,and the Genetic Algorithm with dual-structure codes is raised.In this algorithm,the dual-structure codes which is improved on the tradition coding moded is gived,and the Genetic Algorithm which is combined with the "greed algorithm"is used to deal with the restrict condition.Because of that ,the searching efficiency is improved .At last,the simulation experiment is given ,and the answer of the knapsack problem which is solved by two different encode methods is compared.By this comparition,the advantage which use double structure encode to solve knapsack problem is proved. |
| |
| Keywords: | Genetic Algorithm Knapsack problem dual-structure encode |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
