| 二重结构编码算法求解背包问题的分析及改进 |
| |
| 引用本文： | 施映,何嘉.二重结构编码算法求解背包问题的分析及改进[J].成都信息工程学院学报,2007,22(3):301-305. |
| |
| 作者姓名： | 施映 何嘉 |
| |
| 作者单位： | 成都信息工程学院,四川成都,610225 |
| |
| 摘 要： | 给出了背包问题的数学模型,分析了解决该问题的二重结构编码的混合遗传算法,在此基础上通过引入价值密度的概念并与局部搜索算法相结合对算法进行了改进,并通过大量的数值试验充分证明了改进后的二重结构编码算法的有效性有了一定的提高.
|
| 关 键 词： | 遗传算法 价值密度 背包问题 二重结构编码 二重结构编码 编码算法 求解 背包问题 分析 改进 knapsack problem based codes strategy improvement 有效性 数值试验 结合 搜索算法 局部 度的概念 价值 遗传算法 混合 |
| 文章编号： | 1671-1742（2007）03-0301-05 |
| 收稿时间： | 2006-10-12 |
| 修稿时间： | 2006-10-122006-11-06 |
Analysis and improvement strategy of dual-structure codes based on knapsack problem |
| |
| SHI Ying,HE Jia.Analysis and improvement strategy of dual-structure codes based on knapsack problem[J].Journal of Chengdu University of Information Technology,2007,22(3):301-305. |
| |
| Authors: | SHI Ying HE Jia |
| |
| Institution: | Dept. of Computer Science, CULT, Chengdu 610225, China |
| |
| Abstract: | The knapsack problem is a typical NP complete problem. Its correspondent mathematical model is proposed. The genetic algorithm with the dual-structure codes is analyzed. The concept of the value density and the partial searching algorithm are combined to improve the algorithm. The experiment result shows that the improved one is more efficient. |
| |
| Keywords: | genetic algorithm value density knapsack problem dual-structure encode |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
