一种求解0-1背包问题的改进遗传算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (34): 44-46.

一种求解0-1背包问题的改进遗传算法

吕晓峰1，张勇亮2，马羚2

1.海军航空工程学院兵器科学与技术系，山东烟台 264001
2.海军航空工程学院研究生管理大队，山东烟台 264001

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-12-01 发布日期:2011-12-01

Improved genetic algorithm to 0-1 knapsack problem

LV Xiaofeng1，ZHANG Yongliang2，MA Ling2

1.Department of Armament Science and Technology，Naval Aeronautical and Astronautical University，Yantai，Shangdong 264001，China
2.Brigade of Graduate Student，Naval Aeronautical and Astronautical University，Yantai，Shangdong 264001，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-12-01 Published:2011-12-01

摘要/Abstract

摘要： 针对传统遗传算法（SGA）容易“早熟”的不足，提出一种求解0-1背包问题（KP）的改进遗传算法。借鉴二重结构编码的解码处理方法设计了一种新解码方法，在保证解可行性的同时修正种群中无对应可行解的个体;采用模拟退火算法和改进的精英选择算子改进SGA。实例仿真结果验证了改进遗传算法在进化效率和最优解搜索能力上的优越性。

关键词: 遗传算法, 背包问题, 解码, 模拟退火, 精英选择

Abstract: An improved Genetic Algorithm（GA） is proposed to solve 0-1 Knapsack Problem（KP） considering the deficiency of the Simple GA（SGA） that being easy to “precocity”.A new way to decode is designed to ensure solutions workable according to the way of dual-structure coding，and to revise individuals without corresponding solutions in the population at the same time.And SGA is improved by the Simulated Annealing（SA） algorithm and improved elite selection operator.The advantage of the improved GA in the evolution efficiency and the ability to search the best solution is proved by the simulation results.

Key words: Genetic Algorithm（GA）, Knapsack Problem（KP）, decode way, Simulated Annealing（SA）, elite selection

吕晓峰1，张勇亮2，马羚2. 一种求解0-1背包问题的改进遗传算法[J]. 计算机工程与应用, 2011, 47(34): 44-46.

LV Xiaofeng1，ZHANG Yongliang2，MA Ling2. Improved genetic algorithm to 0-1 knapsack problem[J]. Computer Engineering and Applications, 2011, 47(34): 44-46.

[1]	许昊，张凯，田英杰，种法广，王子超. 深度神经网络图像描述综述[J]. 计算机工程与应用, 2021, 57(9): 9-22.
[2]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[3]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[4]	刘万军，张正寰，曲海成. 融合DenseNet的多尺度图像去模糊模型[J]. 计算机工程与应用, 2021, 57(24): 219-226.
[5]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[6]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[7]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[8]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[9]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[10]	丁成，翁理国，夏旻，崔逸尘，钱俊豪，刘佳. 多注意力机制网络卫星图像分割算法[J]. 计算机工程与应用, 2021, 57(2): 223-229.
[11]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[12]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[13]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[14]	刘臣，陈静娴，郝宇辰，李秋，甄俊涛. 基于时空网络的地铁进出站客流量预测[J]. 计算机工程与应用, 2021, 57(18): 248-254.
[15]	童文林，陈德旺，黄允浒，吕宜生. 结合模拟退火与规则约简的模糊系统优化方法[J]. 计算机工程与应用, 2021, 57(16): 142-150.