Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (30): 47-49.DOI: 10.3778/j.issn.1002-8331.2008.30.014

• 理论研究 • Previous Articles     Next Articles

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

DONG Peng   

  1. 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

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

董 鹏   

  1. 兰州交通大学 交通运输学院,兰州 730070
  • 通讯作者: 董 鹏

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背包问题。

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