Research Of Adaptive Memory Genetic Algorithm And Its Implementation On TSP Problems

Genetic Algorithm is an adaptive heuristic global optimization algorithm which imitates biological natural evolution process. There is only rarely auxiliary information needed when solving problems with genetic algorithm. At the same time, genetic algorithm easily combined with other domain knowledge and has good adaptability and parallel. So it has been widely applied in combinatorial optimization, machine learning, adaptive control, artificial life, etc fields. Although genetic algorithm has get enough attention about its theories and application researchs at home and abroad, and there have many remarkable research achievements been achieved, the theories and methods of genetic algorithm is yet to mature and there are still some shorteages needs to be further improved.First of all, according to the instance of function optimization solved with genetic algoritthm, this thesis analyzes chromosome repeated phenomenon which having the same genetic encoding in the optimization process of genetic algorithm. Also along with increasement of evolutionary algebraic, the probability of repeated individual emergence biger and biger. For the above phenomenon, the gene warehouse with appropriate scale is provided in thesis which is used to store gene encodings and individual fitness value of chromosomes repeated. Individuals of gene warehouse are sorted descendingly accoding to their individual fitness value. When calculating the fitness value of chorosome, the value can directly get from gene warehouse if there is the same genetic code chorosome in the gene warehouse. The problem of repeatedly calculating individual fitness value of repeated chorosome is effectively solved through the previous method. The proposed algorithm can reduce the time complexity and improve the calculation efficiency of genetic algorithm.Second, in view of the abov algorithm can’t dynamically adjust control parameters of genetic operators when excuting according to individual distribution in current population, the Logistic curve equation is applied to change crossover probability and mutation probability adjust formula combined with the similarity coefficient of population for improving algorithm’s adapbility and convergence based on design principle of adjust formula in thesis.Finally, this thesis adopts typical TSP problems as application background and Matlab R2009a and Mircrosoft Visual Studio2010as development environments, In thesis, the system adopting the improved algorithm to solve TSP problems is realized where test instances are selected from the city coordinate data of TSPLIB. And time cost of calculating individual fitness value and convergence for the improved algorithm are tested and verified through this system. Test results show that when the scale of population ranges from50to150and the scale of gene warehouse ranges from0.1times to0.2times of the population scale, the algorithm proposed in this thesis can effectively reduce the time complexity of genetic algorithm and its speed up to about49.70%than original algorithm. On convergence of the algorithm proposed in this thesis, its convergence speed is slightly slower than adaptive genetic algorithm proposed by Srinivas etc, but it 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 than9.38%.