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

Modified adaptive genetic algorithms for solving 0/1 knapsack problems

为提高遗传算法求解问题的性能,提出一种改进的自适应遗传算法,该算法在交叉概率和变异概率公式中引入了当代迭代次数因子,提出了基因差别比例(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.