求解0/1背包问题的快速收敛的混合遗传算法

doi:10.3778/j.issn.1002-8331.2008.30.014

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (30): 47-49.DOI: 10.3778/j.issn.1002-8331.2008.30.014

求解0/1背包问题的快速收敛的混合遗传算法

董鹏

兰州交通大学交通运输学院，兰州 730070

收稿日期:2007-11-27 修回日期:2008-02-26 出版日期:2008-10-21 发布日期:2008-10-21
通讯作者: 董鹏

Hybrid genetic algorithm with high convergent speed for solving 0/1 knapsack problem

DONG Peng

School of Traffic and Transportation Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China

Received:2007-11-27 Revised:2008-02-26 Online:2008-10-21 Published:2008-10-21
Contact: DONG Peng

摘要/Abstract

摘要： 在结合贪婪算法的混合遗传算法中，将基于轮盘赌的选择算子改为稳态复制的选择算子，形成的新的混合遗传算法能显著加快收敛。文中也给出了结束迭代的两个判定条件。通过对三个实例的大量仿真实验，研究了交叉概率、种群数量和替换率对算法性能的影响。实验结果表明这一新算法收敛速度快，寻优能力强，更适合于求解大规模0/1背包问题。

关键词: 混合遗传算法, 0/1背包问题, 稳态复制, 选择算子, 快速收敛

Abstract: In the hybrid genetic algorithm which combined with greedy algorithm，when the roulette wheel selection operator is replaced with a new selection operator based on steady-state reproduction strategy，the convergent speed of the new algorithm can be accelerated remarkably.Two terminations of iteration for the new algorithm are presented in this paper.By many simulation tests，how the crossover probability，population size and replace rate affect the performance of the new algorithm has been studied.It is shown by experiment that the new algorithm has higher convergent speed and is able to find better solutions，so it is more suitable to be used to solve large scale 0/1 knapsack problem.

Key words: hybrid genetic algorithm, 0/1 knapsack problem, steady-state reproduction, selection operator, rapidity of convergence

董鹏. 求解0/1背包问题的快速收敛的混合遗传算法[J]. 计算机工程与应用, 2008, 44(30): 47-49.

DONG Peng. Hybrid genetic algorithm with high convergent speed for solving 0/1 knapsack problem[J]. Computer Engineering and Applications, 2008, 44(30): 47-49.

[1]	刘兰芬，杨信丰. 基于混合遗传算法的有效路径求解[J]. 计算机工程与应用, 2019, 55(11): 244-249.
[2]	陈闯1，RYAD Chellali1，邢尹2. 改进GWO优化SVM的语音情感识别研究[J]. 计算机工程与应用, 2018, 54(16): 113-118.
[3]	张赫男，张绍文. 采用改进的混合遗传算法求解高校排课问题[J]. 计算机工程与应用, 2015, 51(5): 240-246.
[4]	吴家皋1，张曦1，庄嵩杰1，邹志强1，胡斌2. 面向多图层的空间矢量数据缓存更新策略研究[J]. 计算机工程与应用, 2014, 50(7): 89-93.
[5]	游伟，雷定猷，朱向. 三维装箱问题的偏随机密钥混合遗传算法[J]. 计算机工程与应用, 2014, 50(22): 265-270.
[6]	符昊，葛洪伟，邵长鲁，朱亮. 造船监理员调度模型和混合遗传算法求解[J]. 计算机工程与应用, 2014, 50(21): 238-242.
[7]	彭必灿，张正道. 基于稀疏主元分析的过程监控研究[J]. 计算机工程与应用, 2014, 50(18): 240-245.
[8]	王娜，向凤红，毛剑琳. 改进型遗传蚁群混合算法求解0/1背包问题[J]. 计算机工程与应用, 2013, 49(9): 54-56.
[9]	刘波1，2，李波1，李砚1. 不确定条件下应急资源布局的鲁棒双层优化模型[J]. 计算机工程与应用, 2013, 49(16): 13-17.
[10]	赵东红1，2，王来生2，张峰1. 遗传算法的粗糙集理论在文本降维上的应用[J]. 计算机工程与应用, 2012, 48(36): 125-128.
[11]	宋晓萍1，胡常安2. 离散杂草优化算法在0/1背包问题中的应用[J]. 计算机工程与应用, 2012, 48(30): 239-242.
[12]	刘菲，吕世辉，赵中华. 基于多步强化变异算子的混合遗传算法[J]. 计算机工程与应用, 2011, 47(29): 46-48.
[13]	王建华1，2，李南2，郭慧2. 求解敏捷供应链调度优化问题的混合遗传算法[J]. 计算机工程与应用, 2011, 47(17): 224-228.
[14]	李楠1，2，高鹏东1，鲁永泉1，余文华1. 并行混合遗传算法在深度像配准中的应用研究[J]. 计算机工程与应用, 2011, 47(12): 12-15.
[15]	雷阳，李树荣，张强，张晓东. 基于骨干粒子群的混合遗传算法及其应用[J]. 计算机工程与应用, 2010, 46(36): 7-10.

求解0/1背包问题的快速收敛的混合遗传算法

Hybrid genetic algorithm with high convergent speed for solving 0/1 knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics