摘要
针对遗传算法求解大规模0-1背包问题中存在的不足,将定向变异机制引入到遗传算法中,提出了基于主动进化遗传算法的0-1背包问题求解算法。该算法利用概率编码方案对种子个体进行编码,每代种群中的个体通过对该代种子个体进行测度而产生,用于定向变异的诱变因子将参与种子个体的进化。实验结果表明,该算法具有较好的全局寻优能力和执行效率。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2007年第13期31-33,共3页
Computer Engineering
基金
国家"985"工程二期基金资助项目(0000-X07204)
福建省自然科学基金资助项目(2006J0222)
关键词
遗传算法
定向变异
0-1背包问题
genetic algorithm
directed mutation
0- 1 knapsack problem
