求解多约束0-1背包问题的遗传算法的改进

doi:10.3969/j.issn.1006-2475.2012.09.035

计算机与现代化 ›› 2012, Vol. 1 ›› Issue (9): 140-142.doi: 10.3969/j.issn.1006-2475.2012.09.035

求解多约束0-1背包问题的遗传算法的改进

吕聪颖1，胡平2，刘炯2

1.南阳理工学院计算机与信息工程学院，河南南阳473000；2.中华人民共和国国家知识产权局，北京100088

收稿日期:2012-05-04 修回日期:1900-01-01 出版日期:2012-09-21 发布日期:2012-09-21

Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem

LV Cong-ying1， HU Ping2， LIU Jiong2

1. College of Computer and Information Engineering, Nanyang Institute of Technology, Nanyang 473000, China;2. State Intellectual Property Office of the People’s Republic of China, Beijing 100088, China

Received:2012-05-04 Revised:1900-01-01 Online:2012-09-21 Published:2012-09-21

摘要/Abstract

摘要： 提出对基本遗传算法(Genetic Algorithm，GA)的改进策略，并将其应用于多约束0-1背包问题(Multi-constrained 0-1 Knapsack Problems，MKP)的求解。改进策略主要有：将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失，将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后，对大规模测试数据的标准集进行实验，并将该算法与先前的方法进行比较，结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。


关键词: 多约束0-1背包问题, 遗传算法, 线性规划松弛法, 修复操作, 局部优化

Abstract: he improved strategies for GA are presented, and used to solve the MKP. These main improved strategies are: the solution of the LP-relaxed MKP is used as the initial solution; the repair and local improvement operators are used to avoid the loss of population diversity. By using a standard set of large-sized test data to test the new GA, the results show that the new GA has better performance and converges much faster to better solutions.


Key words: multi-constrained 0-1 knapsack problem, genetic algorithm, LP-relaxed algorithm, repair operator, local optimization

吕聪颖;胡平;刘炯. 求解多约束0-1背包问题的遗传算法的改进[J]. 计算机与现代化, 2012, 1(9): 140-142.

LV Cong-ying;HU Ping;LIU Jiong. Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem[J]. Computer and Modernization, 2012, 1(9): 140-142.

[1]	林启钊, 彭志平, 郭棉, 崔得龙. 基于双向多步预测的炉管温度场重构方法[J]. 计算机与现代化, 2024, 0(01): 53-58.
[2]	刘显茁, 邓韦斯, 谢恩彦. 考虑分布式发电并网的配电网自适应保护系统[J]. 计算机与现代化, 2023, 0(09): 120-126.
[3]	张志霞, 谢宝强. 基于FCGA-LSTM与迁移学习的天然气负荷预测[J]. 计算机与现代化, 2023, 0(07): 7-12.
[4]	汪敏, 徐英豪, 朱习军. 基于改进遗传算法优化BP神经网络的糖尿病并发症预测模型#br#[J]. 计算机与现代化, 2022, 0(11): 69-74.
[5]	王扬, 陈梅, 李晖. FOCoR:一种基于特征选择优化的课程推荐技术[J]. 计算机与现代化, 2022, 0(10): 1-7.
[6]	冉昊杰, 王宏智. 基于改进模拟退火算法的生鲜农产品配送中心选址[J]. 计算机与现代化, 2022, 0(10): 36-40.
[7]	战俊伟, 庄毅. 基于能耗与延迟优化的移动边缘计算任务卸载模型及算法[J]. 计算机与现代化, 2022, 0(08): 86-93.
[8]	吴代漾, 赵洁, 梁家铭, 董振宁, 梁周扬. C2C在线短租跨平台房东匹配算法[J]. 计算机与现代化, 2022, 0(06): 43-48.
[9]	徐胜超, 熊茂华. 基于遗传算法的容器云资源配置优化[J]. 计算机与现代化, 2022, 0(01): 108-112.
[10]	徐明, 张剑铭, 陈松航, 陈豪. 柔性作业车间调度问题的多目标优化算法[J]. 计算机与现代化, 2021, 0(12): 1-6.
[11]	张林鹏, 汪西原, 李强. 基于双池化特征加权结构CNN的图像分类[J]. 计算机与现代化, 2021, 0(11): 67-71.
[12]	陈春燕, 刘梦赤. 基于粒子群遗传算法的智能组卷策略[J]. 计算机与现代化, 2021, 0(08): 16-23.
[13]	杨晓东. 基于遗传算法的会计资源共享管理风险评估模型[J]. 计算机与现代化, 2021, 0(06): 24-28.
[14]	刘军, 彭慧娴, 黄斌, 托尼·谢伊. 基于BP-GamysBoost的乳腺癌诊断模型[J]. 计算机与现代化, 2021, 0(04): 8-14.
[15]	徐胜超. 利用遗传算法完成虚拟机放置策略的优化[J]. 计算机与现代化, 2020, 0(12): 25-31.

求解多约束0-1背包问题的遗传算法的改进

Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价