求解0—1背包问题的共同进化遗传算法 |
| |
引用本文: | 刘娜,钟求喜.求解0—1背包问题的共同进化遗传算法[J].计算机科学,2001,28(9):102-105. |
| |
作者姓名: | 刘娜 钟求喜 |
| |
作者单位: | 国防科技大学计算机学院, |
| |
基金项目: | 国家自然科学基金(编号:69903010,60003002) |
| |
摘 要: | 0-1背包问题是一类组合优化问题,迄今已有40多年的研究历史,可广泛应用于碎片收集、作业调度、资金预算和货物装箱等领域。0-1背包问题是一类NP问题,所以传统方法如持续松弛法、分枝-界限法、动态规划法和一些近似算法等等,一般仅能获得问题的近似最优解。近年来,不少学者将稳健的遗传算法应用于0-1背包问题的求解,在问题求解质量方面收到了较好的效果。但是,由于传统的单种群遗传算法中一个染色体编码结构代表了问题的一个完整可行解,因此可能导致对解的较好部分的利用可能被其它较差的部分所掩盖,且问题求解效率随着问题规模的增大而下降。针对上述不足,本文基于合作式共同进化计算模型,将共同进化计算用于求解,提出一种求解0-1背包问题的共同进化遗传算法,以进一步提高问题的求解质量和算法效率。
|
关 键 词: | 0-1背包问题 遗传算法 共同进化 计算机 |
A Coevolutionary Genetic Algorithm for 0-1 Knapsack-Problem |
| |
Abstract: | |
| |
Keywords: | |
本文献已被 CNKI 维普 万方数据 等数据库收录! |
|
点击此处可从《计算机科学》下载全文 |
|