自适应记忆遗传算法研究-《计算机技术与发展》

文章信息/Info

Keywords:: memory genetic algorithm; gene warehouse; adaptive; function optimization; TSP

摘要:: 针对遗传算法优化过程中仍然存在许多问题，文中提出了一种新的自适应记忆遗传算法。引入基因库的概念，用以存储重复出现个体的基因编码和对应的适应度值，进而解决重复个体适应度值的重复计算问题；利用Logistic曲线方程对遗传算法的交叉概率和变异概率进行自适应调整；以TSP为应用背景对文中算法进行实验，结果表明文中算法有效减少了算法的时间复杂度，其加速比能够达到49.70%左右。在算法的收敛性方面，改进后的算法收敛速度快于基本遗传算法，其所得解与TSPLIB提供的最优解的平均相对误差最大不超过9.38%。

Abstract:: There are still many problems in the optimization process of genetic algorithm. Propose a new adaptive memory genetic algo-rithm. The gene warehouse with appropriate scale is provided in thesis which is used to store gene encodings and individual fitness value of chromosomes repeated. The problem of repeatedly calculating individual fitness value of repeated chorosome is effectively solved through the previous method. The Logistic curve equation is applied to change crossover probability and mutation probability for impro-ving algorithm's adaptability. Adopt typical TSP as application background to test. Test results show that the algorithm proposed can ef-fectively reduce the time complexity of genetic algorithm and its speed up to about 49. 70% than original algorithm. On convergence of the algorithm,its convergence speed is faster than simple genetic algorithm. Also,mean relative error of optimal solutions solved with the improved algorithm relative to optimal solution provided by TSPLIB is no more than 9. 38%.