Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (10): 75-77.

• 理论研究 • Previous Articles     Next Articles

Improved adaptive genetic algorithm and its application on knapsack problem

YU Hui,WANG Hong-guo,XU Wei-zhi,GUO Yan-wei   

  1. School of Information Science and Engineering,Shandong Normal University,Ji’nan 250014,China
  • Received:2007-07-17 Revised:2007-09-27 Online:2008-04-01 Published:2008-04-01
  • Contact: YU Hui

改进的自适应遗传算法及在背包问题中的应用

于 惠,王洪国,徐卫志,郭彦伟   

  1. 山东师范大学 信息科学与工程学院,济南 250014
  • 通讯作者: 于 惠

Abstract: In this paper,the mutation only genetic algorithm is improved,adding transposition and greedy process of illegal individual.The crossover and mutation probability are adjusted automaticly with time and individual fitness.According to the experiments,the algorithm gets better results when solving the 0-1 knapsack problem.

Key words: knapsack problem, mutation matrix, Hamming distance matrix, transposition operator

摘要: 对只有变异的自适应遗传算法加以改进,引入变换算子和对非法个体的贪婪处理,能够随时间和个体的适应度大小自动调整变换概率、变异概率,不需要输入。实验表明,该算法在解决0-1背包问题时获得较好效果。

关键词: 背包问题, 变异矩阵, 海明距离矩阵, 变换算子