| 一种基于模式替代的遗传算法解0/1背包问题 |
| |
| 引用本文： | 李康顺,贾玉珍,张文生. 一种基于模式替代的遗传算法解0/1背包问题[J]. 计算机应用研究, 2009, 26(2): 470-471 |
| |
| 作者姓名： | 李康顺 贾玉珍 张文生 |
| |
| 作者单位： | 江西理工大学信息工程学院,江西,赣州,341000;中国科学院,自动化研究所,北京,100080;江西理工大学信息工程学院,江西,赣州,341000;中国科学院,自动化研究所,北京,100080 |
| |
| 基金项目： | 国家“973”计划资助项目(2004CB318103)；江西省教育厅科学技术研究资助项目（赣教技字[2007]205号） |
| |
| 摘 要： | 背包问题是一个典型的 NP完全问题。提出一种基于模式替代的遗传算法解0/1背包问题思想，通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向，以提高遗传算法的搜索速度和寻找最优解的能力。通过仿真数值实验，将该方法与简单遗传算法、贪心算法计算结果比较分析，充分证明了使用基于模式替代遗传算法来求解背包问题的有效性和实用性。
|
| 关 键 词： | 背包问题 模式替代 遗传算法 |
Genetic algorithm with schema replaced for solving 0/1 knapsack problem |
| |
| LI Kang-shun,JIA Yu-zhen,ZHANG Wen-sheng. Genetic algorithm with schema replaced for solving 0/1 knapsack problem[J]. Application Research of Computers, 2009, 26(2): 470-471 |
| |
| Authors: | LI Kang-shun JIA Yu-zhen ZHANG Wen-sheng |
| |
| Affiliation: | (1.School of Information Engineering, Jiangxi University of Science & Technology, Ganzhou Jiangxi 341000, China;2.Institute of Automation, Chinese Academy of Sciences, Beijing 100080, China) |
| |
| Abstract: | Knapsack problem is a typical NP complete problem.This paper raised genetic algorithm with schema replaced for solving 0/1 knapsack problem.It leaded the search direction of the population to a schema by collecting the best several individuals in population.So,improved the searching efficiency and ability.At last,gave the simulation experiment,and the answer of the knapsack problem which was solved by simple genetic algorithm,compared greedy algorithm and genetic algorithm with schema replaced.By this compa... |
| |
| Keywords: | knapsack problem(KP) schema replaced genetic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
