改进的自适应遗传算法求解0/1背包问题  

Modified adaptive genetic algorithms for solving 0/1 knapsack problems

作　　者：王娜[1] 向凤红[1] 毛剑琳[1] 

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650000

出　　处：《计算机应用》2012年第6期1682-1684,共3页journal of Computer Applications

基　　金：云南省应用基础研究基金资助项目(2009ZC050M);云南省教育厅科学研究基金资助项目(08Y0093)

摘　　要：为提高遗传算法求解问题的性能,提出一种改进的自适应遗传算法,该算法在交叉概率和变异概率公式中引入了当代迭代次数因子,提出了基因差别比例(Ca)的概念。Ca越大的基因位发生交叉、变异的概率越大,产生新个体的可能性越大;在模式生成操作中,确定基因位的选取同样由Ca决定。仿真结果表明,此算法在求解0/1背包问题时,其寻优能力有很大提高。To improve the performance of solving problems by genetic algorithm,an improved adaptive genetic algorithm was proposed in the paper.In the algorithm,the contemporary iteration factor was introduced into the formulas of crossover probability and mutation probability.The concept of gene difference ratio（Ca） was proposed.The greater the gene difference ratio was,the more likely a gene-bit crossover and mutation happened,and a new individual was more likely to emerge.In the pattern generation operation,gene selection was also decided by gene difference ratio.The simulation experiments show that,the optimization ability of the improved algorithm is superior to the traditional algorithm in solving 0/1 knapsack problem.

关 键 词：0/1背包问题 自适应遗传算法 交叉变异概率 交叉变异操作 模式替代操作 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]