作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2007, Vol. 33 ›› Issue (13): 31-33. doi: 10.3969/j.issn.1000-3428.2007.13.011

• 博士论文 • 上一篇    下一篇

求解大规模0-1背包问题的主动进化遗传算法

史 亮,董槐林,王备战,龙 飞   

  1. (厦门大学软件学院,厦门 361005)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-07-05 发布日期:2007-07-05

Genetic Algorithm Based on Active Evolution for Large Scale 0-1 Knapsack Problem

SHI Liang, DONG Huailin, WANG Beizhan, LONG Fei   

  1. (Software School, Xiamen University, Xiamen 361005)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-07-05 Published:2007-07-05

摘要: 针对遗传算法求解大规模0-1背包问题中存在的不足,将定向变异机制引入到遗传算法中,提出了基于主动进化遗传算法的0-1背包问题求解算法。该算法利用概率编码方案对种子个体进行编码,每代种群中的个体通过对该代种子个体进行测度而产生,用于定向变异的诱变因子将参与种子个体的进化。实验结果表明,该算法具有较好的全局寻优能力和执行效率。

关键词: 遗传算法, 定向变异, 0-1背包问题

Abstract: In order to overcome the problems in resolving large scale 0-1 knapsack problem with genetic algorithm, this paper introduces the directed mutation into the genetic algorithm and presents an active-evolution-based genetic algorithm(AEBGA) for the 0-1 knapsack problem. The algorithm uses probability coding mechanism to construct seed individual, which is used to generate individuals in each generation. In each generation, inducement is generated and used for seed individual evaluation. SGA, GQA and AEBGA are applied to solve large scale 0-1 knapsack problem and experiment results show that AEBGA has good ability of global optimization and high efficiency.

Key words: genetic algorithm, directed mutation, 0-1 knapsack problem

中图分类号: